用分阶段方法解决刚体在复杂环境中的路径规划难题。
Rigid Body Path Planning using Mixed-Integer Linear Programming
- 先构建无碰撞区域的凸多面体图，再分块求解小规模混合整数规划
- 在线查询时计算时间更短，且随环境尺寸和通道宽度增长表现更好
- 适合需要高效实时路径规划的机器人导航场景
在拥挤环境中导航刚体物体极具挑战性，尤其当存在狭窄通道时。现有基于采样的规划器和基于优化的方法（如混合整数线性规划，MILP）在工作空间规模或障碍物数量增加时扩展性受限。为此，我们提出一种三阶段算法：首先在无碰撞的工作空间中生成凸多面体图；其次针对多面体间求解大量小型MILP问题以生成可行路径；最后在线查询起始与目标配置时快速获得可行路径。该凸多面体图对自由空间进行分解，每个MILP子问题仅限于两到三个自由多面体范围内，从而限制决策变量数量。仿真结果表明，相比基线方法，本方法在线计算时间更短，在二维与三维环境下对环境大小和隧道宽度的扩展性均优于基于采样的规划器。
原文摘要 · Abstract (English)
Navigating rigid body objects through crowded environments can be challenging, especially when narrow passages are presented. Existing sampling-based planners and optimization-based methods like mixed integer linear programming (MILP) formulations, suffer from limited scalability with respect to either the size of the workspace or the number of obstacles. In order to address the scalability issue, we propose a three-stage algorithm that first generates a graph of convex polytopes in the workspace free of collision, then poses a large set of small MILPs to generate viable paths between polytopes, and finally queries a pair of start and end configurations for a feasible path online. The graph of convex polytopes serves as a decomposition of the free workspace and the number of decision variables in each MILP is limited by restricting the subproblem within two or three free polytopes rather than the entire free region. Our simulation results demonstrate shorter online computation time compared to baseline methods and scales better with the size of the environment and tunnel width than sampling-based planners in both 2D and 3D environments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。