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 :



Robot Talk Episode 126 – Why are we building humanoid robots?

  20 Jun 2025
In this special live recording at Imperial College London, Claire chatted to Ben Russell, Maryam Banitalebi Dehkordi, and Petar Kormushev about humanoid robotics.

Gearing up for RoboCupJunior: Interview with Ana Patrícia Magalhães

and   18 Jun 2025
We hear from the organiser of RoboCupJunior 2025 and find out how the preparations are going for the event.

Robot Talk Episode 125 – Chatting with robots, with Gabriel Skantze

  13 Jun 2025
In the latest episode of the Robot Talk podcast, Claire chatted to Gabriel Skantze from KTH Royal Institute of Technology about having natural face-to-face conversations with robots.

Preparing for kick-off at RoboCup2025: an interview with General Chair Marco Simões

and   12 Jun 2025
We caught up with Marco to find out what exciting events are in store at this year's RoboCup.

Interview with Amar Halilovic: Explainable AI for robotics

  10 Jun 2025
Find out about Amar's research investigating the generation of explanations for robot actions.

Robot Talk Episode 124 – Robots in the performing arts, with Amy LaViers

  06 Jun 2025
In the latest episode of the Robot Talk podcast, Claire chatted to Amy LaViers from the Robotics, Automation, and Dance Lab about the creative relationship between humans and machines.

Robot Talk Episode 123 – Standardising robot programming, with Nick Thompson

  30 May 2025
In the latest episode of the Robot Talk podcast, Claire chatted to Nick Thompson from BOW about software that makes robots easier to program.

Congratulations to the #AAMAS2025 best paper, best demo, and distinguished dissertation award winners

  29 May 2025
Find out who won the awards presented at the International Conference on Autonomous Agents and Multiagent Systems last week.



 

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


 












©2025.05 - Association for the Understanding of Artificial Intelligence