IEEE Robotics & Automation Magazine - September 2018 - 63

Motion Planning
Motion planning identifies a continuous path of valid configurations, i.e., joint positions, from an initial state to a desired
goal state. Sampling-based motion planners are widely used
for high-dimensional systems [8]. Such sampling-based planners offer probabilistic completeness, guaranteeing that the
planner will eventually find a solution if one exists. However,
if a solution does not exist, a sampling-based planner cannot
prove this negative; in such a case, the planner would not terminate or would run until reaching a timeout. Motion planners based on gradient descent or optimization are also
common and highly efficient, but they do not offer the same
probabilistic completeness guarantees as the sampling-based
motion planners. Consequently, this work uses such sampling-based planners because probabilistic completeness of
the overall framework is a desired property. Conveniently,
high-quality, open-source implementations of such planners
are available [9]. Future integration of alternative motion
planning approaches is possible, with their accompanying set
of tradeoffs, but the integration of motion planners in TMP
needs special attention to address the coupling of task planning and motion planning.
Off-the-shelf motion planning frameworks often abstract
the details of robot kinematics or assume that the kinematic
equations are fixed or change infrequently, with only configurations changing during planning [9]. In contrast, TMP
requires rapid updates to kinematic equations. As the robot
grasps and transfers objects, these objects' poses change
between fixed values and functions of robot configuration.
Moreover, these changes may involve more than just the individual grasped object, such as in the case of moving a tray or
pushing a cart containing other objects. Consequently, kinematic representations capable of efficient updates are required
for TMP.
Combining Task and Motion Planning
TMP takes an initial state to a desired goal state through the
concurrent or interleaved production of high-level, discrete
action sequences via task planning and continuous, collisionfree paths via motion planning. Most prior work on TMP has
focused on computational performance rather than completeness or generality, which are emphasized in this article.
Lagriffoul and Andres [10] applied geometric constraints to
limit the motion planning space or prove motion to be infeasible in special cases. Hierarchical Planning in the Now [11]
interleaved planning and execution, reducing search depth
but requiring reversible actions, e.g., rearranging objects but
not pouring a cup down a drain, when backtracking. The
work in [12] extends a hierarchical task planner with geometric primitives, using shared literals that relate task-level symbols with motion-level geometric entities. Gharbi et al. [13]
interfaced an off-the-shelf task planner and motion planning
using a heuristic method to remove objects that would potentially block the robot's path. The researchers in [14] formulated the motion side of TMP as a constraint satisfaction
problem over a discretized, preprocessed subset of the config-

uration space. The Robosynth framework [15] uses a satisfiability modulo theories (SMTs) solver to generate task and
motion plans from a static road map, employing plan outlines
to guide the planning process. FFRob [16] developed a tasklayer heuristic similar to the Fast-Forward planner [6] by
using a lazily-expanded road map. Overall, these methods set
aside the broad challenge of ensuring probabilistic completeness that arises from interactions between the task and
motion layers. In contrast, the framework we implement
focuses on probabilistically complete TMP.
A smaller number of task and motion planners do achieve
probabilistic completeness. The aSyMov planner [17] combines a heuristic-search task planner with lazily expanded
road maps. Our implementation of [1] and [2] in TMKit
operates differently at the task, motion, and interface levels,
yielding different performance characteristics than aSyMov.
For example, aSyMov's composed road maps could be amortized over multiple runs, but composing road maps for object
interactions may be expensive. In contrast, [1] and [2] find a
new motion plan each run but efficiently update scene data
structures to handle object interaction. Furthermore, TMKit
is extensible to both forward-search [6] and constraint-based
[7] task planners.
While source code is available for some specific methods,
such as that in [13], we believe TMKit is the first publicly
available framework that is extensible to multiple methods
and domains. A key to this extensibility is our abstraction of
the interaction between task and motion layers via the
domain semantics, which enables the introduction of new
actions and domains without any necessary changes to the
framework itself.
Plan Execution
Motion planners make certain assumptions to achieve sufficient performance, and the execution step must correct those
assumptions in real time. Specifically, motion planners typically assume 1) a given model for the kinematics and geometry of the robot and environment and 2) that motion between
nearby joint configurations is possible. In reality, geometric
models contain numerous errors due to imprecise lengths,
encoder calibration error, flexing of assumedly rigid bodies,
inaccurate object detection, inaccurate camera calibration,
and so forth. Thus, despite the precision or repeatability of
many robots, accurate motion to correct poses still presents
challenges. In addition, robot motion is subject to dynamic
constraints on such variables as velocity, force, and current.
The execution step must track the planned path in a way that
is physically feasible, and it must correct for the inevitable and
sundry errors.
Input to TMP
The input to TMP includes the discrete task domain, the continuous motion domain, and the coupling of these two sides.
Task domain: The task domain defines the discrete actions
the robot can take, including their preconditions and effects.
For example, the pick-up action may have a precondition
september 2018

IEEE ROBOTICS & AUTOMATION MAGAZINE

IEEE Robotics & Automation Magazine - September 2018

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - September 2018