提出高效路径规划算法，让机器人在可移动障碍物中快速找到最优路径。
Search-Based Path Planning in Interactive Environments among Movable Obstacles
- 基于启发式搜索，只探索关键状态空间，大幅提升效率。
- 在含400个物体的复杂地图中，1秒内找到最优解。
- 适用于需要与物体互动的交互式环境，如仓库搬运、家庭服务机器人。
本文研究可移动障碍物中的路径规划（PAMO），目标是在静态障碍物间寻找无碰撞的最小代价路径，同时允许机器人在必要时推动可移动物体。由于需同时搜索机器人和物体的位置状态空间，该问题状态空间呈指数增长。本文提出一种新思路：仅需搜索由启发式引导的部分状态空间，且远离机器人的物体基本保持原位，从而实现高效求解。基于此，本文提出两种PAMO形式化问题——双目标与资源约束，在占用栅格中构建并求解。进一步提出具有完备性与最优性保证的PAMO*算法，并扩展至连续空间的混合状态版本PAMO*，支持高保真交互。实验表明，PAMO*可在含400个物体的密集环境中于1秒内找到最优解。
原文摘要 · Abstract (English)
This paper investigates Path planning Among Movable Obstacles (PAMO), which seeks a minimum cost collision-free path among static obstacles from start to goal while allowing the robot to push away movable obstacles (i.e., objects) along its path when needed. To develop planners that are complete and optimal for PAMO, the planner has to search a giant state space involving both the location of the robot as well as the locations of the objects, which grows exponentially with respect to the number of objects. This paper leverages a simple yet under-explored idea that, only a small fraction of this giant state space needs to be searched during planning as guided by a heuristic, and most of the objects far away from the robot are intact, which thus leads to runtime efficient algorithms. Based on this idea, this paper introduces two PAMO formulations, i.e., bi-objective and resource constrained problems in an occupancy grid, and develops PAMO*, a planning method with completeness and solution optimality guarantees, to solve the two problems. We then further extend PAMO* to hybrid-state PAMO* to plan in continuous spaces with high-fidelity interaction between the robot and the objects. Our results show that, PAMO* can often find optimal solutions within a second in cluttered maps with up to 400 objects.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。