# Search and Rescue in a Maze-like Environment with Ant and Dijkstra Algorithms
## 1 Introduction  
Drones, often referred to as Unmanned Aerial Systems (UASs) [1], Remotely Piloted Aircraft (RPAs) [2], Remotely Operated Aircrafts (ROAs) [3] or, most commonly, Unmanned Aerial Vehicles (UAVs) [4], are on their way to becoming pervasive technology. They have been around for quite some time, with their application initially driven by needs in the military domain (the US military used drones as far back as the Vietnam War [5]), where the precise determination of a unit's location is a common challenge in the field [6]. UAVs have recently become commercially available for civilian use, even for hobbyists, and the use of one or more drones for the express purpose of simultaneous localization and mapping (SLAM) [7] is a thriving research area [8].  
Nowadays, UAVs are technologically advanced devices capable of autonomous flight operations [9], making _remote_ piloting an option, not a requirement. Drones come in all kinds of shapes and forms, as well as vastly different prices, depending on their intendeduse and the required specifications [10]. Autonomous UAVs are becoming an increasingly viable alternative to using human labor, especially for data collection purposes, with key application areas being precision agriculture [11], civil defense, such as fire fighting [12], traffic management [13] or to locate victims in the aftermath of a disaster [14].  
While many applications can benefit from the use of (semi-)automated aerial devices due to the reduced cost (in comparison to human labor) and ease of access these devices have [15], few applications can make as strong a case as civil defense and disaster response. UAVs are especially useful in the aftermath of a large disaster because they are (a) expendable, (b) fast moving and (c) capable of moving in 3D space. The latter is extremely beneficial when existing infrastructure has been wiped out. Thus, there is increasing attention in the literature regarding the use of drones for, e.g., simultaneous localization and mapping (SLAM) [16], logistic operations [12], recovery of hazardous material [17], traffic management and monitoring, as well as the monitoring of structures and infrastructure and inspecting terrain [18] leading up to the deployment of human operatives into an environment. Furthermore, drones are quite capable of transporting and operating communication infrastructure, making them well suited to the formation of dynamic communication and sensing networks [19; 20]. When this is carried out by a swarm, the members of the swarm can use their on-board communication equipment to form temporary dynamic networks, so-called _ad hoc_ networks [21; 22].  
The very nature of a disaster suggests that large, possibly critical damages were caused to the infrastructure. It is not uncommon that the systems needed most in order to react quickly are the worst affected. Natural disasters often result in significant loss of communication and data-collection infrastructure. The use of so-called _swarms_ (formations of multiple UAVs that can, to some extent, operate as a single operational unit) [23] is a topic that receives increasing attention. Whether they are acting as mobile sensor networks [13], monitoring personnel or victims [14] or carrying out tracking and surveillance tasks in general [17], the benefits of being able to deploy such systems quickly is evident.