2019/01/04 by Shoubhik Debnath, Lantao Liu, Debnath, Shoubhik +3
Computer Science · #Advanced Software Engineering Methodologies #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Formal Methods in Verification #Reinforcement Learning in Robotics #Robotics (cs.RO) #Software Reliability and Analysis Research
paper · pdf · doi:10.48550/arxiv.1901.01229
openalex publication_date 2019/01/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A new mechanism for efficiently solving the Markov decision processes (MDPs)\nis proposed in this paper. We introduce the notion of reachability landscape\nwhere we use the Mean First Passage Time (MFPT) as a means to characterize the\nreachability of every state in the state space. We show that such reachability\ncharacterization very well assesses the importance of states and thus provides\na natural basis for effectively prioritizing states and approximating policies.\nBuilt on such a novel observation, we design two new algorithms -- Mean First\nPassage Time based Value Iteration (MFPT-VI) and Mean First Passage Time based\nPolicy Iteration (MFPT-PI) -- that have been modified from the state-of-the-art\nsolution methods. To validate our design, we have performed numerical\nevaluations in robotic decision-making scenarios, by comparing the proposed new\nmethods with corresponding classic baseline mechanisms. The evaluation results\nshowed that MFPT-VI and MFPT-PI have outperformed the state-of-the-art\nsolutions in terms of both practical runtime and number of iterations. Aside\nfrom the advantage of fast convergence, this new solution method is intuitively\neasy to understand and practically simple to implement.\n