- 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. Mehr anzeigen
BuchtitelAlgorithmic Foundations of Robotics XIV
Zeitschrift / SerieSpringer Proceedings in Advanced Robotics
Seiten / Artikelnummer
Organisationseinheit09574 - Frazzoli, Emilio / Frazzoli, Emilio
AnmerkungenConference postponed due to Corona virus (COVID-19) to 2021. Then Conference cancelled due to Corona virus (COVID-19).