A Task and Motion Planning Framework Using Iteratively Deepened AND/OR Graph Networks

📄 arXiv: 2503.07700v1 📥 PDF

作者: Hossein Karami, Antony Thomas, Fulvio Mastrogiovanni

分类: cs.RO, cs.AI

发布日期: 2025-03-10

期刊: Robotics and Autonomous Systems, Volume 189, July 2025, 104943

💡 一句话要点

提出一种基于迭代加深的AND/OR图网络的任务与运动规划框架，解决子任务数量未知的TAMP问题。

🎯 匹配领域: 支柱一：机器人控制 (Robot Control) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 任务与运动规划 AND/OR图网络 迭代加深搜索 多机器人协作 机器人任务分配

📋 核心要点

  1. 传统任务与运动规划器难以处理子任务数量事先未知的复杂场景，例如在杂乱环境中抓取物体。
  2. 论文提出一种迭代加深的AND/OR图网络，在运行时动态扩展图结构，直至找到可行的抓取方案。
  3. 实验在单机器人和多机器人场景下验证了该方法的有效性，并展示了其在不同机器人平台上的可扩展性。

📝 摘要（中文）

本文提出了一种基于AND/OR图网络的集成任务与运动规划方法，用于表示任务级状态和动作，并利用它来解决不同类型的任务与运动规划问题(TAMP)。许多TAMP问题并没有预先确定的子任务数量来实现目标。例如，从杂乱的工作空间中检索目标对象时，原则上，最终抓取它所需的物体重新排列的数量是无法预先知道的。为了应对这一挑战，与传统的规划器（包括基于AND/OR图的规划器）不同，我们通过逐步添加子图来在运行时扩展AND/OR图，直到抓取目标对象变得可行，从而产生一个AND/OR图网络。该方法被扩展到支持多机器人任务与运动规划，并且(i)允许我们在协调给定数量的机器人的活动时执行任务分配，并且(ii)可以处理涉及先验未知数量的子任务的多机器人任务。该方法在仿真和真实的双臂机器人机械臂（即Rethink Robotics的Baxter）上进行了评估和验证。特别是，对于单机器人任务与运动规划，我们在三个不同的TAMP领域验证了我们的方法。此外，我们还使用三种不同的机器人进行仿真，即Baxter、Franka Emika Panda机械臂和PR2机器人。实验表明，我们的方法可以很容易地扩展到具有许多对象和机器人的场景，并且能够处理不同类型的TAMP问题。

🔬 方法详解

问题定义：论文旨在解决任务与运动规划（TAMP）中，子任务数量事先未知的问题。例如，在杂乱环境中抓取目标物体，需要移动多少个障碍物才能成功抓取，这是无法预先确定的。传统TAMP方法通常需要预先定义好所有子任务，因此难以应对此类动态变化的场景。

核心思路：论文的核心思路是使用迭代加深的AND/OR图网络。该网络在运行时动态扩展，逐步探索可能的子任务序列，直到找到一个可行的解决方案。这种动态扩展的方式避免了预先枚举所有可能的子任务组合，从而提高了规划效率。

技术框架：整体框架包含以下几个关键步骤：1) 初始化AND/OR图；2) 迭代扩展图结构，每次扩展都增加新的子任务节点；3) 使用搜索算法（如A*）在AND/OR图中寻找最优路径，该路径代表一个可行的任务序列；4) 如果找到可行路径，则执行该路径；否则，继续扩展图结构。对于多机器人场景，框架还包括任务分配和协调模块。

关键创新：最重要的创新点在于动态扩展的AND/OR图网络。与传统的静态AND/OR图相比，该网络能够根据实际情况动态调整结构，从而更好地适应子任务数量未知的场景。此外，该方法还支持多机器人任务分配和协调，进一步扩展了其应用范围。

关键设计：AND/OR图的节点表示任务状态，边表示任务动作。扩展图结构时，需要定义哪些动作是可行的，以及执行这些动作后状态如何变化。论文中使用了启发式函数来指导图的扩展方向，从而提高搜索效率。对于多机器人场景，需要设计合适的任务分配策略，以平衡各个机器人的负载，并避免冲突。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

论文在仿真和真实机器人平台上进行了实验验证。在单机器人场景下，该方法在三个不同的TAMP领域取得了成功。在多机器人场景下，该方法能够有效地进行任务分配和协调。实验结果表明，该方法具有良好的可扩展性，能够处理具有大量对象和机器人的复杂场景。具体性能数据和对比基线在论文中有详细描述。

🎯 应用场景

该研究成果可应用于各种需要自主任务规划的机器人应用场景，例如：智能仓储、家庭服务机器人、工业自动化等。特别是在环境复杂、任务目标不确定的情况下，该方法能够显著提高机器人的自主性和适应性。未来，该方法有望与深度学习等技术结合，实现更智能、更高效的任务规划。

📄 摘要（原文）

In this paper, we present an approach for integrated task and motion planning based on an AND/OR graph network, which is used to represent task-level states and actions, and we leverage it to implement different classes of task and motion planning problems (TAMP). Several problems that fall under task and motion planning do not have a predetermined number of sub-tasks to achieve a goal. For example, while retrieving a target object from a cluttered workspace, in principle the number of object re-arrangements required to finally grasp it cannot be known ahead of time. To address this challenge, and in contrast to traditional planners, also those based on AND/OR graphs, we grow the AND/OR graph at run-time by progressively adding sub-graphs until grasping the target object becomes feasible, which yields a network of AND/OR graphs. The approach is extended to enable multi-robot task and motion planning, and (i) it allows us to perform task allocation while coordinating the activity of a given number of robots, and (ii) can handle multi-robot tasks involving an a priori unknown number of sub-tasks. The approach is evaluated and validated both in simulation and with a real dual-arm robot manipulator, that is, Baxter from Rethink Robotics. In particular, for the single-robot task and motion planning, we validated our approach in three different TAMP domains. Furthermore, we also use three different robots for simulation, namely, Baxter, Franka Emika Panda manipulators, and a PR2 robot. Experiments show that our approach can be readily scaled to scenarios with many objects and robots, and is capable of handling different classes of TAMP problems.