Hierarchical Multiobjective Shortest Path Problems
METADATA ONLY
Loading...
Author / Producer
Date
2021
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Book title
Algorithmic Foundations of Robotics XIV
Journal / series
Volume
17
Pages / Article No.
261 - 276
Publisher
Springer
Event
The 14th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2020) (cancelled)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
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).