# Search and Rescue in a Maze-like Environment with Ant and Dijkstra Algorithms
## 3 Search and Rescue in Maze-like Environments
### Solving Phase II (Rescue): Signal Routing and Victim Extraction
#### 3.4.2 The Algorithm  
In the proposed approach (cf. Algorithm 2), we make use of a \"_depth attribute_\" to keep track of the diffusion of agents through the maze in order to find a path to the source. To do so, an individual measure of depth is calculated. In a tree data structure, the depth of a node is simply the number of edges from the tree's root node to the node itself [107] and  
Figure 7: The path cost calculations, having found an optimal path back to the source. At each hop, the algorithm favors the link with the lowest cost associated with it (indicated by the integers). therefore easily calculated. The root node is the lowest level of the tree and is assigned depth 0. The next level, connected with only one edge to the root, has depth 1. As the connections to the root grow, so does the level, with the final level (here) being 3. ```
\(Last\_Stopped\) = First agents to arrive at target; \(Stopped\_Agents\) = [\(Last\_Stopped\)]; \(Possible\_Moves\) = [right, left, forward, backward]; whileSource not within\(\_\)Stooped\(\_\)Agentsdo foreach agent not in\(\_\)Stooped\(\_\)Agentsdo  Generate list of all possible next states;  Acquire pheromone information of all next states;  Roulette Wheel \(\leftarrow\) generate probabilities of moving to each next state;  Spin Roulette Wheel to pick next state;  Update current position and pheromone levels; \(Agents\_Nearby\) = [All agents that could connect to \(Last\_Stopped\)]; \(Last\_Stopped\) = Min(depths of \(Agents\_Nearby\)); \(Stopped\_Agents.push(Last\_Stopped)\);  end for  end for
```  
**Algorithm 2**Algorithm to find Shortest Path to Source from Target  
In the maze-routing problem, the same concept can be applied, where the tree's root is the source and the depth there will have the value 0. As the agents move away from the point of origin, some of them will lose direct access to the source, either because of maximum range constraint or because the line of sight may be broken. However, agents will still remain in contact with other agents in the maze. Then, a rule will be followed: out of all the agents around that the agent can connect to, it chooses the one with the lowest depth, and then sets its own depth to this \((\text{depth}+1)\). If all agents concurrently and iteratively apply this rule, then their individual depth should remain a measure of the number of hops to the entry point (and the path will be explicitly identified). Figure 8 shows a flowchart of the working of the system in Phase II. The \(Last\_\)_stopped_ agent shown, is the one that was last chosen to be stopped by a previous stopped node and has to choose an agent from the nearby set of agents, subject to:  
* It is within the transmission range (\(TRange\)) of the \(Last\_stopped\) Agent. * There are no obstacles in between it and the \(Last\_stopped\). In the scenario shown in Figure 8, from the set of \(Nearby\_Nodes\), the first agent has depth of 0 which means that it can see the source. The other agent has depth of 1, which means that its one hop away from the source. Therefore, from the set, the next stopped agent to be chosen is the one with the lowest depth, which is the agent with depth 0. Moreover, after the node is stopped and because it is within the source transmission range and it does not have obstacles blocking it, the proposed search algorithm ends and Dijkstra algorithm runs again to find an optimal shortest path to the source. This will help in making sure that a path to the source can be efficiently formed after running Dijkstra algorithm. The solution proposed is considered a semi-distributed model. At first, the agents move in a distributed manner for the exploration part, then when the target is located, the agents will broadcast a message that the target is located back to the source, which will then find the shortest path in a centralized fashion. If no path is constructed, at first the agents will continue with the proposed improvement that is distributed.