{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:44:42Z","timestamp":1740123882387,"version":"3.37.3"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,9,28]],"date-time":"2016-09-28T00:00:00Z","timestamp":1475020800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Suomen Akatemia","doi-asserted-by":"publisher","award":["268152"],"award-info":[{"award-number":["268152"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s10472-016-9527-5","type":"journal-article","created":{"date-parts":[[2016,9,27]],"date-time":"2016-09-27T18:36:09Z","timestamp":1475001369000},"page":"337-370","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Meeting a deadline: shortest paths on stochastic directed acyclic graphs with information gathering"],"prefix":"10.1007","volume":"79","author":[{"given":"Mikko","family":"Lauri","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aino","family":"Ropponen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Risto","family":"Ritala","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,9,28]]},"reference":[{"unstructured":"Araya-L\u00f3pez, 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\u201372. Vancouver, Canada (2010)","key":"9527_CR1"},{"unstructured":"Bnaya, Z., Felner, A., Shimony, S.E.: Canadian traveler problem with remote sensing. In: Proc. Intl. Joint Conf. on Artificial Intelligence (IJCAI), pp. 437\u2013442 (2009)","key":"9527_CR2"},{"unstructured":"Bonet, B.: Deterministic POMDPs revisited. In: Proc. of the 25th Conference on Uncertainty in Artificial Intelligence (UAI), pp. 59\u201366. Montreal, Canada (2009)","key":"9527_CR3"},{"unstructured":"Bonet, B., Geffner, H.: Solving POMDPs: RTDP-Bel vs. point-based algorithms. In: Proc. Intl. Joint Conf. on Artificial Intelligence (IJCAI), pp. 1641\u20131646 (2009)","key":"9527_CR4"},{"issue":"1","key":"9527_CR5","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1002\/atr.5670390104","volume":"39","author":"A Chen","year":"2005","unstructured":"Chen, A., Ji, Z.: Path finding under uncertainty. J. Adv. Transp. 39(1), 19\u201337 (2005)","journal-title":"J. Adv. Transp."},{"issue":"2","key":"9527_CR6","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1080\/13658816.2011.598133","volume":"26","author":"BY Chen","year":"2012","unstructured":"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\u2013386 (2012). doi: 10.1080\/13658816.2011.598133","journal-title":"Int. J. Geogr. Inf. Sci."},{"unstructured":"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\u20131689 (2009)","key":"9527_CR7"},{"issue":"3","key":"9527_CR8","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1287\/opre.17.3.395","volume":"17","author":"SE Dreyfus","year":"1969","unstructured":"Dreyfus, S.E.: An appraisal of some shortest-path algorithms. Oper. Res. 17(3), 395\u2013412 (1969). doi: 10.1287\/opre.17.3.395","journal-title":"Oper. Res."},{"issue":"3","key":"9527_CR9","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1007\/s10957-005-7498-5","volume":"127","author":"Y Fan","year":"2005","unstructured":"Fan, Y., Kalaba, R., Moore J.E.I.: Arriving on time. J. Optim. Theory Appl. 127(3), 497\u2013513 (2005). doi: 10.1007\/s10957-005-7498-5","journal-title":"J. Optim. Theory Appl."},{"issue":"3-4","key":"9527_CR10","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/s11067-006-9287-6","volume":"6","author":"Y Fan","year":"2006","unstructured":"Fan, Y., Nie, Y.: Optimal routing for maximizing the travel time reliability. Networks and Spatial Economics 6(3-4), 333\u2013344 (2006). doi: 10.1007\/s11067-006-9287-6","journal-title":"Networks and Spatial Economics"},{"issue":"4","key":"9527_CR11","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1287\/opre.17.4.583","volume":"17","author":"H Frank","year":"1969","unstructured":"Frank, H.: Shortest paths in probabilistic graphs. Oper. Res. 17(4), 583\u2013599 (1969). doi: 10.1287\/opre.17.4.583","journal-title":"Oper. Res."},{"unstructured":"French, S., Insua, D.R. 2: Statistical decision theory, Kendall\u2019s Library of Statistics, vol. 9. Wiley (2000)","key":"9527_CR12"},{"key":"9527_CR13","doi-asserted-by":"publisher","first-page":"749","DOI":"10.1016\/S0191-2615(00)00019-9","volume":"35","author":"L Fu","year":"2001","unstructured":"Fu, L.: An adaptive routing algorithm for in-vehicle route guidance systems with real-time information. Transp. Res. B Methodol. 35, 749\u2013765 (2001). doi: 10.1016\/S0191-2615(00)00019-9","journal-title":"Transp. Res. B Methodol."},{"issue":"7","key":"9527_CR14","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1016\/S0191-2615(98)00016-2","volume":"32","author":"L Fu","year":"1998","unstructured":"Fu, L., Rilett, L.: Expected shortest paths in dynamic and stochastic traffic networks. Transp. Res. B Methodol. 32(7), 499\u2013516 (1998). doi: 10.1016\/S0191-2615(98)00016-2","journal-title":"Transp. Res. B Methodol."},{"issue":"2","key":"9527_CR15","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.trb.2005.02.001","volume":"40","author":"S Gao","year":"2006","unstructured":"Gao, S., Chabini, I.: Optimal routing policy problems in stochastic time-dependent networks. Transp. Res. B Methodol. 40(2), 93\u2013122 (2006). doi: 10.1016\/j.trb.2005.02.001","journal-title":"Transp. Res. B Methodol."},{"key":"9527_CR16","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/j.trc.2011.09.007","volume":"21","author":"S Gao","year":"2012","unstructured":"Gao, S.: Real-time traveler information for optimal adaptive routing in stochastic time-dependent networks. Transp. Res. Part C: Emerging Technologies 21, 196\u2013213 (2012). doi: 10.1016\/j.trc.2011.09.007","journal-title":"Transp. Res. Part C: Emerging Technologies"},{"issue":"3","key":"9527_CR17","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1287\/trsc.20.3.182","volume":"20","author":"RW Hall","year":"1986","unstructured":"Hall, R.W.: The fastest path through a network with random time-dependent travel times. Transplant. Sci. 20(3), 182\u2013188 (1986). doi: 10.1287\/trsc.20.3.182","journal-title":"Transplant. Sci."},{"key":"9527_CR18","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1016\/j.trb.2012.01.005","volume":"46","author":"H Huang","year":"2012","unstructured":"Huang, H., Gao, S.: Optimal paths in dynamic networks with dependent random link travel times. Transp. Res. B Methodol. 46, 579\u2013598 (2012). doi: 10.1016\/j.trb.2012.01.005","journal-title":"Transp. Res. B Methodol."},{"issue":"1-2","key":"9527_CR19","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0004-3702(98)00023-X","volume":"101","author":"L Kaelbling","year":"1998","unstructured":"Kaelbling, L., Littman, M., Cassandra, A.: Planning and acting in partially observable stochastic domains. Artif. Intell. 101(1-2), 99\u2013134 (1998)","journal-title":"Artif. Intell."},{"unstructured":"Lauri, M., Ritala, R.: Path planning in dynamic environments with the partially observable canadian traveller\u2019s problem. In: Proceedings of the 1st ICAPS Workshop on Planning and Robotics (PlanRob), pp. 89\u201395 (2013)","key":"9527_CR20"},{"doi-asserted-by":"crossref","unstructured":"LaValle, S.M.: Planning algorithms. Cambridge University Press (2006)","key":"9527_CR21","DOI":"10.1017\/CBO9780511546877"},{"doi-asserted-by":"crossref","unstructured":"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)","key":"9527_CR22","DOI":"10.15607\/RSS.2012.VIII.032"},{"issue":"9","key":"9527_CR23","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1145\/358172.358406","volume":"26","author":"RP Loui","year":"1983","unstructured":"Loui, R.P.: Optimal paths in graphs with stochastic or multidimensional weights. Commun. ACM 26(9), 670\u2013676 (1983). doi: 10.1145\/358172.358406","journal-title":"Commun. ACM"},{"key":"9527_CR24","volume-title":"Cooperative sensing and path planning in a multi-vehicle environment","author":"J Melin","year":"2015","unstructured":"Melin, J., Lauri, M., Kolu, A., Koljonen, J., Ritala, R.: Cooperative sensing and path planning in a multi-vehicle environment (2015)"},{"issue":"1","key":"9527_CR25","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1002\/1097-0037(200101)37:1<35::AID-NET4>3.0.CO;2-G","volume":"37","author":"E Miller-Hooks","year":"2001","unstructured":"Miller-Hooks, E.: Adaptive least-expected time paths in stochastic, time-varying transportation and data networks. Networks 37(1), 35\u201352 (2001)","journal-title":"Networks"},{"issue":"2","key":"9527_CR26","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1287\/trsc.34.2.198.12304","volume":"34","author":"E Miller-Hooks","year":"2000","unstructured":"Miller-Hooks, E., Mahmassani, H.S.: Least expected time paths in stochastic, time-varying transportation networks. Transplant. Sci. 34(2), 198\u2013215 (2000)","journal-title":"Transplant. Sci."},{"unstructured":"Murphy, K.P.: Machine Learning: A Probabilistic Perspective. The MIT Press (2012)","key":"9527_CR27"},{"issue":"11-part-2","key":"9527_CR28","doi-asserted-by":"publisher","first-page":"S125","DOI":"10.1287\/mnsc.44.11.S125","volume":"44","author":"I Murthy","year":"1998","unstructured":"Murthy, I., Sarkar, S.: Stochastic shortest path problems with piecewise-linear concave utility functions. Manag. Sci. 44(11-part-2), S125\u2013S136 (1998). doi: 10.1287\/mnsc.44.11.S125","journal-title":"Manag. Sci."},{"key":"9527_CR29","volume-title":"Theory of games and economic behavior","author":"J von Neumann","year":"1947","unstructured":"von Neumann, J., Morgenstern, O.: Theory of games and economic behavior. Princeton University Press, Princeton (1947)"},{"key":"9527_CR30","doi-asserted-by":"crossref","first-page":"193","DOI":"10.3141\/1964-21","volume":"1964","author":"Y Nie","year":"2006","unstructured":"Nie, Y., Fan, Y.: Arriving-on-time problem: discrete algorithm that ensures convergence. Transp. Res. Record: J. Transp. Res. Board 1964, 193\u2013200 (2006)","journal-title":"Transp. Res. Record: J. Transp. Res. Board"},{"issue":"6","key":"9527_CR31","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1016\/j.trb.2009.01.008","volume":"43","author":"YM Nie","year":"2009","unstructured":"Nie, Y.M., Wu, X.: Shortest path problem considering on-time arrival probability. Transp. Res. B Methodol. 43(6), 597\u2013613 (2009). doi: 10.1016\/j.trb.2009.01.008","journal-title":"Transp. Res. B Methodol."},{"issue":"2","key":"9527_CR32","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/j.tra.2011.10.008","volume":"46","author":"YM Nie","year":"2012","unstructured":"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\u2013419 (2012). doi: 10.1016\/j.tra.2011.10.008","journal-title":"Transp. Res. A Policy Pract."},{"doi-asserted-by":"publisher","unstructured":"Nikolova, E.: Approximation algorithms for reliable stochastic combinatorial optimization. In: Lecture Notes in Computer Science, vol. 6302, pp. 338\u2013351. doi: 10.1007\/978-3-642-15369-3_26 (2010)","key":"9527_CR33","DOI":"10.1007\/978-3-642-15369-3_26"},{"unstructured":"Nikolova, E., Karger, D.R.: Route planning under uncertainty: The canadian traveller problem. In: AAAI, pp. 969\u2013974 (2008)","key":"9527_CR34"},{"issue":"8","key":"9527_CR35","doi-asserted-by":"publisher","first-page":"1053","DOI":"10.1177\/0278364910369861","volume":"29","author":"SCW Ong","year":"2010","unstructured":"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\u20131068 (2010). doi: 10.1177\/0278364910369861","journal-title":"Int. J. Robot. Res."},{"key":"9527_CR36","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/j.sbspro.2013.08.053","volume":"96","author":"Y Pan","year":"2013","unstructured":"Pan, Y., Sun, L., Ge, M.: Finding reliable shortest path in stochastic time-dependent network. Procedia - Social and Behavioral Sciences 96, 451\u2013460 (2013). doi: 10.1016\/j.sbspro.2013.08.053","journal-title":"Procedia - Social and Behavioral Sciences"},{"key":"9527_CR37","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1287\/moor.12.3.441","volume":"12","author":"CH Papadimitriou","year":"1987","unstructured":"Papadimitriou, C.H., Tsitsiklis, J.N.: The complexity of markov decision processes. Math. Oper. Res. 12, 441\u2013450 (1987). doi: 10.1287\/moor.12.3.441","journal-title":"Math. Oper. Res."},{"issue":"1","key":"9527_CR38","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0304-3975(91)90263-2","volume":"84","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Shortest paths without a map. Theor. Comput. Sci. 84(1), 127\u2013150 (1991). doi: 10.1016\/0304-3975(91)90263-2","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Polychronopoulos, G., Tsitsiklis, J.: Stochastic shortest path problems with recourse. Networks 27(2), 133\u2013143 (1996)","key":"9527_CR39","DOI":"10.1002\/(SICI)1097-0037(199603)27:2<133::AID-NET5>3.0.CO;2-L"},{"key":"9527_CR40","first-page":"2329","volume":"7","author":"J Porta","year":"2006","unstructured":"Porta, J., Vlassis, N., Spaan, M., Poupart, P.: Point-based value iteration for continuous POMDPs. J. Mach. Learn. Res. 7, 2329\u20132367 (2006)","journal-title":"J. Mach. Learn. Res."},{"key":"9527_CR41","doi-asserted-by":"crossref","DOI":"10.1002\/9780470316887","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"ML Puterman","year":"1994","unstructured":"Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, New York (1994)"},{"issue":"1","key":"9527_CR42","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.trc.2011.05.009","volume":"20","author":"S Samaranayake","year":"2012","unstructured":"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\u2013217 (2012). doi: 10.1016\/j.trc.2011.05.009","journal-title":"Transportation Research Part C: Emerging Technologies"},{"issue":"6","key":"9527_CR43","doi-asserted-by":"publisher","first-page":"1157","DOI":"10.1007\/s10458-014-9279-8","volume":"29","author":"MTJ Spaan","year":"2015","unstructured":"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\u20131185 (2015). doi: 10.1007\/s10458-014-9279-8","journal-title":"Auton. Agent. Multi-Agent Syst."},{"unstructured":"Stuart, A., Ord, K.J.: Kendall\u2019s Advanced Theory of Statistics, vol. 1. Distribution theory. Arnold, London (1994)","key":"9527_CR44"},{"issue":"3\/4","key":"9527_CR45","doi-asserted-by":"publisher","first-page":"364","DOI":"10.2307\/2332087","volume":"17","author":"LHC Tippett","year":"1925","unstructured":"Tippett, L.H.C.: On the extreme individuals and the range of samples taken from a normal population. Biometrika 17(3\/4), 364 (1925). doi: 10.2307\/2332087","journal-title":"Biometrika"},{"key":"9527_CR46","doi-asserted-by":"publisher","first-page":"140","DOI":"10.3141\/2467-15","volume":"2467","author":"A Zockaie","year":"2014","unstructured":"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\u2013148 (2014). doi: 10.3141\/2467-15","journal-title":"Transp. Res. Record: J. Transp. Res. Board"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-016-9527-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-016-9527-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-016-9527-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T19:50:03Z","timestamp":1498333803000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-016-9527-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,28]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["9527"],"URL":"https:\/\/doi.org\/10.1007\/s10472-016-9527-5","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"type":"print","value":"1012-2443"},{"type":"electronic","value":"1573-7470"}],"subject":[],"published":{"date-parts":[[2016,9,28]]}}}