.png){kind=icon}
.png){kind=icon}
Return
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}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
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
Journal
I
IF:
5.3
Papers:
1.6K
Citations:
3.9W