Скачать или смотреть Hierarchical Multiobjective Shortest Path Problems

Hierarchical Multiobjective Shortest Path Problems

Konstantin Slutsky (Iowa State University, IA, USA)
Dmitry Yershov (Motional Inc)
Tichakorn Wongpiromsarn (Iowa State University, IA, USA)
Emilio Frazzoli (Motional Inc)


We consider the shortest path problem on graphs with weights taking values in Cartesian products of cost monoids. Such cost structures appear in multiobjective planning including, for instance, the minimum-violation planning framework. It is known that these products often do not satisfy the conditions of a cost monoid. Classical dynamic programming graph search algorithms may therefore fail to find an optimal solution.

We isolate the concept of a regular cost monoid and propose an iterative search algorithm that finds an optimal path in graphs weighted by products of such costs. Our algorithm allows this class of multiobjective planning problems to be solved in polynomial time.

Keywords: Noneuclidean Shortest Path Problem, Multiobjective Path Planning, Minimum Violation Motion Planning, Autonomous Vehicle Navigation in Urban Environments, Traffic Rule Constraints