Multiple Depth First Search Algorithm

In the Multiple Depth First Search (MDFS) algorithm, the protocol that the agents run is a variant of the Depth-First-Search (DFS) one. The main idea is that agents extend the DFS tree with new explored cells in their way downwards, and mark these cells as visited when they traverse them in the opposite upward direction. In the DFS tree the hierarchical relationship between the cells is defined as parent/child. The mechanism used for distributing agents to different parts of the network is as follows: each explored cell has a counter that measures how many agents have traversed it coming from the same parent cell. Note that a cell can be accessed by an agent from at most one parent cell. As agents traverse the DFS tree downwards, they increment the counters associated with each traversed cell. At intersections, they choose to move to the explored cells traversed by the minimum number of agents, so as to assign the same number of agents to each branch of the DFS tree.

This algorithms is still not very efficient in terms of exploration time. By definition it traverses each cell at least twice (except for leaf cells), thus resulting in a long exploration time even in open areas without walls where a single traversal would suffice.

Brick&Mortar Algorithm

Our Brick&Mortar algorithm is designed to address the weaknesses of the MDFS algorithm: unlike MDFS, agents typically traverse each cell less than twice, thus resulting in a shorter exploration time.

The driving idea of the Brick&Mortar algorithm is that of thickening the existing walls by progressively marking the cells that surround them as visited. Visited cells are equivalent to wall cells in that they can no longer be accessed. Wall and visited cells are inaccessible cells while unexplored and explored cells are accessible cells. The algorithm aims to progressively thicken the blocks of inaccessible cells, whilst always keeping accessible cells connected. The latter can be achieved by maintaining corridors of explored cells that connect all unexplored parts of the network.

Like MDFS, Brick&Mortar does not require agents to know their location in the building. A relocated agent can simply navigate randomly until it finds an accessible cell and then continues the exploration from there. Brick&Mortar makes the blocks of inaccessible cells thicker until the entire terrain is converted to a large block of inaccessible cells.

The Brick&Mortar algorithm consists of two discrete steps. In the Marking step, the agent marks the current cell choosing between the explored and visited states. In the Navigation step, the agent decides which cell to go to next.

• Marking step: Every time an agent is in an unexplored cell (with no tags on it), it deploys a tag and updates the state of the cell, choosing between the explored and visited states. The current cell is marked as visited if it does not block the path between two accessible cells around it. Otherwise it is marked as explored. Figure 1 provides two examples of the marking step: one where the current cell is marked as explored (map a), and one where it is marked as visited (map b). In the first example, the only path between the two unexplored cells A and B traverses the cell in which the agent (black spot) is at the moment, thus the cell cannot be marked as visited. In the second example, there is an alternative path on the right end side of the map, thus the current cell can be marked as visited without closing the way between A and B. Note that such alternative paths are easy to compute locally, because they are strictly confined to the 8-cell perimeter of the current cell.

Figure 1: Marking rules: the agent must decide to mark the current cell as explored or visited. In the first example (a) the current cell cannot be marked as visited because it is the only available passage between adjacent cells A and B. In the second example (b) the current cell is marked as visited because there is an alternative passage between A and B on the right.

• Navigation step: The agents take a decision about which cell to access next. Priority is always given to the unexplored cells which are adjacent to the current one (Figure 2a). If the unexplored cells are more than one, the cell which is most likely to be marked as visited is chosen, i.e. the one with the most wall cells around it (Figure 2b). If many adjacent cells are unexplored and no one is more likely to be marked as visited, one of them is chosen at random (Figure 2c). If there are no unexplored cells, an explored cell is selected according to the ID of the agent (so that different agents spread in different direction). Finally, when the agent is surrounded by inaccessible cells, it stops its exploration task (Figure 2d).

Figure 2: Different situations in which the agent applies the navigation rules to decide which one of the adjacent cells it will go to during the next move.

Hybrid Exploration Algorithm

