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 sub-problem. 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.
Abstract (translated)
TAMP（任务和动作规划）中的挑战在于在搜索解空间和组合空间中实现有效整合，通常由任务规划器完成。而搜索解空间由运动规划器完成。使用运动规划器来测试任务计划的可行性并填充细节，由于使几何约束处于被动角色，因此效果不佳。 本工作提出了一种新的并行方法整合TAMP的这两个维度，该方法利用图素，这是一种最近简单而强大的语言，用于将问题分解为子问题。如果一个图素分解问题可以在线性时间内以贪心方式求解，则具有宽度为1。在论文中，针对多个TAMP问题类，引入了一个总图素，具有宽度为1的条件。 虽然针对经典规划的图素分解已经得到了开发，但在TAMP的背景下它们提供了两个重要的优势。首先，当由于几何约束，任务计划不可行时，组合搜索会在特定子问题中重新启动。其次，在搜索的每个子问题开始时，不是全局地采样对象配置，而是局部地采样。还考虑了这种基本设置的优化，并报告了现有和新的捡选基准的实验结果。
URL
https://arxiv.org/abs/2403.16277
