article

Meeting a deadline: shortest paths on stochastic directed acyclic graphs with information gathering

Authors:

Risto RitalaAuthors Info & Claims

Annals of Mathematics and Artificial Intelligence, Volume 79, Issue 4

Pages 337 - 370

https://doi.org/10.1007/s10472-016-9527-5

Published: 01 April 2017 Publication History

Abstract

We consider the problem of an agent traversing a directed graph with the objective of maximizing the probability of reaching a goal node before a given deadline. Only the probability of the travel times of edges is known to the agent. The agent must balance between traversal actions towards the goal, and delays due to actions improving information about graph edge travel times. We describe the relationship of the problem to the more general partially observable Markov decision process. Further, we show that if edge travel times are independent and the underlying directed graph is acyclic, a closed loop solution can be computed. The solution specifies whether to execute a traversal or information-gathering action as a function of the current node, the time remaining until the deadline, and the information about edge travel times. We present results from two case studies, quantifying the usefulness of information-gathering as opposed to applying only traversal actions.

References

[1]

Araya-López, M., Buffet, O., Thomas, V., Charpillet, F.: A POMDP extension with belief-dependent rewards. In: Lafferty, J., Williams, C., Shawe-Taylor, J., Zemel, R., Culotta, A. (eds.) Advances in Neural Information Processing Systems 23, pp. 64---72. Vancouver, Canada (2010)

Digital Library

[2]

Bnaya, Z., Felner, A., Shimony, S.E.: Canadian traveler problem with remote sensing. In: Proc. Intl. Joint Conf. on Artificial Intelligence (IJCAI), pp. 437---442 (2009)

Digital Library

[3]

Bonet, B.: Deterministic POMDPs revisited. In: Proc. of the 25th Conference on Uncertainty in Artificial Intelligence (UAI), pp. 59---66. Montreal, Canada (2009)

Digital Library

[4]

Bonet, B., Geffner, H.: Solving POMDPs: RTDP-Bel vs. point-based algorithms. In: Proc. Intl. Joint Conf. on Artificial Intelligence (IJCAI), pp. 1641---1646 (2009)

Digital Library

[5]

Chen, A., Ji, Z.: Path finding under uncertainty. J. Adv. Transp. 39(1), 19---37 (2005)

[6]

Chen, B.Y., Lam, W.H., Sumalee, A., Li, Z.: Reliable shortest path finding in stochastic networks with spatial correlated link travel times. Int. J. Geogr. Inf. Sci. 26(2), 365---386 (2012).

[7]

Dibangoye, J., Shani, G., Chaib-draa, B., Mouaddib, A.I.: Topological order planner for POMDPs. In: Proceedings of the 21st International Joint Conference on Artifical Intelligence, pp. 1684---1689 (2009)

Digital Library

[8]

Dreyfus, S.E.: An appraisal of some shortest-path algorithms. Oper. Res. 17(3), 395---412 (1969).

Digital Library

[9]

Fan, Y., Kalaba, R., Moore J.E.I.: Arriving on time. J. Optim. Theory Appl. 127(3), 497---513 (2005).

[10]

Fan, Y., Nie, Y.: Optimal routing for maximizing the travel time reliability. Networks and Spatial Economics 6(3-4), 333---344 (2006).

[11]

Frank, H.: Shortest paths in probabilistic graphs. Oper. Res. 17(4), 583---599 (1969).

Digital Library

[12]

French, S., Insua, D.R. 2: Statistical decision theory, Kendall's Library of Statistics, vol. 9. Wiley (2000)

[13]

Fu, L.: An adaptive routing algorithm for in-vehicle route guidance systems with real-time information. Transp. Res. B Methodol. 35, 749---765 (2001).

[14]

Fu, L., Rilett, L.: Expected shortest paths in dynamic and stochastic traffic networks. Transp. Res. B Methodol. 32(7), 499---516 (1998).

[15]

