A multi-objective approach for PH-graphs with applications to stochastic shortest paths
- PDF / 993,660 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 89 Downloads / 180 Views
A multi-objective approach for PH-graphs with applications to stochastic shortest paths Peter Buchholz1
· Iryna Dohndorf1
Received: 25 September 2019 / Revised: 23 August 2020 / Accepted: 3 October 2020 © The Author(s) 2020
Abstract Stochastic 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. Keywords Stochastic shortest path problems · Markov decision processes · Phase type distributions · PH graphs · Multicriteria optimization
1 Introduction Shortest path problems are classical decision problems in computer science and operations research with many practical applications. The goal is to find an in some sense optimal path between a source and a destination node in a weighted directed graph. Weights of edges describe time, costs, gain, or reliability when passing the edge. We use in the sequel the term costs of an edge to describe the quantitative parameter. The
B
Peter Buchholz [email protected] Iryna Dohndorf [email protected]
1
Informatik IV, TU Dortmund, 44221 Dortmund, Germany
123
P. Buchholz, I. Dohndorf
entire version of the problem assumes deterministic costs. However, often costs are not exactly known such that stochastic descriptions of the costs are more appropriate which results in the Stochastic Shortest Path Problem (SSPP). We consider in this paper cases where a decision maker can decide to choose an outgoing edge when reaching a node. This implies that decisions are made adaptively and not a priori as in Nie and Wu (2009). In many practical applications, random variables modeling the edge costs are not independent. For example adjacent roads have similar traffic conditions, interest rates in subsequent periods are correlated and failure rates of related components are dependent. This implies that the introduction of correlation in SSPPs is important for realistic models but makes the problem of specifying parameters and computing optimal paths even harder. In a stochastic setting with adaptive decisions, a unique optimal path usually does not exist, instead the chosen path depends on the realization of costs
Data Loading...