The HybridExploration algorithm combines two parallel protocols, one followed by physical agents (robots, or simply agents) and one followed by virtual agents. A physical agent takes significantly longer to move from one cell to another (physical robot motion) than a virtual agent (message propagation). Hence, the time of completing the exploration task is measured as the minimum number of physical steps required by physical agents to explore the entire area.

• Physical Agent Protocol: The Physical Agent Protocol is a modified (simpler) version of the Brick&Mortar algorithm. To make the agents capable of achieving the Exploration Objective, we introduced a mechanism which is similar to the Ants algorithm, and let the agents escape from the loops of explored cells in which they might be trapped. To do that, we need to introduce a counter for each tag, which can be read or modified by the agents. Once we have this, the agents simply need to increase a counter on the tag of a cell each time they traverse it, and then read all the counters of the adjacent cells and choose the minimum. In this way, an agent which traverses the same cell twice can take different decisions about the next move instead of always going toward the same direction, thus avoiding being trapped in a loop like the one shown in Figure 3. The protocol enables them to cover the entire area of interest eventually, but it has two weaknesses. First, physical agents are often inefficient in exploring the area, as they cover the same cells multiple times, instead of focusing their efforts on unexplored parts of the space. Second, although physical agents eventually manage to visit every cell at least once, they are not aware when this happens, i.e. they have no indication of when the exploration task terminates. These two problems motivate the introduction of the Virtual Agent Protocol. The two protocols, the Physical Agent Protocol and the Virtual Agent Protocol, work in synchrony and together constitute our proposed HybridExploration algorithm.

Figure 3: The numbers in the cells represent the times the cell has been traversed in the past. The agent goes to the cell which has been traversed the minimum amount of times to avoid being trapped in a loop.

• Virtual Agent Protocol: To speed up the exploration process and eventually achieve the Termination Objective, we introduce the concept of virtual agents. These are active messages propagated from cell to cell via the corresponding wireless tags. Virtual agents can only move to cells that are already deployed with tags; they cause changes in the current cell's state and make informed decisions about which cell to traverse next. Like physical agents, virtual agents move from one cell to an adjacent cell in the north, east, south or west direction, and they cannot traverse visited or wall cells. Unlike physical agents, they cannot traverse unexplored cells since there are no tags deployed there. Hence, they consider explored cells as their own territory, and build DFS trees along the corridors of explored cells that the physical agents leave behind. The goal of the virtual agents is to remove cyclic paths (loops) of explored cells. The protocol that they run is a variant of the Depth-First-Search (DFS) algorithm. The main idea is that virtual agents extend the DFS tree with new explored cells in their way downwards, and mark these cells as visited when they traverse them in the opposite upward direction. An illustrative example of the Virtual Agent Protocol is provided in Figure 4. The two agents first move together and include each explored cell in their way into the DFS tree. At the intersection, they continue to extend the DFS tree, but the one extends the left branch and the other the right branch. When the two virtual agents meet, they cannot extend the DFS tree any further; hence, they traverse the branches upwards marking cells in the way as visited.

Figure 4: Two virtual agents are collaborating to close a loop left by the physical agents. After the start (A), they separate into each of the two branches of the DFS tree (B) and meet again at the other side of the loop (C). Once there, they do not find any more explored cells which are not part of the DFS tree, so they close the loop by going back and marking every cell as visited .

Algorithm for Robot-Assisted Discovery of Evacuation Routes

When an emergency occurs within a building, it is crucial to guide victims towards emergency exits or human responders towards the locations of victims and hazards. The objective of this work is thus to devise distributed algorithms that allow agents to dynamically discover and maintain short evacuation routes connecting emergency exits to critical cells in the area. We propose two Evacuation Route Discovery mechanisms, Agent2Tag-ERD and Tag2Tag-ERD, and show how they can be seamlessly integrated with existing exploration algorithms, like Ants, MDFS and Brick&Mortar. We then examine the interplay between the tasks of area exploration and evacuation route discovery; our goal is to assess whether the exploration algorithm influences the length of evacuation paths and the time that they are first discovered.

This work is currently under submission, further details will be provided in future.

Click here to download a video example.