- Conference Paper
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. Show more
Book titleAlgorithmic Foundations of Robotics XIV
Journal / seriesSpringer Proceedings in Advanced Robotics
Pages / Article No.
Organisational unit09574 - Frazzoli, Emilio / Frazzoli, Emilio
NotesConference postponed due to Corona virus (COVID-19) to 2021. Then Conference cancelled due to Corona virus (COVID-19).
MoreShow all metadata