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 :



Interview with Dautzenberg Roman: #IROS2023 Best Paper Award on Mobile Manipulation sponsored by OMRON Sinic X Corp.

The award-winning author describe their work on an aerial robot which can exert large forces onto walls.
19 November 2023, by

Robot Talk Episode 62 – Jorvon Moss

In the latest episode of the Robot Talk podcast, Claire chatted to Jorvon (Odd-Jayy) Moss from Digikey about making robots at home, and robot design and aesthetics.
17 November 2023, by

California is the robotics capital of the world

In California, robotics technology is a small fish in a much bigger technology pond, and that tends to conceal how important Californian companies are to the robotics revolution.
12 November 2023, by

Robot Talk Episode 61 – Masoumeh Mansouri

In the latest episode of the Robot Talk podcast, Claire chatted to Masoumeh (Iran) Mansouri from the University of Birmingham about culturally sensitive robots and planning in complex environments.
10 November 2023, by

The 5 levels of Sustainable Robotics

Robots can solve the UN SDGs and not just via the application area.
08 November 2023, by

Using language to give robots a better grasp of an open-ended world

By blending 2D images with foundation models to build 3D feature fields, a new MIT method helps robots understand and manipulate nearby objects with open-ended language prompts.
06 November 2023, by





©2021 - ROBOTS Association


 












©2021 - ROBOTS Association