Abstract
Integrating task and motion planning is becoming increasingly important due to the recognition that a growing number of robotics applications in navigation, search-and-rescue missions, manipulation, and medicine involve reasoning with both discrete abstractions and continuous motions. The problem poses unique computational challenges: a vast hybrid discrete/continuous space must be searched while accounting for complex geometries, motion dynamics, collision avoidance and temporal goals. This paper takes the position that continued progress relies on integrative approaches that bring together techniques from robotics and AI. In this context, the paper examines robot motion planning with temporal-logic specifications and discusses open challenges and directions for future research. The paper aims to promote a continuing dialog between robotics and AI communities.
Introduction
A growing number of diverse robotics applications in mobile navigation, search-and-rescue missions, manipulation, game design and surgical procedures involve reasoning with both discrete actions and continuous motions. In this context, linear temporal logic (LTL) has often been used to express tasks by combining propositions with logical (∧ and, ∨ or, ¬ not) and temporal (◯ next, ♢ eventually, ⊔ until, □ always) operators. As an illustration, the task of inspecting several areas in a damaged building can be expressed as
Given a robot model, an initial state, a description of the environment and a task specification as a formula ϕ in LTL, the combined task- and motion-planning problem considered in this paper is to plan a collision-free and dynamically-feasible motion trajectory that satisfies ϕ. Such problem poses unique computational challenges stemming from (i) robot dynamics and collision avoidance, (ii) temporal constraints and (iii) intertwined dependencies between motion trajectories and temporal constraints.
At the continuous level, the planner needs to generate dynamically-feasible motions that the robot can execute in the physical world. Robot dynamics express physical constraints on the feasible motions, such as bounding the velocity and directions of motions, ensuring a minimum turning radius or keeping the wheels from sliding sideways. Moreover, the presence of obstacles makes planning more challenging since the planned motions must also be collision-free, often requiring the robot to pass through narrow passages and unstructured terrains.
Challenges arise at the discrete level, as well, and significant work in AI is devoted to task planning [70]. In this domain, the task is typically broken down into sequences of actions to be executed by the robot. In this context, LTL has been used to plan for temporally extended goals [3] and to define the semantics for planning languages [55]. Other temporal logics, such as temporal action logic, have also been developed to facilitate reasoning about actions and change [20,47].
When considering the combined motion-planning problem with dynamics and LTL specifications, there are additional challenges due to the intertwined dependencies. In fact, a discrete solution that satisfies an LTL formula ϕ may not be feasible due to constraints imposed by obstacles and dynamics. In the other direction, collision-free and dynamically-feasible trajectories may violate constraints imposed by ϕ.
This paper takes the position that continued progress in addressing the combined task- and motion-planning problem requires integrative approaches that bring together techniques from robotics and AI. The paper examines recent progress and discusses open challenges and directions for future research. The discussion is motivated by the following questions:
What components enable a successful coupling of planning in discrete and continuous spaces? How can advances in discrete planning and motion planning be leveraged to enhance the performance of the overall framework? How can the framework employ information gathered about the space it explores to adapt itself to relevant unexplored discrete actions and continuous regions? What theoretical guarantees can be offered? How can the framework adapt to changing environmental and contextual conditions?
The discussion takes place in the context of integrating task and motion planning when dealing with high-dimensional systems, nonlinear dynamics, and tasks given by LTL. This is by no means an exhaustive discussion of the burgeoning body of work on integrating task and motion planning, which also covers manipulation, uncertainty, planning languages and other aspects [10,12,16,22,25,33,48,62,68,74,81,82]. Several workshops at robotics and AI conferences have also been dedicated to this topic. The goal of this paper is to contribute to the dialog between the two communities.
The paper is organized as follows. Section 2 discusses progress and challenges in motion planning. Section 3 discusses the LTL formalism for task specification. Section 4 discusses controller-synthesis approaches. Section 5 focuses on key aspects and challenges when coupling discrete planning and sampling-based motion planning. Section 6 discusses results in theoretical analysis and their ramifications. Section 7 presents replanning as a viable approach to adapt to dynamic environments. The paper concludes in Section 8 with a brief summary of the main discussion points.
Robot motion planning
The motion-planning problem is to find a trajectory from an initial state to a goal state while avoiding collision with obstacles. This is an essential problem that is embedded in almost all robotics applications [17,50].
While initially considered in a geometric setting, such as the piano mover’s problem [72], motion planning for complex robots requires taking into account the robot dynamics so that the planned motions can be executed in the physical world. The continuous, dynamically-feasible, motion of a robot is often formalized using a function
Even when not considering the dynamics, motion planning is PSPACE-hard [69]. Complete algorithms, which provide a solution if one exists and return failure otherwise, are conceptually complex, hard to implement, and have an exponential dependency on the degrees-of-freedom (DOFs) of the robot [11]. These computational hardness results are directly related to the curse of dimensionality: the size of the search space gets large exponentially fast with the number of DOFs. When dynamics are taken into account, the problem becomes undecidable since differential equations can be used to simulate arbitrary Turing machines [8].
Often, practical approaches to motion planning relax this completeness guarantee in order to alleviate the difficulties implied by the curse of dimensionality. Sampling-based motion planning in particular has resulted in many practical algorithms which guarantee only probabilistic completeness, i.e., a solution is found, when it exists, with probability approaching one as the number of samples approaches infinity [17,50]. The key insight is to selectively sample and explore the space of feasible motions. Numerous formulations have been developed, most notably PRM [38], RRT [51] and others [28,31,35,61,65,75] (see [17,50] for more). To account for dynamics, sampling-based approaches typically expand a motion tree starting from the initial state and incrementally adding collision-free and dynamically-feasible trajectories as branches, as shown in Fig. 1.
Sampling-based motion planners have now been used to solve high-dimensional problems ranging from navigation, manipulation, to computational biology and medicine [2,9,45,58,76]. Another success story has been their use in the DARPA Urban Challenge, which required teams to build a fully autonomous car that can navigate in urban traffic. In a fierce competition, among close to one hundred teams, MIT’s entry vehicle Talos was one of the six vehicles that successfully completed a course of sixty miles [52]. Talos (Fig. 2) uses state-of-the-art estimation algorithms to fuse all the sensory information obtained from its laser-range finders, radars, cameras and navigation system into a live local map of drivable regions and obstacles/hazards. To navigate through this map, Talos uses a carefully-engineered RRT-based planning algorithm.

