IEEE Robotics & Automation Magazine - September 2018 - 62

whereas typical motion planners assume a fixed configuration
space. Thus, we cannot expect to combine existing tools for
isolated task planning and motion planning and produce
frameworks that can consistently use high-level specifications
of behavior to produce motion. Instead, we must handle the
possible interactions of discrete and continuous components
to identify task plans and executable motions.
TM Kit (TMKit) is an end-to-end system for probabilistically complete TMP and real-time execution. [Code and doc-

(a)

umentation are available at [21] under a permissive (BSD)
license.] TMKit follows the high-level design shown in Figure 2
to implement the algorithm of [1] and [2] and at the same
time provides a general framework to integrate multiple
methods for task planning, motion planning, and TM interaction. Shared abstractions and data structures are fundamental aspects of TMKit that enable the coupling of task
planning, motion planning, and real-time estimation and
control. TMKit is modular and extensible, and we are adapting it to additional methods for TMP [3], [4]. Whenever
appropriate, we employ widely used formats and protocols to
promote compatibility. The resulting system generates realtime, collision-free robot motion from high-level specifications. To our knowledge, this is the first publicly available,
general-purpose TMP framework. Sharing this project with
the community will encourage the implementation of more
TMP approaches and provide a valuable tool for the development and comparison of related techniques.
Background

(c)

(b)

Figure 1. An example of a TMP problem: setting a table. The
input for the TMP includes (a) the start state, (b) the goal state,
and a set of allowable actions (e.g., pick, place, and so on). (c)
TMP finds the output, which consists of a sequence of discrete
actions (the task plan) and their corresponding continuous paths
(or motion plans).

Visualization

TM Planner
Candidate Task Actions

Task Domain
Domain Semantics

Task
Planner

Goal Scene
Start Environment

Task Planning
Task planning identifies a sequence of discrete actions that
change an initial state into a desired goal state or condition,
given a task domain that defines the available actions and
their preconditions and effects. This field evolved largely from
pioneering work on the Stanford Research Institute Planning
System [5]. The leading approaches for efficient task planning
are heuristic search [6] and constraint satisfaction [7].
Off-the-shelf task planners typically focus on efficiently
finding a single plan. In contrast, TMP often requires searching through multiple alternative task plans, as previously
discussed. This raises an inherent challenge: motion planners
that are used to compute paths are, at best, probabilistically
complete for high-dimensional systems. Consequently, we
cannot generally prove the nonexistence of corresponding
motion plans. To address this challenge, our system does not
use an off-the-shelf task planner but rather employs a newly
introduced task planner capable of efficiently generating alternative plans.

Motion
Planner

TM Plan

TM Control

Robot

q˜

Additional Constraints

∪

Robot Geometry

Figure 2. A high-level planning and execution block diagram. The inputs are the task domain definition; the environment and robot
geometries, combined to produce the scene graph; and the domain semantics that relate the task and motion layers. The TM planner
generates a plan based on these inputs. The TM control layer executes the plan, sharing a geometric representation-the scene
graph-with the planning layer. The control output u drives the robot, resulting in configuration q. In a parallel layer, we visualize the
system at simulated configuration qu .

IEEE ROBOTICS & AUTOMATION MAGAZINE

september 2018

IEEE Robotics & Automation Magazine - September 2018

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