Combining Task and Motion Planning

• This thesis addresses the problem of automatically computing, given a high-level goal description, a sequence of actions and motion paths for one or several robots to achieve that goal. Also referred to as CTAMP (Combining Task And Motion Planning), this problem may seem trivial at first glance, since efficient solutions have been found for its two underlying problems, namely task planning and motion planning. However, further consideration reveals that combining task and motion planning, in many cases, is not straightforward. We have identified two important issues which are addressed in this thesis.The first issue originates in the fact that symbolic actions can be geometrically instantiated in multiple ways. Choosing a geometric instance for each action is not trivial, because a “wrong” choice may compromise the feasibility of subsequent actions. To address this issue, in the first part of the thesis we propose a mechanism for backtracking over geometric choices in the context of a partial symbolic plan. This process may greatly increase the complexity of CTAMP. Therefore, we also present a constraint-based approach for pruning out geometric configurations which violate a number of geometric constraints imposed by the action sequence, and by the kinematic models of robots. This approach has been tested with success on the real humanoid robotic platform Justin in the context of the GeRT1 project.The second issue results from the necessity to interleave symbolic and geometric computations for taking geometric constraints into account at the symbolic level. Indeed, the symbolic search space forms an abstraction of the physical world, hence geometric constraints such as objects occlusions or kinematic constraints are not represented. However, interleaving both search processes is not a workable approach for large problem instances, because the resulting search space is too large. In the second part of the thesis, we propose a novel approach for decoupling symbolic and geometric search spaces, while keeping the symbolic level aware of geometric constraints. Culprit detection mechanisms are used for computing explanations for geometric failures, and these explanations are leveraged at the symbolic level for pruning the search space through inference mechanisms. This approach has been extensively tested in simulation, on different types of single and multiple robot systems.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Nyckelord

Datavetenskap

Computer Science

Publikations- och innehållstyp

vet (ämneskategori)

dok (ämneskategori)