Gao, S., Chabini, I.: Optimal routing policy problems in stochastic time-dependent networks. Transp. Res. B Methodol. 40(2), 93---122 (2006).

[16]

Gao, S.: Real-time traveler information for optimal adaptive routing in stochastic time-dependent networks. Transp. Res. Part C: Emerging Technologies 21, 196---213 (2012).

[17]

Hall, R.W.: The fastest path through a network with random time-dependent travel times. Transplant. Sci. 20(3), 182---188 (1986).

Digital Library

[18]

Huang, H., Gao, S.: Optimal paths in dynamic networks with dependent random link travel times. Transp. Res. B Methodol. 46, 579---598 (2012).

[19]

Kaelbling, L., Littman, M., Cassandra, A.: Planning and acting in partially observable stochastic domains. Artif. Intell. 101(1-2), 99---134 (1998)

[20]

Lauri, M., Ritala, R.: Path planning in dynamic environments with the partially observable canadian traveller's problem. In: Proceedings of the 1st ICAPS Workshop on Planning and Robotics (PlanRob), pp. 89---95 (2013)

[21]

LaValle, S.M.: Planning algorithms. Cambridge University Press (2006)

Digital Library

[22]

Lim, S., Sommer, C., Nikolova, E., Rus, D.: Practical route planning under delay uncertainty: Stochastic shortest path queries. In: Proceedings of Robotics: Science and Systems. Sydney, Australia (2012)

[23]

Loui, R.P.: Optimal paths in graphs with stochastic or multidimensional weights. Commun. ACM 26(9), 670---676 (1983).

Digital Library

[24]

Melin, J., Lauri, M., Kolu, A., Koljonen, J., Ritala, R.: Cooperative sensing and path planning in a multi-vehicle environment (2015)

[25]

Miller-Hooks, E.: Adaptive least-expected time paths in stochastic, time-varying transportation and data networks. Networks 37(1), 35---52 (2001)

[26]

Miller-Hooks, E., Mahmassani, H.S.: Least expected time paths in stochastic, time-varying transportation networks. Transplant. Sci. 34(2), 198---215 (2000)

Digital Library

[27]

Murphy, K.P.: Machine Learning: A Probabilistic Perspective. The MIT Press (2012)

Digital Library

[28]

Murthy, I., Sarkar, S.: Stochastic shortest path problems with piecewise-linear concave utility functions. Manag. Sci. 44(11-part-2), S125---S136 (1998).

[29]

von Neumann, J., Morgenstern, O.: Theory of games and economic behavior. Princeton University Press, Princeton (1947)

[30]

Nie, Y., Fan, Y.: Arriving-on-time problem: discrete algorithm that ensures convergence. Transp. Res. Record: J. Transp. Res. Board 1964, 193---200 (2006)

[31]

Nie, Y.M., Wu, X.: Shortest path problem considering on-time arrival probability. Transp. Res. B Methodol. 43(6), 597---613 (2009).

[32]

Nie, Y.M., Wu, X., Dillenburg, J.F., Nelson, P.C.: Reliable route guidance: A case study from Chicago. Transp. Res. A Policy Pract. 46(2), 403---419 (2012).

[33]

Nikolova, E.: Approximation algorithms for reliable stochastic combinatorial optimization. In: Lecture Notes in Computer Science, vol. 6302, pp. 338---351. (2010).

Digital Library

[34]

Nikolova, E., Karger, D.R.: Route planning under uncertainty: The canadian traveller problem. In: AAAI, pp. 969---974 (2008)

Digital Library

[35]

Ong, S.C.W., Png, S.W., Hsu, D., Lee, W.: Planning under uncertainty for robotic tasks with mixed observability. Int. J. Robot. Res. 29(8), 1053---1068 (2010).

Digital Library

[36]

Pan, Y., Sun, L., Ge, M.: Finding reliable shortest path in stochastic time-dependent network. Procedia - Social and Behavioral Sciences 96, 451---460 (2013).

[37]

