Rapidly-exploring Random Belief Trees for motion planning under uncertainty

By Adam Bry, Nicholas A. Roy. 2011

501 citations recorded by the source corpus.

In this paper we address the problem of motion planning in the presence of state uncertainty, also known as planning in belief space. The work is motivated by planning domains involving nontrivial dynamics, spatially varying measurement properties, and obstacle constraints. To make the problem tractable, we restrict the motion plan to a nominal trajectory stabilized with a linear estimator and controller. This allows us to predict distributions over future states given a candidate nominal trajectory. Using these distributions to ensure a bounded probability of collision, the algorithm incrementally constructs a graph of trajectories through state space, while efficiently searching over candidate paths through the graph at each iteration. This process results in a search tree in belief space that provably converges to the optimal path. We analyze the algorithm theoretically and also provide simulation results demonstrating its utility for balancing information gathering to reduce uncertainty and finding low cost paths.

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

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

Deep Drone Racing: Learning Agile Flight in Dynamic Environments (2018, background): “Note that moving gates break the main assumption of traditional high-speed navigation approaches [1, 9], specifically that the trajectory can be pre-planned in a static world.”
Path planning in GPS-denied environments via collective intelligence of distributed sensor networks (2016, background): “Some work in sampling-based motion planning literature for planning with uncertainties could be found in Levine, Luders, and How (2010), Bry, Bachrach, and Roy (2012), Bry and Roy (2011), Li, Li, Cheng, and Song (2014).”
Sampling-based robotic information gathering algorithms (2014, methodology): “From Lemma 1 in Bry and Roy (2011), the following properties are necessary for all feasible trajectories to be generated in an RRBT graph: (1) an inﬁnitely dense connected graph must be created around each point in X free , and (2) all trajectories must be of ﬁnite length.”
State estimation for aggressive flight in GPS-denied environments using onboard sensing (2012, background): “In addition to providing good estimates of the system mean, the state estimation algorithm should also accurately represent uncertainty so that control and planning algorithms can be appropriately cautious around obstacles and other state constraints [3].”
Learning high-speed flight in the wild (2021, methodology): “Some works tackle only perception and build high-quality maps from imperfect measurements [5–9], whereas others focus on planning without considering perception errors [10–13].”
Advanced closed loop visual navigation for micro aerial vehicles (2014, methodology): “The search radius r around vnew for near vertices is determined by r = (log(n)/n)(1/d) according to (Bry and Roy, 2011; Karaman and Frazzoli, 2010), where n is the number of state vertices and d the dimension of the sampled state xs.”
Sampling-Based Robot Motion Planning: A Review (2014, background): “Similar uncertainty considerations are added to RRT* framework by Rapidly-exploring Random Belief Trees (RRBT) [220], [221].”
Sampling-based algorithms for optimal motion planning (2011, methodology): “Algorithms based on the RRG were used to solve belief-space planning problems in Bry and Roy (2011).”
Funnel libraries for real-time robust feedback motion planning (2016, unknown): “Similarly, other approaches for belief space planning (Agha-Mohammadi et al., 2014; Berg et al., 2012; Bry and Roy, 2011; Patil et al., 2015; Platt et al., 2010; Prentice and Roy, 2007) also approximate the belief state as a Gaussian distribution over state space (however, see Platt et al.”