[Review] A Multi-Agent Cooperative Exploration Strategy

March 13, 2019 · 4 minute read

Article Review 13-03-2018

Cooperative Frontier-Based Exploration Strategy for Multi-Robot System

Mahdoui, Nesrine, Vincent Frémont, and Enrico Natalizio. 2018, 13th Annual Conference on System of Systems Engineering (SoSE). IEEE, 2018.

Aims of the paper

This paper intends to present one solution to the problem of coordination and communication between multiple robots when exploring an unknown environment. This is achieved by minimising data transfer with a group computation like dynamic which also includes elements of fault tolerance.

Paper Summary

They begin by discussing the nature of the “cooperation” they wish to implement into their exploration system. They seek to find a dynamic method of cooperation where individual agents together decide their actions during the execution of a task. Their use of group leaders for local decision making also implies a weakly centralised hierarchy as the leader is not predefined and often changes throughout the mission.

The problem essentially breaks down into two parts:

  1. Frontier Point Selection and assignment
  2. Group Communication and interaction

During exploration, the drones are clustered up by communication range. A leader is chosen as the drone with the owed id and are in charge of synchronising all the other drones with are the explorers. The leader takes in all of the frontier points from all its explorers and decides on the final candidate frontier points and assigns them to the explorers. If an explorer does not receive any message from a leader, it finds and assigns its own frontier points to explore.

This work uses a 3D voxel map, but uses a technique where the frontier points are selected from each MAVs local map and not a global map. This means that only a stream of frontier points are required to be sent to the leader for processing and not the entire map. The frontier points are combined to establish the cumulative frontier with overlapping frontiers removed. The frontier points are then assigned to each MAV by increase information gain (number of unexplored voxels) while reducing the cost to get to the point.

Once a point has been assigned, each MAV independently find shortest path through explored space to it. Unfortunately trajectories may overlap with others due to their being no shared global map. A discussion follows explaining the communication interactions depending on the type of communication. Specific types of data being broadcast lead to different behaviours. Also, as all drones start as their own leaders, loss of connectivity does not break the system as the drone revers back to leader status and is thus also fault tolerant to some degree. The method of only sending frontier points drastically decreases network throughput and onboard memory requirements.

Evaluation is done only via simulation in two circumstances. The first is evaluated by coverage on a model of a house with up to 3 drones. The results here are that exploration time is considerable reduced (although the workload is not evenly spread between MAVs with some sitting idle and overlapping exploration still exists) as well as distance travelled for each MAV is reduced. The finish condition is that no frontier points are remaining. The second simulation attempts to recreate the Ad-HOC network which emulates the set up if this were to be implemented in real life. This includes emulating lag times and network disconnects and goes to show this methods scalability and fault tolerance. It can be seen that the data transferred is much reduced compared to sending full occupancy grids.

Paper Review

An interesting paper which presents a different approach to the same frontier exploration problem. It does well to present the previous works and method, and I am swayed by some of the results in their evaluation. However, I feel it does feel short in terms of organisation, explanation and detail. I found myself confusing their work with previous work during section 4’s explanation of their method as they explained their methods in contrast to others instead of directly which obfuscated many points. Also I felt that more detail was required throughout. More mathematical detail in terms of modelling and analysis of emergent behaviour would have made their method more convincing. I was disappointed at the lack of explanation at the computation that the Leader makes to select the next frontier points as this is glossed over in section 4.B. As a result of the above, I then found many of the diagrams and tables uninformative due to the lack of explanations. Similar details can be sad about their analysis of the experiments and simulations they conducted and it is hard to judge the effectiveness of their method.

Nevertheless, they did somewhat achieve their aims of presenting a new method for cooperative frontier exploration. Although the execution of the paper is a little lacking, I do think that the content has merit and is worth further exploration. As such I would recommend this paper to those who are interested in exploration methods.