机器人规划中如何分配计算资源以按时完成任务
Effort Allocation for Deadline-Aware Task and Motion Planning: A Metareasoning Approach
- 用元推理方法建模计算资源分配，将问题转化为马尔可夫决策过程
- 提出DP_Rerun算法，在保证时效性前提下性能接近蒙特卡洛树搜索
- 适合需在严格时限内完成复杂任务的机器人系统设计
在机器人规划中，任务常可通过多种路径实现，每条路径由多个动作组成。本文针对任务与运动规划中的截止时间约束，旨在找到一种即使在规划与执行时间不确定的情况下仍能在截止时间内完成的方案。为此，提出一个努力分配问题，将其形式化为马尔可夫决策过程（MDP），通过元推理视角在各选项间分配计算资源。我们通过从背包问题归约，正式证明该问题为NP难。探索了基于模型的方法（利用历史经验学习转移模型）和无模型方法（通过强化学习克服先验数据缺失）。针对基于模型的方法，研究使用蒙特卡洛树搜索（MCTS）近似求解所提MDP，进一步设计启发式策略以应对NP难问题，提出近似且高效的算法DP_Rerun。实验表明，DP_Rerun在性能上媲美MCTS，同时计算开销可忽略不计。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。