Topological Orders Based Planning for Solving POMDPs

Jilles steeve Dibangoye, Brahim Chaib-draa, Abdel-illah Mouaddib

Although partially observable Markov decision processes ($\textsc{pomdp}$s) have received significant attention in past years, to date, solving problems of realistic order of magnitude remains a serious challenge. In this context, techniques that accelerate fundamental algorithms have been a main focus of research. Among them prioritized solvers suggest solutions to the problem of ordering backup operations. Prioritization techniques for ordering the sequence of backup operations considerably reduce the number of backups needed, but involve significant overhead. This paper introduces a novel prioritized method, namely topological order-based planning (\textsc{top}), that exploits causal relations between states to deal with two key issues. First, \textsc{top} detects the structure of $\textsc{pomdp}$s as a means of overcoming both the dimensionality and the history curses. Second, it circumvents the problem of unnecessary backups and builds approximate solutions based on a topological order induced by the underlying structure. Empirical experiments prove that \textsc{top} is competitive with the best techniques on general domains, and can perform significantly better on layered ones.

Subjects: 1.11 Planning; 12.1 Reinforcement Learning

Submitted: May 5, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.