Exploration using Voronoi diagrams

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 :

Flocks of assembler robots show potential for making larger structures

Researchers make progress toward groups of robots that could build almost anything, including buildings, vehicles, and even bigger robots.
25 November 2022, by

Holiday robot wishlist for/from Women in Robotics

Are you looking for a gift for the women in robotics in your life? Or the up and coming women in robotics in your family? Perhaps these suggestions from our not-for-profit Women in Robotics organization will inspire!
24 November 2022, by and

TRINITY, the European network for Agile Manufacturing

The Trinity project is the magnet that connects every segment of agile with everyone involved, creating a network that supports people, organisations, production and processes.
20 November 2022, by

Fighting tumours with magnetic bacteria

Researchers at ETH Zurich are planning to use magnetic bacteria to fight cancerous tumours. They have now found a way for these microorganisms to effectively cross blood vessel walls and subsequently colonise a tumour.
19 November 2022, by

Combating climate change with a soft robotics fish

We have fabricated a 3D printed, cable-actuated wave spring tail made from soft materials that can drive a small robot fish.
17 November 2022, by

#IROS2022 best paper awards

Here we bring you the papers that received an award this year at IROS in case you missed them.
14 November 2022, by

©2021 - ROBOTS Association


©2021 - ROBOTS Association