安全区間経路計画を用いた多目的競合ベース探索
Multi-objective Conflict-based Search Using Safe-interval Path Planning
移動時間と経路リスクなど複数の目的を同時に最適化する多目的マルチエージェント経路探索(MOMAPF)に対し、低レベル探索に多目的安全区間経路計画(MO-SIPP)を組み込んだ新しいMO-CBSを提案し、探索時間とパレート最適解の発見率を改善した。
著者: Zhongqiang Ren, Sivakumar Rathinam, Maxim Likhachev, Howie Choset
分類: cs.RO, cs.AI
原文アブストラクト
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.
