Metadata only
Date
2021Type
- Conference Paper
ETH Bibliography
yes
Altmetrics
Abstract
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
Publication status
publishedExternal links
Book title
Algorithmic Foundations of Robotics XIVJournal / series
Springer Proceedings in Advanced RoboticsVolume
Pages / Article No.
Publisher
SpringerEvent
Organisational unit
09574 - Frazzoli, Emilio / Frazzoli, Emilio
Notes
Conference postponed due to Corona virus (COVID-19) to 2021. Then Conference cancelled due to Corona virus (COVID-19).More
Show all metadata
ETH Bibliography
yes
Altmetrics