Illustration of sampling-based tree search. Curves shown in red correspond to collision-free and dynamically-feasible trajectories, which are obtained by applying input controls and integrating the differential equations of motion. (The colors are visible in the online version of the article;

Left: Talos, team MIT’s entry vehicle in the DARPA Urban Challenge. Right: The tree maintained by the RRT algorithm is shown overlayed on the obstacle map. The trajectories that make up the tree are shown in yellow and blue tones, the obstacles are shown in red, the drivable region is shown in black. The left-, front- and right-camera views are shown at the top of the figure to the right. (The colors are visible in the online version of the article;
Motion planning, however, has generally considered just the reachability problem of computing a trajectory to the goal region. PRM, RRT and other sampling-based algorithms were not designed to take into account high-level specifications given by formal models, such as LTL. As discussed in the rest of the paper, there are significant challenges when considering the combined task- and motion-planning problem.
There are fundamental research issues in developing task-specification formalisms, particularly as it relates to balancing expressiveness with ease-of-use, and ensuring amenability to efficient computation and reasoning. To increase expressiveness and facilitate interaction, it is beneficial to describe tasks in an easy-to-use yet expressive structured language, which can internally be translated into a formalism based on well-established logics, such as LTL [67].
LTL syntax
Let Π denote a set of propositions, where each
Every proposition
The expressiveness of temporal logic makes it possible to consider different constructs, such as
coverage: “inspect sequencing: “inspect partial ordering: “take measurements in conditions: “if ship detected, then track until identified” avoidance and persistency: “avoid hazardous areas; move slowly”
where
Based on the compositional nature of LTL, complex tasks can be constructed by composing simpler ones. As an illustration, the task of using an underwater vehicle to inspect an offshore platform can employ propositions that express detection of pipes, valves, anchors, anchor lines, flotation chambers and other components, and their status (damaged or functional). Partial ordering constructs can be used to prioritize the inspection of critical components. Conditional constructs can be employed to carry out closer inspections when there is some indication of damage of a particular component. Avoidance and persistency can ensure that the vehicle maintains a safe minimum distance away from the platform components, while still being close enough to carry out inspections. Coverage criteria can ensure that all components have been inspected.
The semantics of a proposition

Trajectory generates the word
In this way, when
The combined task- and motion-planning problem is then to compute a control function
A growing body of work has focused on synthesizing reactive controllers that satisfy LTL specifications. These approaches rely on a discrete abstraction of the continuous system, often obtained by partitioning the continuous state space into polytopes. Propositions are defined over the polytopes and actions refer to discrete functions of the robot such as move left, right, up, down, stand up, sit down. The overall behavior of the robot is captured by an automaton which is synthesized from the LTL specification and the discrete abstraction using techniques from model checking. Each transition in the automaton corresponds to an action with well-defined preconditions and postconditions. In order for the automaton to be viable, controllers must be available for each action that are capable of generating collision-free and dynamically-feasible trajectories that are compatible with the action. The work in [26] obtained the discrete abstraction as a graph whose vertices correspond to regions in a workspace decompositions and edges capture the physical adjacency of the regions. Given an LTL formula over propositions of the form “robot is in region
Controller-synthesis approaches generally assume that bisimulation holds, which requires the discrete transition system to behave the same as the underlying continuous system with respect to the LTL specification. Controllers are also required in order to implement the transitions of the automaton synthesized from the LTL specification and the discrete abstraction. A challenging problem in controller synthesis is the design of controllers which can implement the automaton transitions for high-dimensional systems with nonlinear dynamics [15,21]. In certain cases, specifically when the differential equations of motions correspond to a smooth continuous vector field, reachable tubes and sequential controller compositions can be used to implement the automaton transitions [19]. When constrained reachability problems can be solved for the system with nonlinear dynamics, e.g., by means of sampling-based motion planning or reachable sets, the work in [84] provides a framework that continually refines the discrete abstraction until a control policy is found that is compatible with the LTL specification.
Coupling of discrete planning and sampling-based motion planning
Another line of research has focused on motion planning with LTL specifications for high-dimensional robotic systems with nonlinear dynamics. This research treats the combined task- and motion-planning problem as probabilistic search over a hybrid space consisting of discrete and continuous components [6,7,56,57,63,66,80]. The continuous layer is defined by the underlying state space, input controls and robot dynamics. Drawing from the success of sampling-based motion planning, the continuous layer uses a motion tree
The key aspect is the coupling of sampling-based motion planning to handle the complexity arising from high-dimensional robotic systems, nonlinear dynamics and collision avoidance with discrete search to handle discrete abstractions and LTL specifications. Figure 4 provides a schematic illustration. Note that the search can progress much more rapidly in the discrete layer, since it uses a simpler, discrete abstraction. This means that the framework can afford to do more exploration in the discrete layer and then use the results of the discrete search to guide the search in the continuous layer. Conceptually, the role of the discrete layer is to suggest to the continuous layer feasible directions in the form of discrete states along which to expand the motion tree. The continuous layer then, as it expands the motion tree along the suggested directions, analyzes the progress that it makes, and feeds back valuable information to the discrete layer so that it can further improve its search. As a result, the discrete layer could suggest to the continuous layer a different direction for expanding the motion tree in the next iteration. By receiving increasingly feasible directions to guide the expansion, the continuous layer can make additional progress, and eventually the framework will generate a collision-free and dynamically-feasible trajectory that satisfies the task specification.

Synergistic coupling of sampling-based motion planning and discrete search for the combined task- and motion-planning problem with LTL specifications and nonlinear dynamics. (Colors are visible in the online version of the article;
An issue that arises relates to the feasibility of the discrete plans. It is important to note that not every discrete plan is feasible. In some cases, due to the robot dynamics and interactions with the environment, it may not be possible to expand the motion tree
During discrete planning, the feasibility estimates, should be used to select more frequently plans that are deemed highly feasible. This provides the greedy component to the search, by guiding it along directions that are estimated to lead to a solution. To balance greedy with methodical search, less feasible plans should not be completely ignored, but should be selected less frequently. This is particularly relevant in the early stages of the search, where not enough information has been collected to properly evaluate the feasibility of the discrete plans. It is also crucial for the theoretical analysis to ensure probabilistic completeness.
Integration spectrum
The coupling of discrete planning and sampling-based motion planning opens up a wide spectrum of integration possibilities.
Complete plans: At one end of the spectrum, discrete planning can compute an entire discrete sequence
Partial plans: At the other end of the spectrum, discrete planning can compute just a single discrete state
Adjusting the length of the discrete plan based on exploration information: It may also be beneficial to dynamically adjust the length of the discrete plan based on the progress being made. Initially, preference could be given to short sequences to favor exploration over exploitation. As the tree is expanded, the framework can be more confident about its internal estimates, and so it can gradually increase the length of discrete sequences to allow for complete plans.
Criteria on where to be in the above spectrum can be useful in improving the overall performance. Finding the right balance in the above spectrum will depend on the nature of the application as well as the information gathered from the overall search and exploration.
Tradeoffs
This line of research, which couples discrete search with sampling-based motion planning, is capable of taking into account high-dimensional systems and nonlinear dynamics. It, however, places some restrictions on the LTL specifications. In particular, it supports only syntactically co-safe LTL formulas, which use ¬, ∨, ∧, ◯, ♢, ⊔ but not □ when written in positive-normal form (¬ appears only in front of atomic propositions) [73]. Syntactically co-safe LTL can be interpreted over finite discrete traces, which is necessary when planning finite motion trajectories. This provides a tradeoff with controller-synthesis approaches which can handle a broader fragment of LTL but require bisimulation and the availability of controllers to implement the automaton transitions.
Theoretical foundations of sampling-based algorithms for joint task and motion planning
Sampling-based approaches often relax the completeness guarantees to probabilistic or resolution completeness. Similarly, rather than optimality, they provide guarantees on convergence towards optimal solutions. Computational complexity results often relate to the “visibility” of the free space, or they can be analyzed with the help of convergence rates. Along with these, other directions for theoretical analysis emerge in combined task- and motion-planning problems with temporal logic specifications. For example, how expressive and succinct is the task-specification language? How do the expressiveness properties of the specification language relate to the various performance measures for the algorithm, such as completeness, asymptotic optimality, convergence rate and computational complexity? This section discusses these issues and highlights some open problems.
Expressiveness of temporal logic
First important question is concerned with the expressive power of the task-specification language. What exactly is the expressive power of different languages? For example, can LTL describe all possible motion-planning problems? How restricted is co-safe LTL?
Consider first determining the most expressive language for motion planning. Note that our objective is to find a motion that satisfies the specification. Hence, the specification language is linear time [67], since it describes a single motion rather than a branching-time property [23], such as those that describe all motions of a dynamical system. Hence, ideally the specification language should be able to describe all linear-time properties. Unfortunately, LTL is not sufficient as it cannot describe certain linear-time properties [23,67].
Fortunately, there are other languages that can describe all linear-time properties. One such language is the set of all ω-regular specifications, which is equivalent to the set of nondeterministic Büchi automata [77]. On the other hand, LTL is equivalent to the set of all deterministic Büchi automata [67]. However, non-deterministic Büchi automata are strictly more expressive than their deterministic version, which makes LTL weaker than the set of all ω-regular languages.
Another widely-studied language is μ-calculus [18,24], which is often used to analyze the expressive power of various temporal logics. It turns out that the deterministic fragment of μ-calculus is equivalent to the set of all ω-regular languages. Hence, if one were to design an efficient sampling-based algorithm for planning problems with μ-calculus, nondeterministic Büchi automata, or ω-regular specifications, it would be powerful enough to answer any problem instance described by a linear-time specification.
Second, it is possible that the most expressive languages lead to conceptually and computationally complex algorithms. In fact, this task can be analytically fairly challenging. Hence, there is value in considering subsets of linear-time specifications that may lead to simpler, more efficient algorithms. An important class of tasks are those that do not include a persistent component, that is, those specifications which describe tasks that terminate. The set of such specifications are described by the co-safe fragment of LTL [73].
Third, the incorporation of timed specifications still remains largely open. How can we specify a constraint of the form: “reach the goal region within the next 5 minutes”? Fortunately, there are temporal logics that can describe such specifications. For example, the metric temporal logic (MTL) [42] extends LTL with time intervals. As an illustration,
Finally, how can uncertainty and adversaries be included in the specification? For example, the probabilistic temporal logic (PTL) [30] provides the necessary operators to describe chance constraints on specifications. It is possible to specify that a proposition will eventually hold, with at least 95% probability. In this context, controller synthesis has been used to account for specifications given as a formula in probabilistic computation tree logic (PCTL) [49].
It is crucial that all these languages are explored in the context of robot motion planning. This endeavor will allow us to understand the added conceptual and computational complexity in the algorithms as the expressive power of the language increases.
Systems with non-trivial differential constraints
Designing planning algorithms for systems with non-trivial differential constraints has long been a challenge in motion planning [15,17,21,50]. Research has shown that PRM approaches have had limited applicability in motion planning with non-trivial differential constraints since each roadmap edge
Thus, it is reasonable to expect that similar challenges arise also when integrating task and motion planning. In fact, these challenges may have certain implications on the class of specification languages that the algorithmic approach can accommodate. For instance, designing sampling-based algorithms that can handle all linear-time specifications may be limited to exact steering functions, since the persistent motion may need to include a loop [18]. However, focusing on, for example, the co-safe fragment of LTL, may alleviate some of these problems and allow the algorithmic approach to handle a large class of dynamical systems.
Computational complexity, probabilistic completeness and asymptotic optimality
Many robotic problems involve online settings, where the environment is not fully known a priori, but it is discovered on the fly. Furthermore, the environment is often dynamic as there could be moving objects in addition to static obstacles. While taking into account these requirements, the algorithms must also be amenable to real-time computation.
It is for these reasons that sampling-based algorithms often incrementally expand a motion tree. In this way, the motion tree can be adapted to online settings and dynamic environments. Sampling-based algorithms for joint task and motion planning embody these properties. In fact, when a new vertex v is added to the motion tree, the motion trajectory

Incremental generation of a discrete abstraction. (Colors are visible in the online version of the article;
The theoretical properties of sampling-based approaches for joint task and motion planning are motivated with these issues in mind. We describe these theoretical properties in this section.
First, the completeness requirements are often tied to the number or the density of the samples. For example, the randomized algorithms guarantee probabilistic completeness. For algorithms that employ deterministic approaches, resolution completeness properties can be formulated in a similar manner.
Second, some algorithms may improve their solutions, for example, with respect to a cost function, if they are allowed more samples, for instance, guaranteeing asymptotic optimality, i.e., almost-sure convergence towards optimal solutions.
Finally, the proposed algorithms should be analyzed in terms of computational complexity. Since incremental algorithms do not necessarily terminate, their analysis requires, for instance, computing the expected time until termination, when the algorithm terminates. For algorithms that converge to optimal solutions, convergence rates provide the best estimate regarding the computational complexity of the algorithms.
On the one hand, it has been shown that probabilistically-complete sampling-based algorithms can be extended to handle all linear-time specifications [34], even guaranteeing asymptotic optimality [36]. Surprisingly, these extensions can be established without incurring too much computational overhead when compared to popular sampling-based algorithms for motion planning, such as PRM and RRT [34,36]. However, this approach is, unfortunately, limited to dynamical systems that admit an exact steering function.
On the other hand, sampling-based algorithms that can handle a large class of dynamical systems with co-safe LTL specifications have been developed [6,7,60,63,64], as discussed in Section 5.
Despite these advances, very little has been achieving in developing the theoretical foundations of the sampling-based approach for joint task and motion planning with temporal logic specifications. Progress must be made in understanding the trade-offs between three directions: (i) expressive power of specification languages, (ii) geometric/differential complexity of the underlying dynamics and (iii) the formal theoretical guarantees on probabilistic/resolution completeness, asymptotic optimality and computational complexity.
Robust replanning to adapt to changing environmental and contextual conditions
Even when dynamics and obstacles are taken into account during planning, it is still expected that, at certain times, the robot may diverge or fail to follow the planned motions due to the intricacies of the physical world, uncertainty in the motion outcomes, incomplete maps or changes in the environment. The need for a new plan also arises in response to locally-sensed events, such as avoiding unanticipated obstacles or exploring surrounding areas when detecting an object of interest. To adapt to changing environmental and contextual conditions, it becomes important to complement reactive behaviors to avoid immediate dangers with replanning to ensure completion of the task. In this context, several challenges arise such as deciding when and how to modify the current plan, integrating the sensory information into the current world models, and using prior plans to improve future plans.
Prior motion trees can also be beneficial in improving replanning. In particular, deviation from the planned motions during execution only invalidates certain parts of the motion tree. The rest can serve as a reliable guide for future expansions. This can reduce the running time needed for replanning as large parts of previous computations can be reused. This is akin to anytime search methods in AI, which often gain computational efficiency by locally repairing the plan when faced with new obstacles [1,41]. Sampling-based motion planners have also been used in replanning [4,27,37]. Building on this body of work, the expectation is that replanning can provide the necessary robustness to execute the planned motions in the physical world while responding to locally-sensed events.
Conclusion
The integrated task- and motion-planning problem requires integrative approaches that bring together techniques from robotics and AI. While progress has been made, numerous challenges lie ahead in order to ensure continued progress toward increasing the ability of robots to act on their own. Controller-synthesis approaches, coupling of discrete search and sampling-based motion planning, and replanning provide promising research directions. Building on this body of work, significant progress can be made by novel integrative approaches that address planning in a general setting taking into account tasks given in a discrete logic as well as high-dimensional continuous state spaces, nonlinear motion dynamics, general geometries and physics-based interactions. Progress along these directions promises to address fundamental issues and establish a unified paradigm for planning in a general discrete and continuous setting that bridges the gap between AI and robotics. We expect to obtain a better understanding of key components in discrete planning and motion planning, and particularly in their interplay. At the theoretical level, we expect formal guarantees on the algorithmic correctness and efficiency of the approaches, particularly focusing on probabilistic completeness and optimality.
Footnotes
Acknowledgements
The work of E. Plaku was supported by NSF IIS-1449505. The work of S. Karaman was supported by NSF CAREER CNS-1350685.
