Anytime RRBT for Handling Uncertainty and Dynamic Objects

by Hyunchul Yang, Jongwoo Lim, and Sung-Eui Yoon
IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2016

Runtime results of our anytime RRBT method. This simulation environment has the space of 5x5(m^2). We show an initially computed path for the robot (a). (b), (c), and (d) show updated trajectories while following the prior path. The robot can sense the environment only in the green region. Dotted lines are committed trajectories, and the goal is shown as the yellow region. The circles represent the uncertainty; bigger ones mean higher uncertainty.

Intersection scene with 3x3(m^2) size. A purple obstacle moves toward top direction straightly with the constant velocity. The robot encounters the obstacle after a few seconds, and finds paths to the goal region(orange), while avoiding the obstacle. Our method w/o UVO avoids the obstacle with zig-zag paths (a), while ours w/ UVO reduces the speed to avoid collisions, resulting in smooth paths and better runtime performance (b).

Histograms of path lengths in the scene of Fig. 6. Our method w/UVO achieves shorter path lengths over our method w/o UVO.

AnytimeRRBT Crowd scene
AnytimeRRBT intersection scene with UVO
AnytimeRRBT intersection scene without UVO


We present an efficient anytime motion planner for mobile robots that considers both other dynamic obstacles and uncertainty caused by various sensors and low-level controllers. Our planning algorithm, which is an anytime extension of the Rapidly-exploring Random Belief Tree (RRBT), maintains the best possible path throughout the robot execution, and the generated path gets closer to the optimal one as more computation resources are allocated. We propose a branch-andbound method to cull out unpromising areas by considering path lengths and uncertainty. We also propose an uncertaintyaware velocity obstacle as a simple local analysis to avoid dynamic obstacles efficiently by finding a collision-free velocity. We have tested our method with three benchmarks that have non-linear measurement regions or potential collisions with dynamic obstacles. By using the proposed methods, we achieve up to five times faster performance given a fixed path cost.


Paper: PDF (1.1MB)
Poster: PDF(0.3MB)
AnytimeRRBT Source Code: ZIP file(0.2MB) / Github Page

Dept. of Computer Science
373-1 Guseong-dong, Yuseong-gu, Daejeon, 305-701
South Korea
sglabkaist dot gmail dot com