We consider the task of exploring a hazardous terrain using a group of autonomous agents. The area is divided into a grid of square cells, whose size depends on the sensing coverage of the agent. When an agent is at the centre of a cell, it must be able to cover the entire area with a sensor attached to it (e.g. Figure 1) to scan for victims or hazards. The area of a cell must be embedded within the range of the sensor. If we assume that the area covered by the sensor is circular of radius r, then each side of the cell must be ≤√2*r.

Figure 1: The area of a cell must be embedded within the range of the sensor. If we assume that the area covered by the sensor is circular of radius r, then each side of the cell must be ≤√2*r.

A cell can be in one of the following states:

• Wall: The cell cannot be traversed by an agent because it is blocked by an obstacle. We assume that an agent is equipped with sensors (e.g. laser, sonar, etc.) that enable to detect if it can successfully traverse the cell area from the center of it toward the points A, B, C, D (Figure 2) which represent all the possible accesses to the adjacent cells. If any one of these routes is blocked by an obstacle, then the cell is considered to be a wall.

• UnExplored: No agent has been in the cell yet, and therefore no tag has been deployed there yet.

• Explored: The cell has been traversed at least once, but the agents might need to go through it again in order to reach other unexplored cells. A tag is already deployed there by the agent who first visited the cell.

• Visited: The agents have already explored the cell, and they do not need to go through it again to reach other cells. Conceptually, this state is equivalent to a wall cell, in that no agent is allowed to traverse it. A tag is already deployed in the cell.

Figure 2: A, B, C, D are the access points from the current cell toward the adjacent ones. The communication range of agent and tags must be ≥ 2r.

Furthermore, we assume that the perimeter of the area is always formed by wall cells.

Objectives

To assess the performance of the proposed algorithms, we evaluate if they are able to achieve the two following objectives:

• Exploration Objective: all cells in the area are traversed by an agent at least once. This means that no cell is left in the unexplored state. When this objective is achieved, cells can be in any of the explored, visited or wall states.

• Termination Objective: all cells in the area are either walls or visited. No cell is left in the unexplored or explored state.

The Exploration Objective is always achieved earlier (or at the same time as) than the Termination Objective. Both objectives should be achieved in the minimum amount of time, because in an emergency scenario speed is essential. The faster the Exploration Objective is achieved, the faster victims and hazards are identified. The faster the Termination Objective is achieved, the earlier human responders can enter the area with the certainty that there are no hidden hazards. The efficiency of an algorithm can be measured by how fast it is able to achieve both the Exploration and Termination Objectives.