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

By Sam Prentice, Nicholas A. Roy. Int. J. Robotics Res., 2009

349 citations recorded by the source corpus.

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.

Subfields: Aerospace Engineering, Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/d32a2533e5eadcd408e8a9ff4a2947ab3b1981a5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

LQG-MP: Optimized path planning for robots with motion uncertainty and imperfect state information (2010, background): “Existing planners that are most directly related to LQG-MP take into account the available sensing capability to maximize the probability of arriving at the goal or to minimize expected cost [9, 12, 26, 27, 29].”
Advanced closed loop visual navigation for micro aerial vehicles (2014, methodology): “Eventually, Bachrach et al. (2012) showed operation of a MAV with a RGBD based visual odometry approach and planning in information space based on probabilistic roadmaps (PRM) (Prentice and Roy, 2009), having the Kinect fully within the control loop.”
Deliberation for autonomous robots: A survey (2017, neutral): “, [171, 175].”
Sampling-based algorithms for optimal motion planning (2011, background): “…motion planning in high-dimensional spaces, and attracted significant attention over the last decade, including very recent work (see, e.g., Stilman et al. 2007; Berenson et al. 2008; Yershova and LaValle 2008; Prentice and Roy 2009; Koyuncu et al. 2010; Luders et al. 2010; Tedrake et al. 2011).”
A Survey on Active Simultaneous Localization and Mapping: State of the Art and New Frontiers (2022, methodology): “[238] C. Richter, W. Vega-Brown, and N. Roy, “Bayesian learning for safe high-speed navigation in unknown environments,” in Robotics Research.”