用数学规划解决多智能体在受限环境下的避障路径规划问题。
A MILP-Based Solution to Multi-Agent Motion Planning and Collision Avoidance in Constrained Environments
- 将区域序列与大M超平面模型结合，限制智能体在相邻凸多面体间移动。
- 仅对共享或邻接区域的智能体施加碰撞约束，二元变量数呈指数级减少。
- 相比基线方法提速十倍，且可保证有限时间收敛，适合复杂场景部署。
我们提出一种混合整数线性规划（MILP）方法用于多智能体运动规划，将基于多面体动作的运动规划（PAAMP）嵌入到先生成序列再求解的流程中。区域序列将每个智能体限制在相邻的凸多面体区域内，而大M超平面模型则确保智能体间的分离。碰撞约束仅作用于共享或邻近区域的智能体，相比朴素公式大幅减少二元变量数量。采用L1路径长度加加速度代价函数，获得平滑轨迹。我们证明了该方法具有有限时间收敛性，并在包含障碍物的典型多智能体场景中验证：其生成的无碰撞轨迹比未经结构化设计的MILP基线方法快一个数量级。
原文摘要 · Abstract (English)
We propose a mixed-integer linear program (MILP) for multi-agent motion planning that embeds Polytopic Action-based Motion Planning (PAAMP) into a sequence-then-solve pipeline. Region sequences confine each agent to adjacent convex polytopes, while a big-M hyperplane model enforces inter-agent separation. Collision constraints are applied only to agents sharing or neighboring a region, which reduces binary variables exponentially compared with naive formulations. An L1 path-length-plus-acceleration cost yields smooth trajectories. We prove finite-time convergence and demonstrate on representative multi-agent scenarios with obstacles that our formulation produces collision-free trajectories an order of magnitude faster than an unstructured MILP baseline.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。