A multi-objective approach for PH-graphs with applications to stochastic shortest paths

Simple item page
dc.contributor.authorBuchholz, Peter
dc.contributor.authorDohndorf, Iryna
dc.date.accessioned2021-04-06T11:19:09Z
dc.date.available2021-04-06T11:19:09Z
dc.date.issued2020-10-24
dc.description.abstractStochastic shortest path problems (SSPPs) have many applications in practice and are subject of ongoing research for many years. This paper considers a variant of SSPPs where times or costs to pass an edge in a graph are, possibly correlated, random variables. There are two general goals one can aim for, the minimization of the expected costs to reach the destination or the maximization of the probability to reach the destination within a given budget. Often one is interested in policies that build a compromise between different goals which results in multi-objective problems. In this paper, an algorithm to compute the convex hull of Pareto optimal policies that consider expected costs and probabilities of falling below given budgets is developed. The approach uses the recently published class of PH-graphs that allow one to map SSPPs, even with generally distributed and correlated costs associated to edges, on Markov decision processes (MDPs) and apply the available techniques for MDPs to compute optimal policies.en
dc.identifier.urihttp://hdl.handle.net/2003/40139
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-22014
dc.language.isoende
dc.relation.ispartofseriesMath Meth Oper Res;93
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subjectStochastic shortest path problemsen
dc.subjectMarkov decision processesen
dc.subjectPhase type distributionsen
dc.subjectPH graphsen
dc.subjectMulticriteria optimizationen
dc.subject.ddc004
dc.titleA multi-objective approach for PH-graphs with applications to stochastic shortest pathsen
dc.typeTextde
dc.type.publicationtypearticlede
dcterms.accessRightsopen access
eldorado.secondarypublicationtruede
eldorado.secondarypublication.primarycitationBuchholz, P., Dohndorf, I. A multi-objective approach for PH-graphs with applications to stochastic shortest paths. Math Meth Oper Res 93, 153–178 (2021).de
eldorado.secondarypublication.primaryidentifierhttps://doi.org/10.1007/s00186-020-00729-3de

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Buchholz-Dohndorf2021_Article_AMulti-objectiveApproachForPH-.pdf
Size:
959.79 KB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.85 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

LS 04 Praktische Informatik