TiMDPpoly : an Improved Method for Solving Time-dependent MDPs

We introduce TiMDPpoly, an algorithm designed to solve planning problems with durative actions, under probabilis-tic uncertainty, in a non-stationary, continuous-time con-text. Mission planning for autonomous agents such as plan-etary rovers or unmanned aircrafts often correspond to such time-dependent planning problems. Modeling these prob-lems can be cast through the framework of Time-dependent Markov Decision Processes (TiMDPs). We analyze the TiMDP optimality equations in order to exploit their prop-erties. Then, we focus on the class of piecewise polynomial models in order to approximate TiMDPs, and introduce sev-eral algorithmic contributions which lead to the TiMDPpoly algorithm for TiMDPs. Finally, our approach is evaluated on an unmanned aircraft mission planning problem and on an adapted version of the well-known Mars rover domain.