Hierarchical Multiobjective Shortest Path Problems
dc.contributor.author
Slutsky, Konstantin
dc.contributor.author
Yershov, Dmitry
dc.contributor.author
Wongpiromsarn, Tichakorn
dc.contributor.author
Frazzoli, Emilio
dc.contributor.editor
LaValle, Steven M.
dc.contributor.editor
Lin, Ming
dc.contributor.editor
Ojala, Timo
dc.contributor.editor
Shell, Dylan
dc.contributor.editor
Yu, Jingjin
dc.date.accessioned
2021-03-04T15:08:08Z
dc.date.available
2021-01-28T22:46:08Z
dc.date.available
2021-03-04T15:08:08Z
dc.date.issued
2021
dc.identifier.isbn
978-3-030-66722-1
en_US
dc.identifier.isbn
978-3-030-66723-8
en_US
dc.identifier.issn
2511-1256
dc.identifier.other
10.1007/978-3-030-66723-8_16
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/466526
dc.description.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.
en_US
dc.language.iso
en
en_US
dc.publisher
Springer
en_US
dc.title
Hierarchical Multiobjective Shortest Path Problems
en_US
dc.type
Conference Paper
dc.date.published
2021-02-09
ethz.book.title
Algorithmic Foundations of Robotics XIV
en_US
ethz.journal.title
Springer Proceedings in Advanced Robotics
ethz.journal.volume
17
en_US
ethz.journal.abbreviated
Springer proc. adv. robotics
ethz.pages.start
261
en_US
ethz.pages.end
276
en_US
ethz.event
The 14th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2020) (cancelled)
en_US
ethz.event.location
Oulu, Finland
en_US
ethz.event.date
June 21-23, 2020
en_US
ethz.notes
Conference postponed due to Corona virus (COVID-19) to 2021. Then Conference cancelled due to Corona virus (COVID-19).
en_US
ethz.publication.place
Cham
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02130 - Dep. Maschinenbau und Verfahrenstechnik / Dep. of Mechanical and Process Eng.::02619 - Inst. Dynam. Syst. u. Regelungstechnik / Inst. Dynamic Systems and Control::09574 - Frazzoli, Emilio / Frazzoli, Emilio
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02130 - Dep. Maschinenbau und Verfahrenstechnik / Dep. of Mechanical and Process Eng.::02619 - Inst. Dynam. Syst. u. Regelungstechnik / Inst. Dynamic Systems and Control::09574 - Frazzoli, Emilio / Frazzoli, Emilio
ethz.date.deposited
2021-01-28T22:46:15Z
ethz.source
BATCH
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2021-03-04T15:08:19Z
ethz.rosetta.lastUpdated
2021-03-04T15:08:19Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Hierarchical%20Multiobjective%20Shortest%20Path%20Problems&rft.jtitle=Springer%20Proceedings%20in%20Advanced%20Robotics&rft.date=2021&rft.volume=17&rft.spage=261&rft.epage=276&rft.issn=2511-1256&rft.au=Slutsky,%20Konstantin&Yershov,%20Dmitry&Wongpiromsarn,%20Tichakorn&Frazzoli,%20Emilio&rft.isbn=978-3-030-66722-1&978-3-030-66723-8&rft.genre=proceeding&rft_id=info:doi/10.1007/978-3-030-66723-8_16&rft.btitle=Algorithmic%20Foundations%20of%20Robotics%20XIV
Files in this item
| Files | Size | Format | Open in viewer |
|---|---|---|---|
|
There are no files associated with this item. |
|||
Publication type
-
Conference Paper [35866]