Multi-objective Conflict-based Search Using Safe-interval Path Planning
This addresses path planning with conflicting objectives like travel time and risk for applications such as hazardous material transportation, representing an incremental improvement over previous methods.
The paper tackles the multi-objective multi-agent path finding problem by proposing a new MO-CBS approach with a novel MO-SIPP algorithm, resulting in an order of magnitude improvement in average low-level search time and significant gains in success rates for finding Pareto-optimal fronts.
This paper addresses a generalization of the well known multi-agent path finding (MAPF) problem that optimizes multiple conflicting objectives simultaneously such as travel time and path risk. This generalization, referred to as multi-objective MAPF (MOMAPF), arises in several applications ranging from hazardous material transportation to construction site planning. In this paper, we present a new multi-objective conflict-based search (MO-CBS) approach that relies on a novel multi-objective safe interval path planning (MO-SIPP) algorithm for its low-level search. We first develop the MO-SIPP algorithm, show its properties and then embed it in MO-CBS. We present extensive numerical results to show that (1) there is an order of magnitude improvement in the average low level search time, and (2) a significant improvement in the success rates of finding the Pareto-optimal front can be obtained using the proposed approach in comparison with the previous MO-CBS.