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
AnytimeRRBT Crowd scene
AnytimeRRBT intersection scene with UVO
AnytimeRRBT intersection scene without UVO
Abstract
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.
