A New Transformed Stochastic Shortest Path with Dead Ends and Energy Constraint

Abstract

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.