Sunday, April 01, 2007

Coordination of Multi-Robot Exploration

The goal of exploration is to cover an unknown environment in a minimum of time. The key problem with a team of robots is to allocate efficient target locations for each of them, so that they can parallel explore different regions.

An approach for exploration with unlimited communication abilities is used in [1]: During the exploration a global map of the environment is built (known/unknown and obstacle free/unfree areas are mapped). The decision for which of the frontier locations (frontier to an unknown location) are allocated as the next targets is evaluated from two values: The cost of reaching this location (simple distance) and the utility. Whenever one robot chooses a location as a target, the utility of this and the adjacent locations are reduced to all other robots. Consequently an attractive location loses its attractiveness when it is targeted and other robots can explore other regions.

Results: This relative simple approach is needed to introduce quickness and robustness into the system. In real world experiments good results were achieved (see Figure: Coordinated exploration by three robots in a real world experiment; starting point is the left upper corner; Figure from [1]). This multi-robot system is more redundant, more fault-tolerant and faster in the exploration then a single robot.

Further works will deal with limited communication abilities, unknown relative positions of the robots, changing environments and dysfunctions of robots.

Reference: [1] W.Burgard, M.Moos, C.Stachniss, F.Schneider: "Coordinate Multi-Robot Exploration", International Conference on Robotics and Automation, IEEE, 2000,

NT061637N Ireneus Wior


Industry said...

This technology can be applied to the Hopping microbots for exploring planetary surfaces. This way the microbots can organize themselves so as to explore more area and avoid potential traps such as ravines or crevices. A microbot stuck in such a place can send a signal that can make it undesirable to all other microbots. Some prior information of the surface being explored can be obtained by using Hubble telescope.

Industry said...

Sorry forgot to mention my name:

Pavan U045965E

dars.edutainment said...

How the robots learn? Through reinforcement learning or other kind of machine learning?

I personally think that in this case reinforcement learning can be used. Usually for a multi agent problem, how to coordinate them is very important. Can anyone suggest some algorithm that can perform well in this case?

Liu Ming

dars.explore said...

Htun Lin Oo U059294W

It seems the communication is very critical for operation this method of exploration, especially for real-time updating of the robots' coordinates and statuses. I expect that some kind of rough partitioning of the domain for exploration should be done before hand, even when absolutely nothing is known about the region. That way, the robots will be less dependent on being able to communicate in real-time in order for the exploration method to be efficient. Just a thought...

Industry said...

Isn't that how search and rescue operations are also conducted by the commandos, may be in the future, these robots might replace them.