Mixed Integer Conic Programming for Multi-Agent Motion Planning in Continuous Space

Multi-Agent Motion Planning (MAMP) seeks collision-free trajectories for multiple agents from their respective start to goal locations among static obstacles, while minimizing a cost function over the trajectories. Existing approaches for this problem include graph-based, Mix-Integer Programming (MIP) based and trajectory optimization-based, each with its own limitations. This paper introduces a new approach for MAMP based on Mixed Integer Conic Programming (MICP) formulation that complements these existing approaches. We show that our formulation is valid and test our approach against various baselines, including a graph-based method that combines search and sampling, as well as different MIP formulations. The numerical results show that the solutions found by our approach are sometimes eight times closer to the true optimum than the ones found by the baseline when given the same amount of runtime limit. We also verify our approach with multiple drones in a lab setting.

Authors

• Shizhe Zhao
• Yongce Liu
• Howie Choset
• Zhongqiang Ren

Keywords

• Runtime
• Programming
• Cost function
• Trajectory
• Planning
• Intelligent robots
• Drones
• Mixed Integer
• Mixed-integer Conic Programming
• Multi-agent Motion Planning
• Mixed-integer Programming
• Graph-based Methods
• Static Obstacles
• Time Step
• Lower Bound
• Feasible Solution
• Decision Variables
• Number Of Agents
• Overview Of Methods
• Speed Limit
• Solution Quality
• Linear Constraints
• Motion Capture System
• Trajectory Optimization
• Half-plane
• Planning Problem
• Discrete Time Steps
• Mixed-integer Nonlinear Programming
• Sampling-based Methods
• Random Environment
• Narrow Corridor
• Trajectories Of Agents
• Convex Polygon
• Trajectory Length
• Position Of Agent
• Discretion
• Shortest Path