Combined Task and Motion Planning via Sketch Decompositions

Authors

  • Magí Dalmau Moreno Eurecat, Centre Tecnològic de Catalunya, Spain Universitat Pompeu Fabra, Barcelona, Spain
  • Néstor García Eurecat, Centre Tecnològic de Catalunya, Spain
  • Vicenç Gómez Universitat Pompeu Fabra, Barcelona, Spain
  • Héctor Geffner RWTH Aachen University, Germany Linköping University, Linköping, Sweden

DOI:

https://doi.org/10.1609/icaps.v34i1.31468

Abstract

The challenge in combined task and motion planning (TAMP) is the effective integration of a search over a combinatorial space, usually carried out by a task planner, and a search over a continuous configuration space, carried out by a motion planner. Using motion planners for testing the feasibility of task plans and filling out the details is not effective because it makes the geometrical constraints play a passive role. This work introduces a new interleaved approach for integrating the two dimensions of TAMP that makes use of sketches, a recent simple but powerful language for expressing the decomposition of problems into subproblems. A sketch has width 1 if it decomposes the problem into subproblems that can be solved greedily in linear time. In the paper, a general sketch is introduced for several classes of TAMP problems which has width 1 under suitable assumptions. While sketch decompositions have been developed for classical planning, they offer two important benefits in the context of TAMP. First, when a task plan is found to be unfeasible due to the geometric constraints, the combinatorial search resumes in a specific subproblem. Second, the sampling of object configurations is not done once, globally, at the start of the search, but locally, at the start of each subproblem. Optimizations of this basic setting are also considered and experimental results over existing and new pick-and-place benchmarks are reported.

Downloads

Published

2024-05-30

How to Cite

Dalmau Moreno, M., García, N., Gómez, V., & Geffner, H. (2024). Combined Task and Motion Planning via Sketch Decompositions. Proceedings of the International Conference on Automated Planning and Scheduling, 34(1), 123-132. https://doi.org/10.1609/icaps.v34i1.31468