Abdelhadi Larach, Laboratory of Information Processing and Decision Support,
Sultan Moulay Slimane University, Faculty of sciences and Techniques, Beni-Mellal, Morocco
Cherki Daoui, Laboratory of Information Processing and Decision Support,
Sultan Moulay Slimane University, Faculty of sciences and Techniques, Beni-Mellal, Morocco
We consider Stochastic Shortest Path (SSP) Markov Decision Processes (MDPs) with dead ends and energy constraint. The objective is to find an optimal policy that maximizes the probability of reaching the target and minimizes the expected cost if the energy is sufficient. Firstly, we present a new Transformed SSP MDP that guarantees the convergence of the classical iterative algorithms and addresses the problem of energy-reachability. Secondly, we propose a topological algorithm based on a decomposition of the state space into some levels. In each level, a restricted SSP MDP is constructed and solved; the combined solution gives an admissible heuristic solution used as an initial point in the Pre-Gauss-Seidel Value Iteration (PGSVI) algorithm. Finally, an example of robot navigation in hexagonal grid’s environment will be presented to show the advantages of the TSSP MDP and the performance of the proposed topological solver.
Markov Decision Process, Graph theory, Stochastic Shortest Path, Value iteration, Decomposition technique
[1] D. J. White, “A survey of applications of Markov decision processes”, Journal of the operational research society, vol. 44, no 11, (1993): 1073-1096.
[2] A. Larach, C. Daoui, and M. Baslam, “A Markov Decision Model for Area Coverage in Autonomous Demining Robot”, International Journal of Informatics and Communication Technology (IJ-ICT), vol. 6, no 2, (2017): 105-116.
[3] A. R. Sfar, E. Natalizio, Y. Challal, “A Markov game privacy preserving model in retail applications”, In Selected Topics in Mobile and Wireless Networking (MoWNeT), 2017 International Conference on IEEE, (2017): 1-8.
[4] M. L. Puterman, “Markov decision processes: discrete stochastic dynamic programming”, John Wiley & Sons, (2014).
[5] D. P. Bertsekas, and J. N. Tsitsiklis, “An analysis of stochastic shortest path problems”, Mathematics of Operations Research, vol. 16, no 3, (1991): 580-595.
[6] B. Bonet, and H. Geffner, “Solving stochastic shortest-path problems with RTDP”, Universidad Simon Bolivar, Tech. Rep., (2002).
[7] B. Bonet and H. Geffner, “Labeled RTDP: Improving the Convergence of Real-Time Dynamic Programming”, In: ICAPS. (2003): 12-21.
[8] B. Bonet, and H. Geffner, “Faster heuristic search algorithms for planning with uncertainty and full feedback”, In: IJCAI. (2003): 1233-1238.
[9] A. Kolobov, D. S. Weld, H. Geffner, “Heuristic search for generalized stochastic shortest path MDPs”, In: Proceedings of the Twenty-First International Conference on International Conference on Automated Planning and Scheduling, AAAI Press, (2011): 130-137.
[10] D. S. Weld and A. Kolobov, “Stochastic Shortest Path MDPs with Dead Ends”, HSDIP, (2012): 78.
[11] F. Teichteil-Konigsbuch, “Stochastic safest and shortest path problems”, Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, AAAI Press, (2012): 1825-1831.
[12] A. Kolobov, D. S. Weld, “A theory of goal-oriented MDPs with dead ends”, arXiv preprint arXiv: 1210.4875, (2012).
[13] F. Trevizan, F. Teichteil-Konigsbuch, and S. Thiebaux, “Efficient solutions for stochastic shortest path problems with dead ends”, In: Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence, UAI, (2017): 11-15.
[14] R. E. Bellman, “Dynamic Programming”, Princeton University Press. Princeton, NJ, (1957).
[15] M. L. Littman, T. L. Dean, and L. P. Kaelbling, “On the complexity of solving Markov decision problems”, In: Proceedings of the Eleventh conference on Uncertainty in artificial intelligence. Morgan Kaufmann Publishers Inc., (1995): 394-402.
[16] K. W. Ross, and R. Varadrajan, “Multi-chain Markov decision processes with a sample path constraint: A decomposition approach”, Mathematics of Operations Research, vol. 16, no 1, (1991): 195-207.
[17] M. Abbad, and H. Boustique, “A decomposition algorithm for limiting average Markov decision problems”, Operations Research Letters, vol. 31, no 6, (2003): 473-476.
[18] M. Abbad and C. Daoui, “Hierarchical algorithms for discounted and weighted Markov decision processes”, Mathematical Methods of Operations Research, vol. 58, no 2, (2003): 237-245.
[19] C. Daoui, and M. Abbad, “One some algorithms for limiting average Markov decision processes”, Operations Research Letters, vol. 35, no 2, (2007): 261-266.
[20] C. Daoui, M. Abbad and M. Tkiouat, “Exact decomposition approaches for Markov decision processes: A survey”, Advances in Operations Research, vol. 2010, (2010).
[21] P. Dai, D. S. Weld and J. Goldsmith, “Topological value iteration algorithms”, Journal of Artificial Intelligence Research, vol. 42, (2011): 181-209.
[22] A. Larach, S. Chafik and C. Daoui, “Accelerated decomposition techniques for large discounted Markov decision processes”, Journal of Industrial Engineering International, vol. 13, no 4, (2017): 417-426.
[23] M. Sharir, “A Strong-connectivity Algorithm and its Applications in Data Flow analysis”, Computers & Mathematics with Applications, 7(1), (1981): 67-72.
APA:
Larach, A., & Daoui, C. (2019). A New Transformed Stochastic Shortest Path with Dead Ends and Energy Constraint. International Journal of Advanced Science and Technology (IJAST), ISSN: 2005-4238(Print); 2207-6360 (Online), NADIA, 129, 43-58. doi: 10.33832/ijast.2019.129.04.
MLA:
Larach, Abdelhadi, et al. “A New Transformed Stochastic Shortest Path with Dead Ends and Energy Constraint.” International Journal of Advanced Science and Technology, ISSN: 2005-4238(Print); 2207-6360 (Online), NADIA, vol. 129, 2019, pp. 43-58. IJAST, http://article.nadiapub.com/IJAST/Vol129/4.html.
IEEE:
[1] A. Larach, and C. Daoui, “A New Transformed Stochastic Shortest Path with Dead Ends and Energy Constraint.” International Journal of Advanced Science and Technology (IJAST), ISSN: 2005-4238(Print); 2207-6360 (Online), NADIA, vol. 129, pp. 43-58, Aug. 2019.
IJAST aims to facilitate and support research related to advanced science and technology and the applications. Our Journal provides a chance for academic and industry professionals to discuss recent progress in the areas of advanced science and technology.
