FFRob: Leveraging symbolic planning for efficient task and motion planning
FFRob: Leveraging symbolic planning for efficient task and motion planning
复制标题
FFRob：利用符号规划实现高效的任务和运动规划
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
L. Kaelbling
中科院分区：
文献类型：
--
作者：
Caelan Reed Garrett;Tomas Lozano;L. Kaelbling
由于混合配置空间的高维性和多模态，涉及许多对象的移动操纵问题很难解决。执行纯粹几何搜索的规划器解决这些问题的速度非常慢，因为他们无法考虑配置空间。符号任务规划器可以有效地构建涉及许多变量的计划，但不能表示操作中所需的几何和运动学约束。我们提出了用于解决任务和运动规划问题的 FFRob 算法。首先，我们引入扩展动作规范（EAS）作为通用规划表示，支持任意谓词作为条件。我们采用现有的启发式搜索思想来解决带规划问题，特别是删除松弛，以解决 EAS 问题实例。然后，我们将 EAS 表示和规划器应用于导致 FFRob 的操纵问题。 FFRob 使用操作基元的批量采样和多查询路线图结构来迭代离散化任务和运动规划问题，该结构可以条件化以评估可移动对象不同放置下的可达性。这种结构使 EAS 规划器能够有效地计算包含几何和运动学规划约束的启发式算法，从而对到目标的距离进行严格估计。此外，我们证明 FFRob 在概率上是完整的，并且具有有限的预期运行时间。最后，我们凭经验证明了 FFRob 在复杂多样的任务和运动规划任务（包括可移动物体之间的重新排列规划和导航）上的有效性。
Mobile manipulation problems involving many objects are challenging to solve due to the high dimensionality and multi-modality of their hybrid configuration spaces. Planners that perform a purely geometric search are prohibitively slow for solving these problems because they are unable to factor the configuration space. Symbolic task planners can efficiently construct plans involving many variables but cannot represent the geometric and kinematic constraints required in manipulation. We present the FFRob algorithm for solving task and motion planning problems. First, we introduce extended action specification (EAS) as a general purpose planning representation that supports arbitrary predicates as conditions. We adapt existing heuristic search ideas for solving strips planning problems, particularly delete-relaxations, to solve EAS problem instances. We then apply the EAS representation and planners to manipulation problems resulting in FFRob. FFRob iteratively discretizes task and motion planning problems using batch sampling of manipulation primitives and a multi-query roadmap structure that can be conditionalized to evaluate reachability under different placements of movable objects. This structure enables the EAS planner to efficiently compute heuristics that incorporate geometric and kinematic planning constraints to give a tight estimate of the distance to the goal. Additionally, we show FFRob is probabilistically complete and has a finite expected runtime. Finally, we empirically demonstrate FFRob’s effectiveness on complex and diverse task and motion planning tasks including rearrangement planning and navigation among movable objects.
DOI：
--
发表时间：
2012
期刊：
--
影响因子：
--
作者：
Gregory, P
通讯作者：
Gregory, P