Multi-objective Conflict-based Search for Multi-agent Path Finding

Conventional multi-agent path planners typically compute an ensemble of paths while optimizing a single objective, such as path length. However, many applications may require multiple objectives, say fuel consumption and completion time, to be simultaneously optimized during planning and these criteria may not be readily compared and sometimes lie in competition with each other. Naively applying existing multi-objective search algorithms to multi-agent path finding may prove to be inefficient as the size of the space of possible solutions, i. e. , the Pareto-optimal set, can grow exponentially with the number of agents (the dimension of the search space). This article presents an approach named Multi-objective Conflict-based Search (MO-CBS) that bypasses this so-called curse of dimensionality by leveraging prior Conflict-based Search (CBS), a well-known algorithm for single-objective multi-agent path finding, and principles of dominance from multi-objective optimization literature. We prove that MO-CBS is able to compute the entire Pareto-optimal set. Our results show that MO-CBS can solve problem instances with hundreds of Pareto-optimal solutions which the standard multi-objective A* algorithms could not find within a bounded time.

Authors

• Zhongqiang Ren
• Sivakumar Rathinam
• Howie Choset

Keywords

• Measurement
• Automation
• Conferences
• Approximation algorithms
• Search problems
• Planning
• Fuels
• Pathfinding
• Multi-Agent Path Finding
• Conflict-based Search
• Search Algorithm
• Multi-objective Optimization
• Multiple Objects
• Path Planning
• Number Of Agents
• Curse Of Dimensionality
• Multi-objective Algorithm
• Pareto Optimal Solutions
• Pareto Optimal Set
• Dominant Principle
• Numerical Results
• Running Time
• Loss Of Generality
• Feasible Solution
• Root Node
• Euclidean Norm
• Number Of Objects
• Individual Paths
• Tree Search
• Vertices
• Optimal Path
• Empty Set
• Expansion Strategy
• Leaf Node
• Average Running Time