Building Efficient Partial Plans using Markov Decision Processes

Pierre Laroche 1
1 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Markov Decision Processes (MDP) have been widely used as a framework for planning under uncertainty. They allow to compute optimal sequences of actions in order to achieve a given goal, accounting for actuators uncertainties. But algorithms classically used to solve MDPs are intractable for problems requiring a large state space. Plans are computed considering the whole state space, without using any knowledge about the initial state of the problem. In this paper, we propose a new technique to build partial plans for a mobile robot, considering only a restricted MDP, which contains a small set of states composing a path between the initial state and the goal state. To ensure good quality of the solution, the path has to be very similar to the one which would have been computed on the whole environment. We present in this paper a new method to compute partial plans, showing that representing the environment as a directed graph can be very helpful to find near-optimal paths. Partial plans obtained using this method are very similar to complete plans, and computing times are considerably reduced.
Type de document :
Communication dans un congrès
International Conference on Tools with Artificial Intelligence, 2000, none, 19 p, 2000
Liste complète des métadonnées

https://hal.inria.fr/inria-00099379
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:53:27
Dernière modification le : jeudi 11 janvier 2018 - 06:19:51

Identifiants

  • HAL Id : inria-00099379, version 1

Collections

Citation

Pierre Laroche. Building Efficient Partial Plans using Markov Decision Processes. International Conference on Tools with Artificial Intelligence, 2000, none, 19 p, 2000. 〈inria-00099379〉

Partager

Métriques

Consultations de la notice

191