A New Decomposition Technique for Solving Markov Decision Processes

Pierre Laroche; Yann Boniface; René Schott

inria-00101093, version 1

A New Decomposition Technique for Solving Markov Decision Processes

Pierre Laroche ()^a^, 1, Yann Boniface ()^b^, 2, René Schott ^3, 4

Symposium on Applied Computing - SAC'2001 (2001) 5 p

Abstract: In this paper, we present a new tool for automatically solving Markov Decision Processes. Using a predefined partition o fthe MDP, a directed graph is built to decompose the global MDP into small local MDPs which are independently solved. An approximate solution for the global MDP is obtained using local solutions. Our approach has been tested on a mobile robotics application. It allows near-optimal solutions to be obtained in significantly reduced time. We also present preliminary results concerning a parallel implementation.

a – UNIVERSITE DE METZ
b – UNIVERSITE NANCY 2
1: Laboratoire d'Informatique Théorique et Appliquée (LITA (EA3097))
Université Paul Verlaine - Metz
2: CORTEX (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
3: Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
4: Institut Elie Cartan Nancy (IECN)
CNRS : UMR7502 – INRIA – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)

inria-00101093, version 1
http://hal.inria.fr/inria-00101093
oai:hal.inria.fr:inria-00101093
From: Publications Loria <>
Submitted on: Tuesday, 26 September 2006 14:56:27
Updated on: Monday, 11 June 2007 15:37:31

See detailed view

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Peer-reviewed conferences/proceedings</head>
<biblStruct type="inproceedings" xml:id="inria-00101093"><analytic>
<author><persName><forename>Pierre</forename><surname>Laroche</surname></persName>
<affiliation>
<orgName type="laboratory">LITA (EA3097)</orgName>
<orgName type="team">Laboratoire d'Informatique Théorique et Appliquée</orgName>
<country>FR</country>
<orgName type="institution">Université Paul Verlaine - Metz</orgName>
</affiliation>
</author>
<author><persName><forename>Yann</forename><surname>Boniface</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">CORTEX</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>René</forename><surname>Schott</surname></persName>
<affiliation>
<orgName type="laboratory">LORIA</orgName>
<orgName type="team">Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">IECN</orgName>
<orgName type="team">Institut Elie Cartan Nancy</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7502</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<title type="main" level="a">A New Decomposition Technique for Solving Markov Decision Processes</title></analytic><monogr><meeting>Symposium on Applied Computing - SAC'2001</meeting><imprint><publisher>none</publisher><pubPlace><settlement>Las Vegas</settlement><country> USA</country></pubPlace><biblScope type="publicationDate">2001-00-00</biblScope><biblScope type="pp">5 p</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00101093</idno></biblStruct>
</listBibl>
</listBibl>