Effort Allocation for Deadline-Aware Task and Motion Planning: A Metareasoning Approach

📄 arXiv: 2410.05828v1 📥 PDF

作者: Yoonchang Sung, Shahaf S. Shperberg, Qi Wang, Peter Stone

分类: cs.RO

发布日期: 2024-10-08

备注: 48 pages, 6 figures

💡 一句话要点

针对截止时间约束的任务与运动规划，提出基于元推理的计算资源分配方法

🎯 匹配领域: 支柱一：机器人控制 (Robot Control) 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 任务与运动规划 截止时间约束 元推理 马尔可夫决策过程 蒙特卡洛树搜索

📋 核心要点

  1. 现有任务与运动规划方法难以在规划和执行时间不确定的情况下，保证在截止时间内完成任务。
  2. 论文提出将计算资源分配问题建模为MDP，利用元推理在不同方案中分配计算资源，以满足截止时间约束。
  3. 实验结果表明，提出的DP_Rerun算法在保证性能的同时，显著降低了计算时间，接近MCTS的性能。

📝 摘要（中文）

本文针对机器人规划中任务通常可以通过多种包含若干动作的选项来实现这一问题，特别关注任务与运动规划中的截止时间约束。目标是在不确定的规划和执行时间下，找到一个可以在截止时间内执行的方案。我们提出了一个努力分配问题，将其形式化为一个马尔可夫决策过程（MDP），通过利用元推理的视角在给定的选项中分配计算资源来找到这样的方案。我们通过从背包问题进行归约，正式证明了该问题的NP-hard性质。我们探索了两种方法：一种是基于模型的方法，其中转移模型从过去的经验中学习；另一种是无模型的方法，通过强化学习克服了无法获取先验数据的问题。对于基于模型的方法，我们研究了蒙特卡洛树搜索（MCTS）来近似解决所提出的MDP，并进一步设计了启发式方案来解决NP-hard问题，从而产生了近似但高效的算法DP_Rerun。实验表明，DP_Rerun表现出与MCTS相当的有希望的性能，同时只需要极少的计算时间。

🔬 方法详解

问题定义：论文旨在解决具有截止时间约束的任务与运动规划问题。在机器人规划中，一个任务通常有多种实现方式，每种方式包含不同的动作序列。由于规划和执行时间的不确定性，如何在截止时间内找到可行的方案是一个挑战。现有方法通常难以在不确定性下保证满足截止时间，或者计算复杂度过高。

核心思路：论文的核心思路是将计算资源分配问题建模为一个马尔可夫决策过程（MDP）。通过元推理，智能体可以学习如何在不同的规划选项中分配计算资源，以最大化在截止时间内完成任务的概率。这种方法允许智能体根据当前状态和可用时间，动态地调整规划策略。

技术框架：整体框架包括以下几个主要阶段：1) 任务分解：将高层任务分解为多个可选项，每个选项包含一系列动作。2) MDP建模：将努力分配问题建模为MDP，其中状态表示当前时间和已完成的任务，动作表示在不同选项上分配的计算资源。3) 求解MDP：使用基于模型的方法（MCTS和DP_Rerun）或无模型的方法（强化学习）来求解MDP，找到最优的资源分配策略。4) 方案执行：根据求解得到的策略，执行相应的动作序列。

关键创新：论文的关键创新在于将元推理应用于任务与运动规划中的资源分配问题，并将其形式化为MDP。通过这种方式，智能体可以学习如何在不确定性下有效地分配计算资源，以满足截止时间约束。DP_Rerun算法是另一个创新点，它通过启发式方法加速了MCTS的求解过程，显著降低了计算时间。

关键设计：DP_Rerun算法的关键设计在于其启发式策略，用于在MCTS的搜索过程中优先探索更有希望的节点。具体来说，该算法会根据当前状态和可用时间，估计每个选项的完成概率，并优先探索那些完成概率较高的选项。此外，论文还探索了不同的奖励函数，以鼓励智能体在截止时间内完成任务，并惩罚超时行为。对于强化学习方法，论文采用了常见的Q-learning算法，并设计了合适的探索策略，以平衡探索和利用。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，提出的DP_Rerun算法在性能上与MCTS相当，但计算时间显著降低。具体来说，DP_Rerun可以在极短的时间内找到近似最优的资源分配策略，使其在实际应用中更具优势。此外，实验还验证了基于模型和无模型方法的有效性，为不同的应用场景提供了选择。

🎯 应用场景

该研究成果可应用于各种需要在截止时间内完成任务的机器人应用场景，例如：自动驾驶、物流配送、应急救援等。在这些场景中，机器人需要在有限的时间内规划并执行一系列动作，以达到特定的目标。该方法可以帮助机器人更有效地利用计算资源，提高任务完成的成功率。

📄 摘要（原文）

In robot planning, tasks can often be achieved through multiple options, each consisting of several actions. This work specifically addresses deadline constraints in task and motion planning, aiming to find a plan that can be executed within the deadline despite uncertain planning and execution times. We propose an effort allocation problem, formulated as a Markov decision process (MDP), to find such a plan by leveraging metareasoning perspectives to allocate computational resources among the given options. We formally prove the NP-hardness of the problem by reducing it from the knapsack problem. Both a model-based approach, where transition models are learned from past experience, and a model-free approach, which overcomes the unavailability of prior data acquisition through reinforcement learning, are explored. For the model-based approach, we investigate Monte Carlo tree search (MCTS) to approximately solve the proposed MDP and further design heuristic schemes to tackle NP-hardness, leading to the approximate yet efficient algorithm called DP_Rerun. In experiments, DP_Rerun demonstrates promising performance comparable to MCTS while requiring negligible computation time.