Robohub.org
 

Exploration using Voronoi diagrams


by
21 September 2010



share this:

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 President of Robohub and Associate Professor at the Bristol Robotics Laboratory
Sabine Hauert is President of Robohub and Associate Professor at the Bristol Robotics Laboratory

            AUAI is supported by:



Subscribe to Robohub newsletter on substack



Related posts :

Robot swarms trained by trial and error in simulation keep working on real robots

  17 Nov 2026
Researchers have developed a new approach to reinforcement learning that helps robot swarms, allowing behaviours learned in simulation to transfer reliably to real-world robots.

Watch the IROS 2026 plenary and keynote talks

  16 Nov 2026
Catch up on the invited presentations from the International Conference on Intelligent Robots and Systems.

Robot Talk Episode 170 – Robots in the real world, with Daniela Shchegelskaya

  13 Nov 2026
In the latest episode of the Robot Talk podcast, Claire chatted to Daniela Shchegelskaya from the University of Twente about getting robots to operate reliably in safety-critical environments.

AI100 report released: embodied AI highlighted as grand challenge

  11 Nov 2026
Embodied AI is listed as one of the most inspiring open grand challenges.

AIhub coffee corner: Are humanoids the future of embodied AI?

  09 Nov 2026
The AIhub coffee corner captures the musings of AI experts over a short conversation.

Robot Talk Episode 169 – Robot sensing inspired by nature, with Dexter Shepherd

  06 Nov 2026
In the latest episode of the Robot Talk podcast, Claire chatted to Dexter Shepherd from the University of Sussex about using artificial intelligence to help robots understand and adapt to their environment.

Robots in society, business and culture: October 2026

We showcase a selection of robotics stories from society, business, research and culture.

Muscle coordination can be mimicked by electric motors – it could lead to improved robots

  02 Nov 2026
Researchers built a physical model using ordinary electric motors to try and simulate how muscles may perform tasks.


↑


AUAI is supported by:







Subscribe to Robohub newsletter on substack




 















©2026.05 - Association for the Understanding of Artificial Intelligence