news    views    talk    learn    |    about    contribute     republish     crowdfunding     archives     events

Exploration using Voronoi diagrams

September 21, 2010

How can a robot explore and make maps of new environments while avoiding obstacles?

One way is to let the robot remain at equal distance from its two nearest obstacles, thereby navigating exactly in between them (Voronoi edge). If you follow the trajectory performed by the robot, it might look something like the blue line in the figure below.

The Voronoi diagram is shown in blue, intersections are in green and obstacles are in red.

However, challenges arise when the robot is at equal distance from more than two obstacles (intersection). In those cases, the robot needs to decide between which two obstacles it should navigate next. Ideally, you would want the robot to choose its way so that it eventually explores the entire environment.

For this purpose, Kim et al. propose two algorithms that allow the robot to track visited edges and subsequently decide on new edges to explore. By the end of the exploration, the robot will have constructed a topological map of its entire environment based on Voronoi edges (i.e. a Voronoi diagram).

Experiments shown below were conducted with a Khepera III robot equipped with Infrared (IR) sensors for distance measurement and capable of localizing based on odometry. Results show the correct exploration and mapping of the environment.

Voronoi diagram built by a Khepera III robot.

Sabine Hauert is lecturer at the Bristol Robotics Laboratory and co-founder of Robohub, the Robots Podcast and the Autonomous Robots blog... read more

Other articles on similar topics:

comments powered by Disqus

Kickstart Accelerator
April 17, 2017

Are you planning to crowdfund your robot startup?

Need help spreading the word?

Join the Robohub crowdfunding page and increase the visibility of your campaign