Multi-objective Conflict-based Search Using Safe-interval Path Planning
Published in
arXiv.org(2021)External Links:
TL
TL;DR
This paper develops the MO-SIPP algorithm, shows its properties and embeds it in MO-CBS, and presents extensive numerical results to show that there is an order of magnitude improvement in the average low level search time and a significant improved in the success rates of finding the Pareto-optimal front.
Abstract
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.
References46 items
1
Multicriteria Optimization and Decision Making: Principles, Algorithms and Case Studies
2
Binary Branching Multi-Objective Conflict-Based Search for Multi-Agent Path Finding
3
Optimal and Bounded-Suboptimal Multi-Agent Motion Planning
4
Multi-Objective Graph Heuristic Search for Terrestrial Robot Design
5