This Article Full Text (PDF) All Versions of this Article: 0278364909341659v1 0278364909341659v2 28/11-12/1448    most recent References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Scopus Google Scholar Articles by Prentice, S. Articles by Roy, N. Social Bookmarking                         What's this?

The Belief Roadmap: Efficient Planning in Belief Space by Factoring the Covariance

Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, USA, prentice{at}mit.edu

Nicholas Roy

Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA 02139, USA, nickroy{at}mit.edu

When a mobile agent does not know its position perfectly, incorporating the predicted uncertainty of future position estimates into the planning process can lead to substantially better motion performance. However, planning in the space of probabilistic position estimates, or belief space, can incur a substantial computational cost. In this paper, we show that planning in belief space can be performed efficiently for linear Gaussian systems by using a factored form of the covariance matrix. This factored form allows several prediction and measurement steps to be combined into a single linear transfer function, leading to very efficient posterior belief prediction during planning. We give a belief-space variant of the probabilistic roadmap algorithm called the belief roadmap (BRM) and show that the BRM can compute plans substantially faster than conventional belief space planning. We conclude with performance results for an agent using ultra-wide bandwidth radio beacons to localize and show that we can efficiently generate plans that avoid failures due to loss of accurate position estimation.

Key Words: planning under uncertainty • motion planning • probabilistic • state estimation

This version was published on November 1, 2009

The International Journal of Robotics Research, Vol. 28, No. 11-12, 1448-1465 (2009)
DOI: 10.1177/0278364909341659


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?