Autonomous Systems



  Brooks, A.
Parametric POMDPs for planning in continuous state spaces
PhD thesis, The University of Sydney, Jan, 2007

This thesis is concerned with planning and acting under uncertainty in
partially-observable continuous domains. In particular, it focusses
on the problem of mobile robot navigation given a known map. The
dominant paradigm for robot localisation is to use Bayesian estimation
to maintain a probability distribution over possible robot poses. In
contrast, control algorithms often base their decisions on the
assumption that a single state, such as the mode of this distribution,
is correct. In scenarios involving significant uncertainty, this can
lead to serious control errors. It is generally agreed that the
reliability of navigation in uncertain environments would be greatly
improved by the ability to consider the entire distribution when
acting, rather than the single most likely state.

The framework adopted in this thesis for modelling navigation problems
mathematically is the Partially Observable Markov Decision Process
(POMDP). An exact solution to a POMDP problem provides the optimal
balance between reward-seeking behaviour and information-seeking
behaviour, in the presence of sensor and actuation noise.
Unfortunately, previous exact and approximate solution methods have
had difficulty scaling to real applications.

The contribution of this thesis is the formulation of an approach to
planning in the space of continuous parameterised approximations to
probability distributions. Theoretical and practical results are
presented which show that, when compared with similar methods from the
literature, this approach is capable of scaling to larger and more
realistic problems.

In order to apply the solution algorithm to real-world problems, a
number of novel improvements are proposed. Specifically, Monte Carlo
methods are employed to estimate distributions over future
parameterised beliefs, improving planning accuracy without a loss of
efficiency. Conditional independence assumptions are exploited to
simplify the problem, reducing computational requirements.
Scalability is further increased by focussing computation on likely
beliefs, using metric indexing structures for efficient function
approximation. Local online planning is incorporated to assist global
offline planning, allowing the precision of the latter to be decreased
without adversely affecting solution quality.

Finally, the algorithm is implemented and demonstrated during
real-time control of a mobile robot in a challenging navigation task.
We argue that this task is substantially more challenging and
realistic than previous problems to which POMDP solution methods have
been applied. Results show that POMDP planning, which considers the
evolution of the entire probability distribution over robot poses,
produces significantly more robust behaviour when compared with a
heuristic planner which considers only the most likely states and

Download    PDF full text (24.29M)

Associated Projects   

Copyright Notice & Disclaimer

The Centre for Autonomous Systems finished at the end of 2010. This web site is kept as an example of the work undertaken by the Centre between 2003 and 2010.

This web site is hosted by the Australian Centre for Field Robotics. Please check the ACFR web site for the latest work in this and similar fields of research.