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





Related posts :



Robots to the rescue: miniature robots offer new hope for search and rescue operations

  09 Sep 2025
Small two-wheeled robots, equipped with high-tech sensors, will help to find survivors faster in the aftermath of disasters.

#IJCAI2025 distinguished paper: Combining MORL with restraining bolts to learn normative behaviour

and   04 Sep 2025
The authors introduce a framework for guiding reinforcement learning agents to comply with social, legal, and ethical norms.

Researchers are teaching robots to walk on Mars from the sand of New Mexico

  02 Sep 2025
Researchers are closer to equipping a dog-like robot to conduct science on the surface of Mars

Engineering fantasy into reality

  26 Aug 2025
PhD student Erik Ballesteros is building “Doc Ock” arms for future astronauts.

RoboCup@Work League: Interview with Christoph Steup

and   22 Aug 2025
Find out more about the RoboCup League focussed on industrial production systems.

Interview with Haimin Hu: Game-theoretic integration of safety, interaction and learning for human-centered autonomy

and   21 Aug 2025
Hear from Haimin in the latest in our series featuring the 2025 AAAI / ACM SIGAI Doctoral Consortium participants.

AIhub coffee corner: Agentic AI

  15 Aug 2025
The AIhub coffee corner captures the musings of AI experts over a short conversation.

Interview with Kate Candon: Leveraging explicit and implicit feedback in human-robot interactions

and   25 Jul 2025
Hear from PhD student Kate about her work on human-robot interactions.



 

Robohub is supported by:




Would you like to learn how to tell impactful stories about your robot or AI system?


scicomm
training the next generation of science communicators in robotics & AI


 












©2025.05 - Association for the Understanding of Artificial Intelligence