Heuristic search for manipulation planning

Manipulation problems involving many objects present substantial challenges for planning algorithms due to the high dimensionality and multi-modality of the search space. Symbolic task planners can efficiently construct plans involving many entities but cannot incorporate the constraints from geometry and kinematics. Existing approaches to integrated task and motion planning as well as manipulation planning remain prohibitively slow to plan in these high-dimensional hybrid configuration spaces involving many objects. We present the FFRoB algorithm for task and motion planning and the hybrid heuristic backward-forward (HHBF) planning algorithm for general manipulation planning. Both algorithms adapt heuristic ideas from one of the most successful symbolic planners in recent years, the FastForward (FF) planner, to continuous robotic planning domains. FFRoB discretizes task and motion planning problems using a multi-query roadmap structure that can be conditionalized to model different placements of movable objects. This structure enables the planner to efficiently compute the FFRoB heuristic which incorporates geometric and kinematic planning constraints to give a tight estimate of the distance to the goal. The resulting tightly integrated planner is simple and performs efficiently in a collection of tasks involving manipulation of many objects. HHBF generalizes this idea to planning with arbitrary manipulation primitives. It dynamically searches forward from the initial state towards the goal but uses a backward search from the goal, based on a simplified representation of the actions, to bias the sampling of the infinite action space towards action that are likely to be useful in reaching the goal. As a result, it can construct long manipulation plans in a large class of manipulation domains even more effectively than FFRoB. For both algorithms, we empirically demonstrate their effectiveness on complex manipulation tasks.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2015

Author dc:creator

• Garrett, Caelan Reed

Advisor dc:contributor.advisor

• Tomás Lozano-Pérez and Leslie Pack Kaelbling.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/100596

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/100596