.png){kind=icon}
返回
CP-MILP: Mixed Integer Linear Programming for Multi-Agent Motion Planning With Linear Dynamics
.png){kind=icon}
PRE
AI
DOI：10.1109/LRA.2025.3623912.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
This paper considers a Multi-Agent Motion Planning (MAMP) problem that seeks collision-free paths for multiple agents from their respective start to goal locations among static obstacles, while minimizing the arrival times of the agents with linear dynamics. Among existing approaches such as graph search, sampling, and trajectory optimization, mixed integer programming (MIP) can often find high quality solutions with optimality guarantees. MIP approaches have been investigated extensively and many of them build upon a mixed-integer linear program (MILP) for single-agent, which depends on big-M constraints, a popular technique to formulate conditional constraints. We take the view that some big-M constraints there are unnecessary, and may potentially slow down the computation. This paper thus proposes a new MILP formulation using a perspective technique related to the control terms to bypass some of the big-M constraints, and hence the name Control Perspective MILP (CP-MILP). We analyze the property of our CP-MILP and experimental results show CP-MILP sometimes requires up to near an order of magnitude less runtime to solve to optimality.
Keyword:
Trajectory
Planning
Collision avoidance
Runtime
Dynamics
Aerospace electronics
Vectors
Mixed integer linear programming
Indexes
Trajectory optimization
Motion and path planning
multi-robot systems
path planning for multiple mobile robots or agents
期刊
I
IF:
5.3
论文数:
2.0K
被引数:
3.9W
机构
引用论文
.png){kind=icon}
Distributed Nonlinear Trajectory Optimization for Multi-Robot Motion Planning多机器人运动规划的分布式非线性轨迹优化
OAAI
OAAI分享收藏
查看更多内容