I. Introduction
Robotic devices often need to perform tasks that involve the execution of multiple actions. For example, opening a door may mean moving to the door, pressing the handle and then pushing the door. Executing such sequences of actions implies that robots need to plan at two levels: (1) the task planning level, where sequences of actions that take the robot to its goal are computed (a topic often studied in the artificial intelligence community) and (2) the motion planning level, where individual motion plans that implement the actions selected at the task planning level are computed (a topic often studied in the robotics community [1], [2]). The feasibility of motion plans cannot always be quickly determined at task planning level, and thus decoupling of task planning from motion planning leads to infeasible solutions when motion plans cannot be computed for proposed task plans. As a result, recent approaches consider task planning and motion planning simultaneously (e.g., [3]–[11]). For the remainder of the paper we will refer to this problem as the simultaneous task and motion planning (STAMP) problem. The input to the STAMP problem is in the form of task graphs. These are directed acyclic graphs that represent possible sequences of actions that take the robot to the goal. A path in the task graph that connects the robot's initial state to a goal state represents a possible task plan. If every edge along the task plan has a motion plan associated to it such that the motion plans can be executed in sequence, a solution to the STAMP problem has been found [12].