Real-time motion planning in unknown environment: Voronoi-based StRRT (Spatiotemporal RRT)

For a robot to move autonomously in an unknown dynamic environment, a real-tune motion planning is necessary. When the motions of obstacles are unknown, motion planning is usually performed by virtually expanding the area obstacles occupy. However, there are many cases in which the adequate solution trajectory cannot be obtained due to inadequate expansion. Another approach would be to determine candidates of the safe trajectory from the layout of obstacles as a generalized Voronoi diagram and then randomly search for an appropriate trajectory. However, this requires many calculations. It may be sufficient if a local generalized Voronoi diagram is available for limiting the sampling area. Based on this idea, this paper proposes a Voronoi-based StRRT composed of an StRRT subjected to biasing extraction of sample points toward the border of a generalized Voronoi diagram and show the possibilities of this method to plan safe trajectories.