Search

Emerging applications involving a high degree of uncertainty, dynamics, variability and unpredictability have begun to impart greater complexity to tasks performed by robots. In these kinds of environments, one of the most common causes for robot failures has been linked to the inability of the underlying planner to adapt to changing conditions in the environment. While an extensive range of methods have been developed to solve static planning problems in the robotics domain, until now solving the dynamic counterparts of these problems remain mostly elusive. Motivated by these challenges, this thesis presents developments that advance the state-of-the-art in optimal task and motion planning to address the dynamic variant of common robotic planning problems. Studies into adaptive planning problems are conducted to investigate the challenges that arise when extending planning methods from offline planning to online planning. In particular, this research seeks to characterise the inter actions between plan quality and computational efficiency when solving dynamic planning problems and to identify the practical considerations for implementing adaptive planning algorithms in physical systems. The contributions of this thesis are a number of fast yet practical planning techniques and methods that provide and maintain near-optimal, collision-free solutions to complex planning problems involving dynamic environments. In this thesis I first describe a case study that examines the challenges unique to dynamic motion planning through a robotic pick and place task. The observations derived from this case study inspired the development of two new methods for solving complex task planning problems. The first of these is an adaptive task and path planning framework that addresses the optimal task planning problem for mobile robots under dynamic conditions. This framework integrates a sampling-based multi-goal path planning algorithm with symbolic task planning to incrementally find high-quality task plans. Crucially, the framework supports anytime-like planning and dynamic re-planning of both tasks and low-level motions to enable fast and adaptive computation of optimal solutions. To support this, a tree pruning technique is proposed for multi-goal planning problems to substantially reduce the time and memory complexity of the planner. In the second half of this thesis, I present a highly competitive clustering-based algorithm for robotic task sequencing problems (RTSPs). Unlike existing methods, the algorithm is capable of finding near-optimal solutions for complex tasks involving hard spatial constraints. With a view towards dynamic robotic task sequencing, I go on to introduce two new concepts to the RTSP. The first is partial planning, which adopts the idea of planning-during-execution to reduce the pre-execution planning time of an algorithm for online applications. The second is the concept of dynamic RTSPs, a new sub-class of RTSPs that involve dynamic ally-changing problem variables. I subsequently present an adaptive algorithm for online tracking of near-optimal RTSP solutions under dynamic influences. As a pioneering work within the scope of dynamic task sequencing, I provide a quantitative evaluation of the algorithm for the purpose of benchmarking in future developments.