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 :

How robots learn to hike

A new control approach that enables a legged robot, called ANYmal, to move quickly and robustly over difficult terrain.
20 January 2022, by

How robots and bubbles could soon help clean up underwater litter

Everyone loves to visit the seaside, whether to enjoy the physical benefits of an exhilarating swim or simply to relax on the beach and catch some sun. But these simple life affirming pleasures are easily ruined by the presence of litter, which if persistent can have a serious negative impact on both the local environment and economy. However, help is at hand to ensure the pristine nature of our coastlines.
19 January 2022, by

Maria Gini wins the 2022 ACM/SIGAI Autonomous Agents Research Award

Congratulations to Maria Gini on winning this prestigious award, recognising her research and leadership in the field of robotics and multi-agent systems.
18 January 2022, by

UN fails to agree on ‘killer robot’ ban as nations pour billions into autonomous weapons research

Given the pace of research and development in autonomous weapons, the U.N. meeting might have been the last chance to head off an arms race.
16 January 2022, by

Science Magazine robot videos 2021

A compilation of Science Magazine videos featuring robotics research that were released during last year.
14 January 2022, by

CBQ: Commercial-grade Autonomous Mowers, Safety, and Dogfooding | Sense Think Act Podcast #11

In this episode, Audrow Nash speaks to Charles Brian Quinn (aka, CBQ), CEO and a Co-Founder of Greenzie. Greenzie make an autonomous driving system for commercial lawn mowers. We talk about Greenzie's...
11 January 2022, by and

©2021 - ROBOTS Association


©2021 - ROBOTS Association