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 43 – Maitreyee Wairagkar

In this week's episode of the Robot Talk podcast, host Claire Asher chatted to Maitreyee Wairagkar from the University of California all about neurotechnology, artificial intelligence, and assistive robotics.
31 March 2023, by

Education and healthcare are set for a high-tech boost

The enhancement of human-machine interaction is expected to bring big improvements in support for learning and access to healthcare.
29 March 2023, by

Robot Talk Episode 42 – Thom Kirwan-Evans

In this week's episode of the Robot Talk podcast, host Claire Asher chatted to Thom Kirwan-Evans from Origami Labs all about computer vision, machine learning, and robots in industry.
25 March 2023, by

Resilient bug-sized robots keep flying even after wing damage

New repair techniques enable microscale robots to recover flight performance after suffering severe damage to the artificial muscles that power their wings.
23 March 2023, by

How drones for organ transportation are changing the healthcare industry

The healthcare drone industry has witnessed a dramatic surge in the last couple of years. In 2020, the market grew 30% and is expected to grow from $254 million in 2021 to $1,5 billion in 2028.
21 March 2023, by





©2021 - ROBOTS Association


 












©2021 - ROBOTS Association