Papadimitriou, C.H., Tsitsiklis, J.N.: The complexity of markov decision processes. Math. Oper. Res. 12, 441---450 (1987).

Digital Library

[38]

Papadimitriou, C.H., Yannakakis, M.: Shortest paths without a map. Theor. Comput. Sci. 84(1), 127---150 (1991).

Digital Library

[39]

Polychronopoulos, G., Tsitsiklis, J.: Stochastic shortest path problems with recourse. Networks 27(2), 133---143 (1996)

[40]

Porta, J., Vlassis, N., Spaan, M., Poupart, P.: Point-based value iteration for continuous POMDPs. J. Mach. Learn. Res. 7, 2329---2367 (2006)

Digital Library

[41]

Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, New York (1994)

Digital Library

[42]

Samaranayake, S., Blandin, S., Bayen, A.: A tractable class of algorithms for reliable routing in stochastic networks. Transportation Research Part C: Emerging Technologies 20(1), 199---217 (2012).

[43]

Spaan, M.T.J., Veiga, T.S., Lima, P.U.: Decision-theoretic planning under uncertainty with information rewards for active cooperative perception. Auton. Agent. Multi-Agent Syst. 29(6), 1157---1185 (2015).

Digital Library

[44]

Stuart, A., Ord, K.J.: Kendall's Advanced Theory of Statistics, vol. 1. Distribution theory. Arnold, London (1994)

[45]

Tippett, L.H.C.: On the extreme individuals and the range of samples taken from a normal population. Biometrika 17(3/4), 364 (1925).

[46]

Zockaie, A., Nie, Y., Mahmassani, H.: Simulation-based method for finding minimum travel time budget paths in stochastic networks with correlated link times. Transp. Res. Record: J. Transp. Res. Board 2467, 140---148 (2014).

Cited By

Veiga TRenoux J(2023)From Reactive to Active Sensing: A Survey on Information Gathering in Decision-theoretic PlanningACM Computing Surveys10.1145/358306855:13s(1-22)Online publication date: 13-Jul-2023
https://dl.acm.org/doi/10.1145/3583068
Arruda EPereira BThiers CTura B(2019)Optimal testing policies for diagnosing patients with intermediary probability of diseaseArtificial Intelligence in Medicine10.1016/j.artmed.2018.11.00597:C(89-97)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1016/j.artmed.2018.11.005

Recommendations

Planning for multiple measurement channels in a continuous-state POMDP

Continuous-state partially observable Markov decision processes (POMDPs) are an intuitive choice of representation for many stochastic planning problems with a hidden state. We consider a continuous-state POMDPs with finite action and observation spaces,...
Continuous-Time Markov Decision Processes with State-Dependent Discount Factors

We consider continuous-time Markov decision processes in Polish spaces. The performance of a control policy is measured by the expected discounted reward criterion associated with state-dependent discount factors. All underlying Markov processes are ...
Stochastic Dynamic Programming with Non-linear Discounting
Abstract
In this paper, we study a Markov decision process with a non-linear discount function and with a Borel state space. We define a recursive discounted utility, which resembles non-additive utility functions considered in a number of models in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Annals of Mathematics and Artificial Intelligence

Annals of Mathematics and Artificial Intelligence Volume 79, Issue 4

April 2017

123 pages

ISSN:1012-2443

Issue’s Table of Contents

Copyright © Copyright © 2017 Springer International Publishing Switzerland.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 April 2017

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Veiga TRenoux J(2023)From Reactive to Active Sensing: A Survey on Information Gathering in Decision-theoretic PlanningACM Computing Surveys10.1145/358306855:13s(1-22)Online publication date: 13-Jul-2023
https://dl.acm.org/doi/10.1145/3583068
Arruda EPereira BThiers CTura B(2019)Optimal testing policies for diagnosing patients with intermediary probability of diseaseArtificial Intelligence in Medicine10.1016/j.artmed.2018.11.00597:C(89-97)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1016/j.artmed.2018.11.005

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents