Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Đáp ứng một thời hạn: các đường đi ngắn nhất trên các đồ thị có hướng ngẫu nhiên và việc thu thập thông tin
Tóm tắt
Chúng tôi xem xét vấn đề của một tác nhân di chuyển qua một đồ thị có hướng với mục tiêu tối đa hóa xác suất đạt được một nút mục tiêu trước thời hạn được xác định. Chỉ có xác suất của thời gian di chuyển của các cạnh là được biết đến đối với tác nhân. Tác nhân phải cân bằng giữa các hành động di chuyển về phía mục tiêu và các độ trễ do các hành động cải thiện thông tin về thời gian di chuyển của các cạnh trong đồ thị. Chúng tôi mô tả mối quan hệ của vấn đề này với quy trình quyết định Markov một phần có thể quan sát tổng quát hơn. Hơn nữa, chúng tôi chỉ ra rằng nếu thời gian di chuyển của các cạnh là độc lập và đồ thị có hướng cơ sở là vô chu trình, một giải pháp vòng lặp đóng có thể được tính toán. Giải pháp này xác định xem có nên thực hiện một hành động di chuyển hay hành động thu thập thông tin tùy thuộc vào nút hiện tại, thời gian còn lại cho đến khi hết thời hạn, và thông tin về thời gian di chuyển của các cạnh. Chúng tôi trình bày kết quả từ hai nghiên cứu trường hợp, định lượng tính hữu ích của việc thu thập thông tin so với việc chỉ áp dụng các hành động di chuyển.
Từ khóa
#đồ thị có hướng ngẫu nhiên #thời hạn #quyết định Markov #thu thập thông tin #thời gian di chuyểnTài liệu tham khảo
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)
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)
Bonet, B.: Deterministic POMDPs revisited. In: Proc. of the 25th Conference on Uncertainty in Artificial Intelligence (UAI), pp. 59–66. Montreal, Canada (2009)
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)
Chen, A., Ji, Z.: Path finding under uncertainty. J. Adv. Transp. 39(1), 19–37 (2005)
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). doi:10.1080/13658816.2011.598133
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)
Dreyfus, S.E.: An appraisal of some shortest-path algorithms. Oper. Res. 17(3), 395–412 (1969). doi:10.1287/opre.17.3.395
Fan, Y., Kalaba, R., Moore J.E.I.: Arriving on time. J. Optim. Theory Appl. 127(3), 497–513 (2005). doi:10.1007/s10957-005-7498-5
Fan, Y., Nie, Y.: Optimal routing for maximizing the travel time reliability. Networks and Spatial Economics 6(3-4), 333–344 (2006). doi:10.1007/s11067-006-9287-6
Frank, H.: Shortest paths in probabilistic graphs. Oper. Res. 17(4), 583–599 (1969). doi:10.1287/opre.17.4.583
French, S., Insua, D.R. 2: Statistical decision theory, Kendall’s Library of Statistics, vol. 9. Wiley (2000)
Fu, L.: An adaptive routing algorithm for in-vehicle route guidance systems with real-time information. Transp. Res. B Methodol. 35, 749–765 (2001). doi:10.1016/S0191-2615(00)00019-9
Fu, L., Rilett, L.: Expected shortest paths in dynamic and stochastic traffic networks. Transp. Res. B Methodol. 32(7), 499–516 (1998). doi:10.1016/S0191-2615(98)00016-2
Gao, S., Chabini, I.: Optimal routing policy problems in stochastic time-dependent networks. Transp. Res. B Methodol. 40(2), 93–122 (2006). doi:10.1016/j.trb.2005.02.001
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). doi:10.1016/j.trc.2011.09.007
Hall, R.W.: The fastest path through a network with random time-dependent travel times. Transplant. Sci. 20(3), 182–188 (1986). doi:10.1287/trsc.20.3.182
Huang, H., Gao, S.: Optimal paths in dynamic networks with dependent random link travel times. Transp. Res. B Methodol. 46, 579–598 (2012). doi:10.1016/j.trb.2012.01.005
Kaelbling, L., Littman, M., Cassandra, A.: Planning and acting in partially observable stochastic domains. Artif. Intell. 101(1-2), 99–134 (1998)
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)
LaValle, S.M.: Planning algorithms. Cambridge University Press (2006)
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)
Loui, R.P.: Optimal paths in graphs with stochastic or multidimensional weights. Commun. ACM 26(9), 670–676 (1983). doi:10.1145/358172.358406
Melin, J., Lauri, M., Kolu, A., Koljonen, J., Ritala, R.: Cooperative sensing and path planning in a multi-vehicle environment (2015)
Miller-Hooks, E.: Adaptive least-expected time paths in stochastic, time-varying transportation and data networks. Networks 37(1), 35–52 (2001)
Miller-Hooks, E., Mahmassani, H.S.: Least expected time paths in stochastic, time-varying transportation networks. Transplant. Sci. 34(2), 198–215 (2000)
Murphy, K.P.: Machine Learning: A Probabilistic Perspective. The MIT Press (2012)
Murthy, I., Sarkar, S.: Stochastic shortest path problems with piecewise-linear concave utility functions. Manag. Sci. 44(11-part-2), S125–S136 (1998). doi:10.1287/mnsc.44.11.S125
von Neumann, J., Morgenstern, O.: Theory of games and economic behavior. Princeton University Press, Princeton (1947)
Nie, Y., Fan, Y.: Arriving-on-time problem: discrete algorithm that ensures convergence. Transp. Res. Record: J. Transp. Res. Board 1964, 193–200 (2006)
Nie, Y.M., Wu, X.: Shortest path problem considering on-time arrival probability. Transp. Res. B Methodol. 43(6), 597–613 (2009). doi:10.1016/j.trb.2009.01.008
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). doi:10.1016/j.tra.2011.10.008
Nikolova, E.: Approximation algorithms for reliable stochastic combinatorial optimization. In: Lecture Notes in Computer Science, vol. 6302, pp. 338–351. doi:10.1007/978-3-642-15369-3_26 (2010)
Nikolova, E., Karger, D.R.: Route planning under uncertainty: The canadian traveller problem. In: AAAI, pp. 969–974 (2008)
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). doi:10.1177/0278364910369861
Pan, Y., Sun, L., Ge, M.: Finding reliable shortest path in stochastic time-dependent network. Procedia - Social and Behavioral Sciences 96, 451–460 (2013). doi:10.1016/j.sbspro.2013.08.053
Papadimitriou, C.H., Tsitsiklis, J.N.: The complexity of markov decision processes. Math. Oper. Res. 12, 441–450 (1987). doi:10.1287/moor.12.3.441
Papadimitriou, C.H., Yannakakis, M.: Shortest paths without a map. Theor. Comput. Sci. 84(1), 127–150 (1991). doi:10.1016/0304-3975(91)90263-2
Polychronopoulos, G., Tsitsiklis, J.: Stochastic shortest path problems with recourse. Networks 27(2), 133–143 (1996)
Porta, J., Vlassis, N., Spaan, M., Poupart, P.: Point-based value iteration for continuous POMDPs. J. Mach. Learn. Res. 7, 2329–2367 (2006)
Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, New York (1994)
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). doi:10.1016/j.trc.2011.05.009
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). doi:10.1007/s10458-014-9279-8
Stuart, A., Ord, K.J.: Kendall’s Advanced Theory of Statistics, vol. 1. Distribution theory. Arnold, London (1994)
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
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). doi:10.3141/2467-15