{'fraction_non_alphanumeric': 0.02749692827831003, 'fraction_numerical': 0.006705588525814508, 'mean_word_length': 4.455357925173049, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exploration and Coverage with Swarms of Settling Agents

We consider several algorithms for exploring and filling an unknown, connected region, by simple, airborne agents. The agents are assumed to be identical, autonomous, anonymous and to have a finite amount of memory. The region is modeled as a connected sub-set of a regular grid composed of square cells. The algorithms described herein are suited for Micro Air Vehicles (MAV) since these air vehicles enable unobstructed views of the ground below and can move freely in space at various heights. The agents explore the region by applying various action-rules based on locally acquired information Some of them may settle in unoccupied cells as the exploration progresses. Settled agents become virtual pheromones for the exploration and coverage process, beacons that subsequently aid the remaining, and still exploring, mobile agents. We introduce a backward propagating information diffusion process as a way to implement a deterministic indicator of process termination and guide the mobile agents. For the proposed algorithms, complete covering of the graph in finite time is guaranteed when the size of the region is fixed. Bounds on the coverage times are also derived. Extensive simulation results exhibit good agreement with the theoretical predictions.


Introduction
In many real-life scenarios, one is interested in deploying agents over an unknown region in order to explore it and possibly create an environment capable of detecting disturbances, localized activities and various events of interest. Often such scenarios are characterized by no a-priori knowledge on the region to be explored and covered, movement on the ground may be hampered by rubble and debris, agents lacking a global reference frame and limited communication capabilities with other agents and/or with the deploying station. For example, operating in a post-earthquake, collapsed building, rescue workers would obviously benefit from having a map of the free space inside the wreckage and a sensor network that can detect survivors. In general, unknown indoor environments present the major challenges of difficult ground movement, lack of a global reference frame (due to the impossibility of receiving the GPS signal) and severe degradation of RF communication due to multi-path and absorption effects. Sensing ranges, in most real-life scenarios, are also severely limited due to irregularities in the terrain. These irregularities might also hamper and slow down the movement of ground-based exploration and rescue robots.
We present here the concept of exploring an unknown region by a swarm of flying drones (agents) that eventually uniformly cover the region. The agentsidentical, autonomous, and anonymous -enter the region one after another from entry points and explore the region in a distributed manner according to some predefined action rules based on locally sensed information. While flying drones (MAV's) have many advantageous in search and rescue scenarios, their main drawback is a high power consumption during flight combined with limited, on-board energy (i.e., battery). This is especially critical in the aforementioned scenarios in which agent size is severely limited and consequently so are the battery weight and agent capabilities. The solution is to design exploration and coverage methods that put an emphasis on minimizing the flight time. In addition, the payload capacity of small MAV's is limited and the deployment of dispensable beacons is not relevant. Therefore, as a meta-rule, some of the agents settle and become beacons that can guide the exploration by the remaining mobile agents. The resulting sensing and covering infrastructure, effectively a directed acyclic graph of the region (or a directed forest if more than one entry point exists) composed of settled agents, may be used to generate implicitly a map and an ad-hoc sensor network to aid and guide subsequent operations.
Exploration is commonly defined in robotics research as the process of visiting of every part of a region by at least one agent at least once. In the context of this article, uniform filling (dispersal) refers to uniformly distributing agents in an unknown (but bounded) environment hence a uniformly filled region is obviously an explored region. Deployment is the process through which the agents enter the region, and the combination of deployment with the filling process must result in uniform coverage of the region of interest with agents Note, some researchers refer by "uniform filling/ dispersal" to the combined deployment and uniform distribution of agents.
The exploration strategies described in this paper are based on two basic metaconcepts. The first concept is the use of agents in the Dual Role of (mobile) Explorers and of Physical Beacons or Pheromones that guide exploring agents while also creating the uniform coverage. This concept is especially relevant for small, payload-limited flying agents as explained above. The idea draws upon the concept of stigmergy in biology which is defined by Kennedy et al [1] as "communication by altering the state of the environment in a way that will affect the behaviors of others for whom the environment is a stimulus". Our implementation of stigmergy utilizes the settled agents as the medium to change the state of the environment, in the form of beacons. The moving and exploring agents use these changes in the environment to guide their future actions. This process obviates the need for other markers and/or the need to rely on the environment to store information. An agent entering the region starts as a mobile agent and hence may move, once at every time step, to one of its neighboring cells in the region. The agents can also decide to become stationary and settle (i.e., become a beacon) if the proper conditions are met. The change from a mobile agent to a stationary one is considered irreversible. Once settled, an agent serves as a "beacon" to other, mobile agents thereby guiding their movement. The conditions for a change of the state and the actions taken in each state differentiate between the algorithms described herein. Once an agent settles its energy consumption decreases significantly. Thus, the Dual Role meta-concept helps decrease the energy consumption of the agents, generate the coverage, and guide the exploring agents. Another way to look on the covered surface is as a "shared memory" serving the mobile agents. And just like we want a shared memory to be reliable and scalable we require the same from the coverage formed by the settled agents.
As described above, the users deploying the swarm need an indication when the exploration and coverage of the region terminates (i.e., all the region has been explored and is uniformly covered). In addition, directing drones to empty regions can mitigate the effect of limited available energy. The second meta-concept, termed Backward Propagating Closure, realizes the requirement for a deterministic indication of termination and will be shown to effectively funnel drones to empty regions. Settled agents in fully explored, and therefore completely covered areas signal that further exploration is unnecessary by displaying Closed to already explored sections of the region. This signal, starting with settled agents closest to the boundaries of the region propagates "backwards", like a wave front, towards to the deployment point/s. Thus, when the settled agent at the entry point/s displays Closed signal it indicates to the user that all the cells of the region are already filled hence the exploration is completed.
The algorithms developed and analyzed in this paper are divided into two families -the Dual Layer Coverage, DLC for short, algorithms and the Single Layer Coverage (SLC) algorithms. The DLC algorithms result in two layers of uniform coverage of the regionone of settled agents and one of mobile agents hovering above -whereas the SLC algorithms result in a uniform coverage of the region by single layer of settled agents In the first algorithm presented the agents do a random walk over the region and continue entering the region until each cell is occupied by two agentsone mobile and one settled. A long cover time is the main drawback of such a random process and therefore the subsequent algorithms utilize "gradient-based" exploration strategies. In these processes, mobile agents are guided to empty areas by moving up the "gradient" implicitly generated by the signaling settled agents. These algorithms assume the agents can read the gradient displayed by the settled agents and keep in memory a value corresponding to the value displayed by the beacon below. Using these capabilities, the cover time is significantly reduced. Termination of the exploration and coverage process in the DLC algorithms is indicated by waiting for the next agent deployment a sufficiently long time. The SLC family of algorithms utilize (in addition to the concepts described above) the Backward Propagating Closure in order to both generate a deterministic indication of process termination and funnel the agents to empty regions. Consequently, these algorithms also show a reduction in the number of agents used in the coverage process and in the combined energy consumption compared to the DLC algorithms. However, these improvements come at the cost of additional sensing and signaling capabilities by the agents. Extensive experimental results show good correlation with theoretical predictions of performance.
In the following section, a review of related work is presented. Next, definitions and assumptions pertinent to all the algorithms discussed in this paper are presented. In sections 4 and 5, the DLC and SLC algorithms are described in detail and analyzed. Experimental results are discussed in section 6.
The main contributions of this paper are as follows: Seven algorithms for the exploration of unknown indoor regions by uniformly covering the region with agents are presented. A modified definition of the term termination time is introduced in which termination is achieved only when an external observer can positively detect termination. A novel concept to propagate information about coverage completion is introduced. It is used to give the external observer the needed indication and guide the agents during the coverage process. The mutual interaction between the entry process of the agents into the region and their movement in the region is analyzed. Theoretical and experimental results show the termination time is linear with region size.

Related Work
This work further develops themes and ideas that originally appeared in [2] and [3]. Preliminary results on the coverage of unknown indoor regions by a swarm of MAV's using DFS and the efficiency of a backward propagating information diffusion process was presented in [2]. In [3] the authors present and rigorously prove results about "DLLG", a dual-layer coverage algorithm, and present "SLUG", a backward propagating single-layer algorithm. The authors of [3] further compare the performance of these algorithms in terms of termination time and energy use. The concepts at the base of these algorithms are further developed in this work and additional algorithms are presented. We compare these empirically and analytically and present mathematical proofs and conjectures about their performance.
Numerous papers have been published on coverage and/or exploration of unknown regions using swarms of agents. The strategies used to spread the swarm of agents in a region can be divided into three broad categories -using virtual/artificial physics [4], separation into Voronoi partitions based on a utility function [5] and those using graphtheoretic concepts such as Depth First Search [6]. The various possibilities for required outcomes, combined with the large number of possible assumptions about the capabilities of the agents (memory, sensing, swarm size, etc.'), along with the various activation (i.e., timing) and deployment schemes and the assumed topologies of the unknown environment resulted in rich and diverse research topics and thousands of papers and reports. Comparison between the various strategies is henceforth quite problematic. A review of the common assumptions and required outcomes is given by Das in [7, p. 403]. In the next several paragraphs a brief review of the prior research most relevant to our work is presented. A more extensive overview of the literature can be found in Flocchini et al [8].
Filling and more specifically uniform filling (or dispersal) has been extensively studied and continues to be the focus of many researchers. In the field of mobile swarm robotics this problem is studied as a means to achieve a global behavior such as exploration, coverage, or a specific formation pattern. This vast body of work is broadly divided between those using centralized control (i.e., driven by a central entity that receives reports from agents and consequently commands their motions) control or decentralized control )i.e., based on designing independent behavioral rules for the agents resulting in the desired global outcome).
This work follows and extends previous research by Wagner et al. [9]. In their work, the authors assume a group of mobile agents tasked with exploring, but not uniformly covering, all the vertices of a graph-like environment guided by virtual pheromones [10]. The problem of uniform filling was formulated by Hsiang et al. [11] for the case of ground robots. In this paper the authors describe several distributed algorithms based on the 'follow-the-leader" concept and Depth First Search or Breadth First Search strategies to guide the filling process. The agents enter the region via a door and the objective of the algorithms is to minimize the filling time defined as the time until all the cells are filled with an agent (called the "make span"). The paper proves an upper bound for the filling time based on three noteworthy assumptions. The first is that the number of agents in a cell is limited to one. The second is that the robots are synchronous and the third that the agents have a finite memory. All of these methods assume an initially unknown but bounded and connected region modeled as a subset of a regular grid.
Theoretical bounds on the minimal capabilities (sensing range, memory) of the agent required to achieve uniform filling are derived by Barrameda et al. [12] [13]. The authors show agents must have some persistent and finite memory in order to cover a non-simply connected region. In [12] the authors assume the robots are asynchronous and consider the filling of simply connected regions (i.e., without holes). The authors then present lower bounds on the visibility range and amount of memory needed to reach uniform coverage. The results are based on the 'meta-rule' that a robot never backtracks. In [13] the authors present bounds on the memory and visibility range of robots needed to fill non-simply connected regions. They use the follow-the-leader paradigm and in order to deal with holes they use robots to temporarily block the multiple possible ways of advance. A similar concept is presented in [14].
Some researchers assume that the initial location of the agents is inside the region based on some arbitrary spatial distribution [15], [16]. A more common assumption it that the initial location of the agents is outside the region, as is the case in this research. If this is the case, a deployment process is commonly defined [17] [18], [19], [20]. If this is the case a deployment process should be defined (i.e., the agents should enter the region of interest according to some well defined timing strategy).
Additional ways to divide the body of work is according to the way the region is modeled. The region to be filled may be a part of the two-dimensional plane (i.e., continuous) [17], [4], [21] or modeled as graph (usually as grid graph) [15]. Moreover, the region may restricted to be simply-connected which means none of the obstacles is completely surrounded by empty cells [12], [15] however a more realistic and common assumption is for the region to be non-simply connected [21], [22], [23], [24]. In this research we assume the region of interest can be modeled as a non-simply connected grid graph since the presence of pillars and/or piles of rubble cannot be ruled out.
In the vast majority of the research the concept of recurring action-cycles is used to describe the behavior of an agent. Hence an additional way to organize the body of work is according to the scheduler (fully synchronous, semi-synchronous, or asynchronous) used to define the relationship between the action cycles of the different agents. Défago et al. [25] present a review of the various models including the time scheme used in this research.
While most research assume the agents are ground robots, the advantages of airborne robots in exploration (i.e., increased field of view) have been recognized by some researchers in the last decade. The idea of using airborne drones as a beacon was first mentioned by Stirling et al. [17], [18] and later by Aznar et al. [26], [27], with the objective of exploring (not uniformly filling) a region. In [17], [18], [19], [26], [27] each drone has a unique Id with the exploration strategies based on either depth first search [17], [18] or on a potential field generated by virtual pheromones in [26], [27]. In Rappel et al. [2] the authors present a DFS-based uniform coverage strategy by airborne agents however the issue of collision avoidance, critical when using airborne agents, is problematic since the number of mobile agents in each cell is not limited.
Energy is the prime constraint on the performance of swarms composed of flying agents. Consequently, most papers that assume flying agents also discuss the energy consumption and use it as one of the performance metrics. Stirling et al. [17] proposed an energy model that takes into account the energy consumption of a drone before its entry into the region, during movement and when operating as a beacon. Based on this model the total energy consumption is computed and sensitivity to different parameters analyzed. Aznar et al. [26] also use the total energy consumption with recurrence equations used to predict the total energy.
A settled agent can signal other agents using various mediums -RF, acoustic, and visual amongst others. Possibly the best solution for the scenarios described above is visual as it is both localized and secure from interference by neighboring agents. First suggested by Peleg [28] as a means of signaling with lights without explicit communication, the idea has been since extended for the lights to be used only as a memory [29]. Das et al. [30] investigate additional capabilities imparted to agents with lights. Prior to this work the idea was used by Poudel et al. [31] that present a uniform scattering algorithm that is linear with time for synchronous robots with lights, a compass and a visibility range of 2. It is important to note that comparison of the performance metrics (e.g., cover time) of the various approaches, especially the issue of energy consumption, is problematic due to the differing assumptions about the agent's capabilities, the modeling of the region and the time scheme.

Preliminaries
In this section definitions and assumption that are pertinent to all the algorithms are described.

Problem Formulation
In the coverage problem, a swarm of drones seeks to enter and uniformly cover an a-priori unknown region R composed of interconnected cells in a decentralized manner. In the terminal configuration every cell is occupied by two drones in the dual layer coverage problem or by one drone in the single layer coverage problem The unknown region, , to be covered is a connected region that is modeled as an orthogonal grid graph and access to the region is via well-defined entry point/s. It is an arbitrary, possibly non-simply connected grid composed of equally sized cells forming the empty region to be explored surrounded by walls and incorporating obstacles. Each cell of R can contain a single mobile agent and/or a single settled agent. The agents enter the region in a prescribed order from an "agent source" or a deployment point that is adjacent to the entry point and that has a sufficient number of drones to The region R can also be therefore represented by graph a ( , ) with the vertices, V, representing the empty cells and the edges, E, representing the connections between adjacent cells. In the rest of this paper, the terms cell and vertex are interchangeable. Unless stated otherwise, n = |V| i.e., the cardinality of the graph is equal to the number of empty cells in the region and m = |E|. An example, non-simply connected region with one entry point, eight rooms and a double corridor is depicted in Figure 1.

Timing model
Time, , is discretized such that = 0, 1, 2, 3, … , , …. and each step is further subdivided into M (a very large integer) equal sub time-steps, , such that = 1/ . Each agent wakes up once in every time step at a randomly selected sub time-step as given by Definition 1 and Eq. (1). This is the most probable time model in real-life, decentralized multi-agent systems in which each agent has its own internal timer that controls when it wakes up. For sufficiently large values of M the scheduler is asynchronous and the probability that two agents will wake up in the same instance is negligible. The time between successive action cycles of a specific agent is bounded by (0,2) and the number of activations of agent between two successive action cycles of agent is in the range [0:2]. Such time models are called fair 2-bounded asynchronous schedulers in the literature [25]. The wake-up time of agent at time step is denoted by , and defined as: With (1, − 1) denoting the uniform distribution over the integers {0,2, … − 1}.

The Agents
The agents are assumed to be Miniature Air Vehicles (MAV's) capable of motion in the horizontal plane (i.e., parallel to the to the surface) and in the vertical plane (i.e., perpendicular to the surface). In the horizontal plane the agents move in one of four principal directions (i.e., "Manhattan Walk") whereas in the vertical plane the agents can only move straight down (i.e., parallel to the gravity vector). Hence, at every time step, every agent is either in flight and searching for a place to land, or has already landed somewhere in R. The former type of agent is called mobile whereas the latter is called settled. Agents always start as mobile agents and may settle at some time step. Settled agents are assumed to remain in place forever, providing useful information to the mobile agents. Each agent can sense the presence of agents in any adjacent cell at Manhattan distance 1 from it (i.e., the sensing range of agents is 1). Agents can sense whether a neighboring agent is mobile or settled. While mobile agents can sense both mobile and settled agents, the settled agents can only sense neighboring settled agents. Figure 3 depicts the sensing volume and possible directions of movement. Figure 3 Sensing and moving region of an agent. The ground, occupied by a settled agent is marked in grey while the plane in which the flying agents move is marked in blue. The mobile agent, a drone, is shown both in the air (dark blue) and settled on the ground (brown). The arrows denote the possible directions of movement Definition 2: The set of all entitiesagents and/or walls -sensed by agent at a cell (or node) ∈ at time is denoted by ( , ). This set is also called "the neighbors of at time at cell u". For brevity, we omit the reference to both a specific time and agent whenever possible. The set may include up to 8 agents since each cell may be occupied by both a settled agent and a mobile agent. As ( , ) is a grid graph and the agents perform a Manhattan-type walks, the positions of the neighbors of agent ai are enumerated systematically according to Figure 4. A mobile agent in cell is enumerated as "5" while a settled agent in cell is enumerated as "0". Furthermore, when discussing the agent directly underneath a mobile agent in cell reference is made to position "0". Again, for brevity, we omit the reference to a specific cell, agent or time step when it is obvious from the context. The agents are identical, anonymous (i.e., have no identifiers) and autonomous (i.e., have no central controller). The agents may also utilize a small, limited memorydepending on the algorithm. At every wake-up, the agent does a Look, Compute and Action (LCA) action cycle [32] in which it senses its surroundings, makes a decision and implements the action. All actions are assumed to be instantaneous (i.e., atomic). The agent may do several types of actions. The first is "move" from one cell to another; the second is "settle in place", the third is "settle in a neighboring cell" which is composed of a moving to the relevant cell and settling in place and the fourth is "signal" in which a settled agent becomes a beacon and projects (e.g. using lights) some information.
The energy consumption of an agent is the sum of the energy consumed while mobile and the energy consumed while settled.
Assuming constant power consumption in the mobile and settled states Eq. (2) can be re-written as: Assuming ≫ we get that ≅ (4)

Definition 3:
The vertex location of the agent at time is denoted by ( , )

Agent Entry Model
When dealing with the covering problem, there is the issue of the initial location of the agents. In real life applications such as Search and Rescue it is obvious the agents are initially outside the region. Clearly and fully defining the interaction between the deployment process and the coverage algorithm is critical when trying to develop tight bounds on the coverage time. Several deployment strategies are discussed in the literature ( [18], [19], [20]). Using the terminology coined in [18], the first and simplest strategy is Linear-Temporal Incremental Deployment (LTID) in which agents attempt to enter the region at a constant rate. The second is Single Incremental Deployment (SID) in which an agent is deployed at a constant rate but only if the previously deployed agent has become a beacon. Hence, this strategy requires either propagation of messages across the network of beacons with the additional delays and complexity such a communication protocol entails or long-range wireless communication with the accompanying problems of multi path attenuation in the enclosed region. Experimental results from [18] indicate this strategy is advantageous when DFS is used since the entering agent will travel the shortest path to the exploration frontier. When greedy exploration is used the advantages of this strategy are doubtful. The third strategy Adaptive Group Size (AGS) deploys agents into the region depending on the density of mobile agents. The mobile agents are assumed to measure the density of mobile around in their sensing neighborhood. The main advantage is localized reductions in the number of mobile agents but at a cost of additional sensing and complex logic. All three deployment strategies described above were developed in conjunction with a DFS exploration strategy. In [19] the authors present a hybrid entry model called FGID combining SID and AGS that allows the number of mobile agents to be greater than one and does away with the dependency on the density of mobile agents. In [20] an agent at the exploration frontier signals that additional agents are to enter the region depending on the number of empty cells it detects. While this model is adaptive to the explored environment it requires communication between the agent and the entry point/s (which is not specified in the paper). In the three papers mentioned above as well as many others the blocking of an entry point by another agent is not discussed. It is dealt with by either limiting the entry rate or (implicitly) neglecting the phenomena.
In this research the agents are initially outside the region and enter it one-at-a-time. We use the constant rate entry model in which the time interval between successive entry-attempts, denoted as ∆ , is constantsee Figure 5. When ∆ > 1, the time window in which agents may enter the region is limited to the first time step and in the other ∆ − 1 time steps only the agents inside the region are active. In other words, no agent will enter the region during the interval ∆ if entry does not occur during the first time step. Whether an agent actually enters or not depends on the occupancy of the entry point. Since movement of the mobile agents out of the entry point/s depends on the filling strategy, the actual entry rate depends on the progression of the filing process and vis-versa. The model described is similar to the LTID strategy described in [18] however unlike LTID this strategy takes into account the occupancy of the entry point/s. The effect of ∆ on the covering process and specifically the termination time is investigated both theoretically and experimentally. Figure 5 The Constant Rate Agent Entry model. Agents, located outside the region, may enter every ∆ time steps

Performance Metrics
We are interested in the performance of the swarm as a whole as it solves the coverage problem and therefore define the following three metricstermination time, total energy used, and number of agents used. The definition of the termination time is kept intentionally vague since the two families of algorithms -DLC and SLChave different termination criteria and these will be defined in their respective sections. As described above we assume that the power consumption of a mobile agent in flight is constant and that once an agent settles its power consumption is zero. Hence the energy consumption is linear with respect to the time an agent is mobile, and the total energy used is the sum of the flight times of all the agents. Both the total energy used and number of agents used are measures of the effort to cover the region while the termination time measures its result. In addition to these three aggregative metrics, we are also interested in the maximal energy consumption of any of the agents since it relates to the energy limit of the agents. Definition 4: The termination time, ( ), of a coverage process done by a multiagent system with respect to a region R is the first time step that the process of covering R with agents terminates.

Definition 5:
The set of agents participating in the coverage process at time step = is defined by ( ) = { 1 , 2 , … , ( ) } and the cardinality of ( ), is denoted by ( ) = | ( )|. Note, when referring to the number of agents without explicit mention of the time the meaning is the number of agents at , = ( ). Definition 6: The total energy consumption used by a multi-agent system with respect to a graph environment R is equal to ∑ -the sum of all individual agents' energy consumptions. Total energy consumption is also denoted ( ). Definition 7: The maximum specific energy consumption by any agent at the termination of the process, is denoted by ( ), and defined by ( ) = ( : = 1: )

Dual Layer Coverage (DLC) Algorithms
Uniform coverage in the Dual Layer Coverage family of algorithms is achieved when every cell in the region contains exactly two agentsone settled and one mobile hovering above it. All the algorithms are based on the basic concept of the dual use of agentsas explorers and as beaconsbut different, local information-based action, rules are used. In the following sub-sections, the algorithms are described in detail and their performance is analyzed Definition 8: The termination time, ( ), of a coverage process done by a multi-agent system using a Dual Layer Coverage algorithm with respect to a region R is the first time step every cell in R is occupied by two agentsone settled and one mobile.

Dual Layer Coverage by Random Walk (DLRW)
Single agent and multi-agent random walk on graphs and grids has been investigated in numerous prior works. Notably in Alon et al. [33] the authors analyze the length of time until every cell in a graph is visited (at least once) by one of several agents doing a random walk starting from a common vertex. This length of time, defined in [33], as the cover time does not require any specific distribution of the agents when it is reached. A more relevant characteristic of a random walk is the hitting time defined as the expected time it will take an agent to move from vertex to vertex , ≠ ; , ∈ . Patel et al. [34] derived expressions for the hitting time of random walks on graphs when the number of agents in a cell is not limited. It is, however, these constraints on the number of agents in a cell and the final agent distribution that are critical to uniform filling process.
The acronym DLRW stands for Dual Layer, Random Walk and thus describes both the required coverage of the region coverage and the essence of the local action rules used in the algorithm to achieve it. The action rules of this simple algorithm state that when there is an empty cell in the sensed region of a mobile agent it will settle in it thereby expanding the region covered. Preference is given to settling directly underneath as may happen when the first agent enters an empty region or if a settled agent fails underneath a mobile one. If settled agents already occupy all the neighboring cells, then a mobile agent will check if there are cells without a mobile agent in them. If there are such cells, then it will arbitrarily select one and move to it. If all the neighboring cells are filled by two agents (a settled agent and a moving agent), then the agent will stay in its current cell. Once an agent settles (in other words, lands) it will stop moving and become a beacon. As a beacon, its very presence indicates there is an agent in the cell and nothing more. In accordance with Definition 2 the state of agent , denoted by , is the set {mobile, settled}. The state machine of an agent is described in Figure 6, the flowchart of the algorithm in Figure 7 and the local action rules for agent at time are described by the pseudocode in Figure 8. ← ; ← " " /* settle there [2] Else /* if not [3] ̃← { = 0, = 1: 4} /* define set ̃ as all empty neighboring /* cells [4] ← integer ( /* stay in place [7] End If End If

The Absorbing Markov Chain representation
The use of Markov Chains in analyzing random walks by a single agent is common (e.g. [35], [34]) . The state of the Markov chain in this case is the location of the agent. This is a possible since if the agent doing the random walks is in a certain cell, then all the other cells are necessarily unoccupied. However, this definition is irrelevant in the case of multiple agents doing a random walk and instead we define the state of the process as a vector composed of the state of each cell. When dual layer coverage is used, the state of a cell is defined by the number of agents in it.
We model the algorithm described above as an absorbing Markov chain in order to prove its eventual termination. In addition, the absorbing Markov chain representation allows calculation of the expected cover time however that is practically impossible to do so except for the simplest regions.
We denote the state of cell at time step by and the state of the coverage process at time step , , as the tuple { 1 , 2 , ⋯ , }. The state of a vertex has a value from the set {0, 1, 2} corresponding to {empty; filled by one settled agent; filled by one settled and one mobile agent}. As described above, in the DLRW algorithm, the possible actions of each agent (and their corresponding probabilities) depend solely on its current position and neighborhood. Therefore, by definition, the possible transitions from the current state of the coverage process depend only on the current state of the agents. Since this is true for all cells and at any time step , changes in the state of the coverage depend only on the current state of the process. Hence the coverage process defined above has the Markov property as defined in [36] and is thus a Markov process.
In [37], a state of a Markov chain is defined as absorbing if it is impossible to leave it. Following from above definition, a Markov chain is defined in [37] as absorbing if (a) it has at least one absorbing state, and (b) if from every state it is possible to reach an absorbing state (not necessarily in one step). Using above definition of , the states at the beginning and at the end of the coverage process are 0 = {0, 0, ⋯ ,0 } and = {2, 2, ⋯ ,2 } respectively. Moreover, based on the above definition of absorbing, is an absorbing state since it can be reached from any state, nor can any agent leave it. Once reached, no additional agents can enter the region. Having defined the starting and absorbing states for the algorithm we can now prove that the DLRW terminates with probability 1. Proposition 1: The DLRW algorithm terminates with probability 1.
Proof: See [37], Theorem 11.3 Note, that while the number of possible transient states is combinatorically upper bounded by 3 | | − 1, the actual number of transient states and the possible transitions between them may be much smaller and depends on the region's topology and the time scheme used.
Using the formulation in [36] and [37], for the case of one absorbing state and transient states we define the transition matrix , P, as: Such that is a × matrix describing the probability of transitions between transient states, is a × 1 vector of the transitions from the transient states to the absorbing state and is a 1 × 1 identity matrix. With these definitions, , the fundamental matrix for P, is a × matrix defined as: Following from Eq. (3), the expected number of steps from each transient state to the absorbing state, denoted by , is given by Eq. (7) where is a unit column vector. Note that since is the absorbing state, the expected number of steps from 0 until the absorbing state is reached is τ(1). In other words: To clarify the above result, we shall consider a simple example of a 2 by 2 region and with the entry point being in the cell marked as 1see Figure 9. The asynchronous time scheme described above is used and the agents enter the region once every time step. The states are defined in Figure 10 and the state transition diagram is shown in Figure 11. Possible transitions are marked by the directed edges along with their probabilities. The probabilities depend on the time scheme as it determines the possible orders of movement between the agents.

Figure 11 Absorbing Markov chain example -State transition diagram
The transition matrix corresponding to the above example is: The analytical solution of the above example yields the expected cover time of 10.333 with a standard deviation of 2.54 versus an expected time of 10.5 with a standard deviation of 2.7 by in using the simulation. Note that there are 13 relevant transient states out of the possible 80 combinatorial states. The main takeaway arising from the above example is that the absorbing Markov chain analogy makes it possible to accurately compute the expected cover time however the process is arduous and requires exact knowledge of the region and might be impossible to practically implement due to the complexity of bookkeeping all possible, probabilistic transitions.

Algorithm Analysis
To bound the expected coverage time, we look at the two processes that together determine the coverage timethe filling process and the deployment process. Definition 9: (a) The hitting time from a vertex ∈ to the entry point, e, is denoted by ℎ( , ). The maximum hitting time from any vertex to the entry point is denoted by ℎ ( ). (b) The (absolute) maximum hitting time over all ordered pairs of nodes is denoted by ℎ such that ℎ ≥ ℎ ( ). (c) The minimum hitting time from any vertex to the entry point is denoted by ℎ ( ).

Proposition 2:
The coverage time of the region R with a single entry point denoted as e satisfies 2 × ∆ ≤ and ≤ 2 × ℎ ( ) × ∆ Proof: For the lower bound, we analyze the coverage process as if it's composed of two process occurring in parallel and therefore define the absolute lower bound as ( , ). The rationale -interaction between the two processes will always increase the lower bound of each of the processes. When agents do not enter the region because of the deployment process, (e.g., large ∆ ) the filling process will lengthen and when the entry point is occupied due to the random walks performed by the agents the deployment process will lengthen. Hence, this definition of the lower bound will always be smaller than the lower bound that takes into account the interaction between the processes. The shortest time for the deployment process is the required number of agents, 2 × , multiplied by ∆ . Similarly, the shortest time for the coverage is 2 × ℎ ( ) however since ℎ ( )=1 in any region the shortest time for the coverage is 2 . Therefore, the lower bound for the expected coverage time is 2 × ∆ .
For the upper bound, we first analyze the problem for ∆ = 1 and then expand the result for ∆ > 1. As the number of agents in the region increases so does the probability that the movement of an agent will be blocked due to the presence of other, mobile agents (and the limit of one mobile agent in a cell). Hence, as the number of agents increases so does the expected time to reach a cell on the graph (and settle in it if it is empty). Consequently, the expected time to reach the last empty node in the region is the longest. Therefore, our analysis focuses on the situation in which the region is fully covered by settled agents and there are − 1 mobile agents. The single cell, u, occupied only by a settled agent may be located anywhere in the region. That cell is calledthe empty cell. In this situation, only the mobile agents neighboring the empty cell may move and do so only to the empty cell. Obviously, during the random walk process the position of the empty cell changes. Imagine a token that is located at the empty cell. When an arbitrary, neighboring agent, a, of the empty cell moves to the empty cell, it exchanges its position with the token's. Hence, at the end of the action cycle of agent a, the agent is in the previously empty cell and the token (that is the empty cell) in the previous position of agent a. This process continues until the token reaches the entry point. Clearly, the token is performing a random walk on the graph. Furthermore, analysis of the multi agent random walk is therefore equivalent to analysis of the single token random walk. Since the graph is undirected the expected time until the token reaches the entry point is equivalent to the expected time for the last agent to enter the region to reach the last empty cell -ℎ( , ) = ℎ( , ). Using Definition 9, ℎ( , ) is upper bounded by ℎ ( ). Thus, the upper bound on the expected coverage time when ∆ = 1 is given by 2 × ℎ ( ) . The main drawback of the above upper bound is difficulty in calculating ℎ ( ) even when the region and the entry point are known. An alternative, looser upper bound uses the fact that ℎ ≥ ℎ ( ) and the known values of ℎ for certain graphs. Specifically, for the 2 dimensional grid and linear graphs the upper bounds are Θ( 2 log ) and ( 3 ) respectively ( [33], [38]).
When ∆ > 1, agent entry into the region, as defined above, is possible only during the first time step of ∆ . Hence, it is possible that when the token reaches the entry point no agent will enter the region. In such a case, the random walk done by the token will continue until the time step when both the token reaches the entry point again and it is the first time step of ∆ . In order to extend the upper bound to these cases we will use the fact that these are two independent random processes. The entry model can be thought of a disc with a single hole, adjacent to the entry point and rotating at 1/∆ turns per time step. The last agent will enter only when the hole in the disc and the empty cell are aligned. Since the two processes are independent of each other the joint expectation of the two processes is given by the multiplication of the expectations of each process [37] and we get that

Dual Layer, Limited Gradient (DLLG)
In the Dual Layer, Random Walk algorithm the settled agents only signal their presence and thus the mobile agents can only perform a random walk in their search for a cell to settle in. In the DLLG algorithm (the second of the DLC family of algorithms), the mobile agents advance up a gradient of Step Counts (SC for short) projected by the settled agents. Once a mobile reaches the empty parts of the region, it settles. Mobile agents move up the gradient when the difference between the step counts of the current and destination cells is one which is equivalent to a gradient steepness of one. Specifically, at every time step, every mobile agent with step count attempts to move to a neighboring location with step count + 1 (and no mobile agents). Hence the name of this algorithm -Dual Layer, Limited Gradient (DLLG). The step count of a settled agent is the number of steps (not time steps) taken by the agent from the entry point until the time it settled and became a beacon. Moreover, the step count of every mobile agent necessarily equals the step count of the settled agent (the "beacon") it flies over, thus mobile agents are always "climbing" the gradient defined by the beacons in single-step increments. The result is a directed movement (unlike the random movement in DLR) of the mobile agents to the empty, still unexplored parts of the region. Mobile agents become beacons over time. As a first priority, whenever a mobile agent sees a neighboring empty cell, it attempts to land in that cell, changing its state to "settled" and thereafter projecting its step count to any mobile agent that sees it.
DLLG is a distributed algorithm that is implemented via straightforward local action rules, which all of the agents in R execute at every time step. As a first priority, and as in DLRW, a mobile agent will settle down if there are neighboring empty cells and expand the filled region. In the case an agent enters the region and there are no settled agents directly underneath it, the step count it will project is "1". If there are no empty cells to settle in, the agent will attempt to advance (i.e., move up the gradient) to a cell with a step count greater by one than its current step count. When a mobile agent cannot advance up the gradient, due to whatever reason, it stays in its current location. When there are several relevant cells to advance to, an agent will arbitrarily select one. The result is a directed acyclic graph (DAG) created by the settled agents and in which the edges are the possible directions a mobile agent may move. Mobile agents, once all the empty cells are occupied, continue advancing up the gradient of step counts stopping only when blocked by a wall or by another mobile agent. The result is a filling of the upper layer from the boundaries of the region towards the entry point with a subsequent, monotonous reduction of the area yet uncovered. These more complicated action-rules (compared to DLRW action rules) require agents with the following additional capabilities.
• Ability to project the step count to the mobile agent moving above.
• A finite memory of bits to store the step count. Hence, in accordance with Definition 2, the state, , of agent is determined by the combination of its physical state (i.e., mobile or settled) and step count. Implementation of DLLG requires agents that can store as well as signal their step count. Since the signaling is by the beacons to the flying agents, multiple lights facing upwards controlled by color, intensity, etc., seems the most logical solution [7, p. 252]. In the case of a quadcopter, the lights at the ends of the rotor booms can be used for this. Definition 10: The step count of agent at time step = is the number of steps the agent moved from its Entry Point to its location at time = . Definition 11: The state of an agent using the DLLG algorithm is defined by the 2tuple S = ( 1 , 2 ) where 1 s has a value from the set {mobile, settled} and 2 is the step count.
The local action rules of the Dual Layer, Limited Gradient algorithm implemented by each agent at every time step are defined by the flowchart in Figure 12 and the pseudocode in Figure 13. The blocks in the flowchart are enumerated for easy reference in the pseudocode. Initialization: for all agents ∈ located at t=0 at the agent source set S = ( 1 , 2 ) = ("mobile",0)  Dual Layer, Limited Gradient algorithm pseudocode

Example
An example of the coverage of a non-simply connected region with 18 cells using the DLLG algorithm is depicted in Figure 14 in the form of snapshots at different times. The snapshots offer a top-down perspective of the process and in order to clarify the process different colors are used as follows -empty cells are black, obstacles are white, cells filled by a settled agent are yellow with the step count in red and mobile agents are green "X"-s. The snapshots show the gradual filling of the region by settled agents - Figure 14(a) -(d) and the filling of the upper layer by mobile agents from the region's boundary towards the entry point in Figure 14(e). The final state is shown in Figure  14(f).

Algorithm Analysis & Performance
Analysis of the coverage process needs to take into consideration the coupling between the entry model and the local action rules. The agents enter the region according to the entry scheme described above once every ∆ time steps. The termination time for the case of ∆ ≥ 2, derived in [3] is given by: Proposition 3: For a linear graph = ( , ), with cells the termination time of the coverage process using the Dual Layer, Limited Gradient algorithm and ∆ = 1 is upper bounded by: As described above, the agents start outside the region and the outcome of the DLLG algorithm are two layers of agents in the region. In order to derive the upper bound on the termination time we will use an adversarial scheduler that defines the relative wake up order of any two neighboring agents in a time step. This is useful in a linear graph in which movement of agents closer to the entry point is only affected by agents further away. Then, based on the adversarial scheduler and the agent entry model the upper bound on the termination time is derived. Definition 12: The distance of agent from the entry point is given by δ(EP, j). Definition 13: The scheduler that will result in the largest termination time on a linear graph is defined as the wake-up order of the agents, in time step = , that begins with agents at the entry point and ends with the agents at the expansion frontier. We call this the adversarial scheduler. When zooming in on two adjacent, mobile agents, this means that at time step = the agent closer to the entry point will wake up first. , < , ∀ , such that ( , ) ≥ ( , ) + 1 (11) Proof: We start by analyzing the movement of two neighboring mobile agents, denoted by and , located over settled agents in the graphsee Figure 15. Agent will move to the right only after agent moves since only one mobile agent can occupy a cell at any given time. The relative wake-up defined by Definition 12: The distance of agent from the entry point is given by δ(EP, j). Definition 13 means agent will always move one time step after agent . Note that in all other wake up schedules, agent might wake up after agent and thus both agents will move in the same time step hence the adversarial scheduler defined above will result in the worst termination time regardless of the distribution of mobile agents.
We can now analyze the coverage process of the linear graph . At = 0, the first agent will enter the region at the entry point. At = 1 the 1 st agent will settle according to the DLLG action rules, and the 2 nd agent will enter the region. At = 2, the mobile agent at the entry point will move to the right and an additional mobile agent will enter. At = 3, due to the adversarial scheduler only the right-most mobile agent will move (and the agent entry point will stay in place). Only at = 4 will the agent at the entry point move after which another mobile agent will enter. This sequence continues until 2 enter the region and is depicted in Figure 16 that is divided into 3 sections. The left most with the time step, the center section shows the positions of the mobile and settled agents and the right section shows the total numbers of mobile, settled and all agents in three columns. Every row in the center section is sub-divided into two and shows the locations of all the agents. It is easily discernable that with the adversarial scheduler an additional agent enters the region once every two time steps. Moreover, the number of agents at the odd time step is given by: From which we get However, in DLUG a mobil And after rearranging and setting = 2 we get: And consequently The lower bound on the termination time is the shortest time until 2 agents enter the region. When Δ = 1 it is simply 2 − 1.
Experimental results verify the two upper bounds. Moreover, the experimental results show the termination time in connected regions (not necessarily linear regions) when ∆ = 1 is upper bounded by 2 × (2 − 1). Based on these results we write the following conjecture. Conjecture 1: The termination time of the Dual Layer, Limited Gradient algorithm over any connected region R and for ∆ ≥ 1 is given by:

Dual Layer, Unlimited Gradient (DLUG)
In the Dual Layer, Unlimited Gradient (DLUG) algorithm settling agents signal their step count and the mobile agents attempt to move up the gradient as fast as possible. This means that at every time step, a mobile agent will move up the gradient as long as it is increasing and regardless its steepness. Specifically, at each time step the mobile agent will select as its destination the neighboring cell with the step count that is closest, but larger, than its current step count that is also not occupied by a mobile agent. This difference from the Dual Layer, Limited Gradient algorithm described above is beyond technical. Conceptually, in the DLUG algorithm, preference is given to moving towards the empty parts of the region as fast as possible at the cost of a less ordered gradient. The rationale being to minimize the instances a mobile agent is staying in place since the energy consumption is the same regardless of whether it's moving or staying in place.
The purpose of the step count is to guide the mobile agents. However, defining the step count as the "number of cells an agent has travelled since it entered" (see Definition 10) may create local maxima. These local maxima will slow down or even stop the movement up the gradient since agents do not move down the gradient. Hence, the definition of the step count is modified to "at every time step the step count of a mobile agent equals the step count of the settled agent (the "beacon") it flies over". Consequently, whenever a mobile agent settles it will signal the step count of the last beacon it flew over incremented by one. Definition 14: (a) The step count of a mobile agent at time step = is the step count of the settled agent directly underneath -= 0 . 2 . (b) The step count of a settled agent at time step = is the step count of the last settled agent it flew over incremented by 1.
According to Definition 14 an agent senses the step count directly underneath it at the beginning of every action-cycle rather than storing it in memory and incrementing by one at every time step the agent moves. When the agent settles it sets the projected light pattern accordingly. This alternative implementation negates the need for a memory and means the agent is oblivious. The modified definition of the step count reduces to the original definition when the gradient steepness is limited to one since the step count of every settled agent is equal to its distance from the entry point.
Besides this fundamental difference in the local action rule the Dual Layer, Unlimited Gradient algorithm is similar to the DLLG algorithm. The state of an agent is defined using Definition 11 and as a first priority mobile agents settle in empty neighboring cells. Furthermore, the two algorithms can be implemented by the same agents. The result of the DLUG algorithm is a directed acyclic graph (DAG) with its root at the entry point and its vertices denoted by their step count. However, in DLUG a mobile agent in cell may move to any neighboring cells with a higher step count and consequently the outgoing degree of cell will always be equal or greater than the degree of the same cell when DLLG is used. The DAG resulting from the DLUG algorithm will always have at least as many directed links as the DAG resulting from the DLLG algorithm.
At every time step all the agents in R execute the local action rules defined by the Dual Layer, Unlimited Gradient algorithm and described in the flowchart in Figure 17 and the pseudocode in Figure 18. ← ; 1 ← " "; 2 ← 1 /* set step count as 1 [2] Else /* if not [3] ̃= /* subset of that is filled with beacons /* and with no mobile agents [5] If | /* lowest step count in the set relevantCells /* greater than current step count [5] ← ℎ . 2 = /*the subset of relevantCells with beacons /*having a step count equal to lowestSC [6] If |

Example
An example of the difference in the coverage process between the Dual Layer, Unlimited Gradient and Dual Layer, Unlimited Gradient algorithms is shown below in Figure 19. At = 26 the agents are distributed in the region as shown in Figure 19(a). The difference between the two algorithms effects the behavior of the agent surrounded by the blue circle. In the example, at = 27 that agent wakes up before the agent over = 5. Since the DLLG algorithm limits the gradient steepness to 1, the agent can only stay in place as shown in Figure 19(b). However, using DLUG, it will move to the cell with = 7 (Figure 19(c)). As seen, due to a specific wake-up order the ability to move up a steeper gradient enabled the agent to move instead of staying in place. Simulation results show this is not very common and in many cases the termination times of the two algorithms are close.

Algorithm Analysis & Performance
In linear regions the upper bounds are the same as those derived for the Dual Layer, Limited Gradient algorithm since in a linear region the gradient steepness is always one due to the single direction of advance. Experimental show that in general the termination time in DLUG is linear with the size of the region for ∆ ≥ 2 and regardless of the topology of the region. Moreover, for ∆ = 1 the termination time is upper bounded by the termination time for ∆ = 2. Additionally, the termination time is linear with ∆ for ∆ ≥ 2. Based on these results we propose the following conjecture. Conjecture 2: The termination time of the Dual Layer, Unlimited Gradient algorithm over any connected region R is given by The DLC family of algorithms solve the uniform coverage problem using simple agents and local action rules. Dual Layer, Random Walk requires minimal sensing capability by the agent but at the cost of a high coverage time. Dual Layer, Limited Gradient and Dual Layer, Unlimited Gradient exhibit significantly shorter upper bounds on the coverage time that are validated by experimental results. However, all the DLC algorithms have two major disadvantages. The first is the need for 2 agents in order to reach coverage along with the ensuing cost. The second is the significant energy expenditure of the mobile agents that fill the top layer especially since this layer is filled from the boundary of the region towards the entry point. The Single Layer Coverage family of algorithms discussed in the next section was developed in order to overcome these disadvantages. Hence, it might be asked "what do the agents in the top layer do after termination?". There are at least two possible answerssettle down next to the existing beacons and create a redundant coverage layer or exit the region according to some signal sent by the user. We leave that decision to the developer of the operational system.

Single Layer Coverage (SLC) Algorithms
Coverage in the Single Layer Coverage family of algorithms is achieved when every cell in the region contains one settled agent and this information is known to an external observer (i.e., the user). This definition extends the definition of the coverage process and the termination time of the coverage process because of the paramount importance of indicating that the process completed. All the SLC algorithms use the meta-concept of Dual Use Agentsas explorers and as beaconswith the algorithms differing one from another by the action rules. More importantly, all the SLC algorithms use the meta-concept of Backward Propagating Closure as the means to generate the indication of termination. In the following sub-sections, the algorithms are described in detail and their performance analyzed Definition 15: The termination time, T C ( ), of a coverage process done by a multiagent system using a Single Layer Coverage algorithm with respect to a region R is the first time step at which (a) every cell in R is occupied by one settled agent and (b) external observer/s located at the entry point/s receive a deterministic indication of termination.

Top-level design
Achieving single layer coverage means changes to the functionality of the settled agents. In the DLC algorithms, the term settled agent is interchangeable with the term beacon. The term settled agent describes the physical state (i.e., on the ground) while the term beacon describes the functionality of the agent (i.e., a guiding light). This is possible since the (sole) function of a settled agent is to guide the mobile agents towards the relevant areas of expansion. In the SLC algorithms, we add another function to the settled agentto signal to the mobile agents where NOT to move. A settled agent performing that function is called a Closed Beacon since it signals incoming mobile agents "this direction of advance is closed". Thus, a settled agent can be either a "Beacon" or a "Closed Beacon" depending on its locally sensed information. Transition of an agent to Closed Beacon is always from Beacon as depicted in Figure 20 and explained in the next section about the Backward Propagating Concept. In either case the transition is nonreversible. Note that in order to enable movement along the gradient a Closed Beacon continues to signal its step count.
In the SLC algorithms, the mobile agents move up or down the gradient of step counts projected by the settled agents. The rationale for advancing up the gradient is the same as in the DLLG and DLUG algorithms. In many instances during a single layer coverage process there are mobile agents in a sub-region in which all the settled agents are in the Closed Beacon state. We call these agents the "superfluous agents". Moving down the gradient both removes the superfluous agents away from the regions that are already uniformly covered and guides them towards the Entry Point/s (when all the region is in state Closed Beacon). Formally, the state of agent , , is according to Definition 11 where 1 has a value from the set {mobile, Beacon, Closed Beacon} and additional memory since at every time step the agent decides whether it is a Beacon or a Closed Beacon. Figure 20 SLC algorithmsagent transition diagram. An agent always starts as mobile and may transition to Beacon or Closed Beacon. Beacons may transition to Closed Beacons.

Backward Propagating Closure and deterministic termination
In real life search and rescue scenarios, the sole source of information of the user into the coverage process is via the events at the entry point. While the user may conclude that the process has finished if the rate of entry slows down significantly it may be critical in some scenarios to definitely know that the process has finished. The purpose of the Backward Propagating Closure (BPC for short) meta-concept is to give the user explicit indication that the coverage process is finished. The combination of gradient-guided movement and the BPC concept results in "funneling" of mobile agents to still "un-Closed" parts of the region and the return of the superfluous agents back to the entry point/s after process termination. The funneling speeds up the coverage process while the return of the agents to the entry point decreases the number of agents engaged in the coverage process.
Essentially the BPC concept is a way of propagating information about on the state of settled agents in case the state is Closed Beacon. Intuitively, the indication an exploration direction is "closed" will start from the edges of the region. When all the relevant neighbors of settled agent signal "Closed" the agent will change its state to "Closed Beacon" as well. This process continues until all the settled agents are Closed Beacons * . The transition of a settled agent to the Closed Beacon state depends upon two conditions. The first is that there are no empty cells around. The second condition depends on the rules that define the neighboring cells to which a mobile agent may advance. Thus, the BPC meta-concept is defined differently for each SLC algorithm. One possible definition is that a settled agent will transition to Closed Beacon only when all the neighboring settled agents with a higher step count are also Closed Beacons. This is given in the definition below. Definition 16: The state of the settled agent a located at will change to Closed Beacon if: (1) ̌= ̂ with a. ̌= { . 2 > 0 . 2

Example
An example of the Backward Propagating Closure process is given in Figure 23 for a region with = 7 cells. Figure 23(a) shows the empty region while Figure 23

Algorithm Analysis & Performance
Following from the definition of the termination time in the SLC algorithms is the need to bound the time of the BPC process. Intuitively, the upper bound on the run-time of the Backward Propagating Closure (BPC) process on ( , ) is and in the following paragraphs we will prove this bound by deriving expressions for the maximum distance the signal must propagate and for the minimal propagation rate. The ratio of these expressions is the maximum propagation time.

Definition 17:
( ) is the time span from the time step an agent settles in the last empty cell in ( , ) until the settled agent at the Entry Point transitions to "Closed Beacon". Definition 18: The maximal propagation distance is the maximal number of vertices the BPC signal must pass from the last leaf in ( , ) that transitions to "Close Beacon" to the Entry Point. It is denoted by ( ).

Proof:
We denote by a linear graph with vertices and the Entry Point at one end. Trivially the last cell to be filled is the cell at the other end of the graph. Hence the BPC signal has to propagate along the entire graph and consequently ( ) = − 1. Suppose that this is not the minimal distance and that ( ) = (or greater). However, this means the signal propagated through + 1 vertices. This contradicts that the cardinality of the graph is . Hence Given a settled agent at cell that at time step = transitions to Closed Beacon. We ask what is the number of time steps until the BPC signal propagates to settled agent located in a neighboring cell and ∈̑. From the time scheme described above it is clear the signal may propagate within the same time step if , < , and in the following time step if , > , . In other words, the minimum propagation rate is 1.

Proposition 5:
For any given graph = ( , ) and | | = the upper bound on ( ) is given by n.

( ) ≤
Proof: An agent that settles always transitions to Beacon state hence transition to Closed Beacon can only be done in the following time step. The ratio of the maximal distance derived in Proposition 4 and the minimal propagation rate derived above we get that the propagation time of the BPC signal is − 1.Summing up we get that ( ) = when is a linear graph and ( ) < otherwise. ∎ Note that the above proof did not make use of Definition 16 and is thus correct for other definitions.

Single Layer, Limited Gradient (SLLG)
The SLLG algorithm combines the exploration strategy and traversal rules used in Dual Layer, Limited Gradient algorithm with the Backward Propagating Closure metaconcept in order to fill the region by a single layer of agents. Preference is given by the mobile agents to settling versus advancing along already covered cells. When settling is not possible, agents advance up a gradient projected by the settled agents. At every time step, agent with step count senses its neighboring region. If there are Beacons signaling a step count that is equal to + 1 the agent will attempt to move to those cells that are also unoccupied by mobile agents. If all the Beacons with + 1 are occupied, then it will stay in place. The rationale being that the mobile agents may move in the next time step/s. However, if there are no Beacons with + 1 then the agent will try to retrace its movement by going down the gradient projected by Closed Beacons. By limiting the retracing to Closed Beacons there is no possibility that a retracing agent will block the advance of incoming agents. That is because as stated above the advancing mobile agents move only over Beacons. Accordingly, an agent that determines it cannot advance will check if there are any Closed Beacons with a step count that is smaller than its own and no mobile agents. If there are, it will arbitrarily select one and move to it. The transition of a settled agent to the Closed Beacon state in SLLG follows directly from the action rules governing the advance up the gradient and is defined below. Definition 19: The state of the settled agent a located at will change to Closed Beacon if: (1) ̌= ̂ with a. ̌= { . 2  (2) ≠ 0| = 1: 4 The flowchart in Figure 24 shows the different behaviors of the mobile agents with the expansion behavior in blocks (1)-(4), advancing up the gradient in blocks (5)- (8) and retracing in blocks (9)- (13). The detailed local action-rules implemented by the mobile agents are described in the pseudocode below ( Figure 26 and Figure 27). Based on Definition 19 the flowchart ( Figure 25) and the pseudocode ( Figure 28) describing the local action-rules of a settled agent implementing the Backward Propagating Closure meta-concept are listed below.
The resulting macro behavior is the uninterrupted flow of the mobile agents to the parts of the region that are still not filled by agents in Closed Beacon state. The explored region using the Single Layer, Limited Gradient local action rules is very similar to that of explored using (centralized) BFS with one major difference. Since SLLG has no (centralized) queue and the movement is partly arbitrary, at any time before completion the exploration may progress in certain parts more than others. Moreover, the step count of a settled agent may be greater than its minimal distance from the entry point. ← ; 1 ← " "; 2 ← 1 /* set step count as 1 [2] Else /* if not [3] ̃= { = 0: = 1: 4}    Single Layer, Limited Gradient pseudocodesettled agent

Example
A possible coverage scenario with 18 empty cells is described in Figure 29. The Figure 29 shows snapshots of the progression of the coverage process at different times steps. In order to distinguish between the different entities, colors are used as followsempty cells are black, obstacles are white, and mobile agents are green "X"-s. Cells filled by a Beacon are yellow while cells filled by a Closed Beacon are brown. In both cases the step count is in red. In Figure 29(b), a settled agent has transitioned to Closed Beacon because further expansion is not possible. The indication however has not propagated since each of its neighbors has neighboring cells that are empty and/or filled by a Beacon. The back propagation, once all the cells are filled, is shown in Figure  29  Single Layer, Limited Gradient -Example. The snapshots of the process are ordered left to right, top to bottom. Color code: empty cells are black, obstacles are white, cells filled by a Beacon agent are yellow and cells filled with a Closed Beacon are brown, the step count in red and mobile agents are green "X"-s. Proof: During the coverage process agents deploy into the region, uniformly fill it by settling while concurrently indications of the process completion propagate back to the entry point. Although the coverage is by a single layer, the number of agents that enter the region may be larger than since agents will continue to enter the region as long as the entry point is not a Closed Beacon. This number is bounded by 2 as no more than 2 agents may populate a cell. Hence, in order to derive the upper bound we can ask what is the time it will take to fill the region with 2 agents with termination being achieved when all the settled agents are in the Closed Beacons state and there two layers of agents (one settled and one mobile). The termination time in this case will necessarily be longer than that of the original problem since 2 agents must enter the region regardless of the Backward Propagating Closure process. This is equivalent to asking what is the termination time of the Dual Layer, Limited Gradient algorithm when the termination condition is that 2 enter the region and that the agent at the entry point is at state Closed Beacon. We call this new, notional algorithm "DLLG with BPC". We upper bound the termination time of this algorithm by (artificially) dividing the process into a deployment and filling phase followed by a "completion propagation" phase and using the upper bound on the time of each phase. That is possible for the following reasons: (1) The BPC process propagates regardless of the mobile agents (2) The coverage using DLLG is not affected by the BPC process since in the Closed Beacon state the settled agents continue to signal their step counts and guide the mobile agents. The mobile agents implementing the DLLG local action rules will disregard the Close indication and continue moving up the gradient as before. Consequently, the upper bound on the termination time of the "DLLG with BPC" algorithm is the sum of the termination times of the two constituent processes. The termination time of the DLLG algorithm according is 2 − 1)∆ +1 for ∆ ≥ 2 and from Proposition 5 we know that ( ) ≤ hence

Algorithm Analysis & Performance
For the sake of the lower bound, we assume a best-case scenario in which the exploration process and the backward propagating closure process are concurrent process or in other words when the longer of the two finishes so does the other. The minimal time for the BPC process is one in the case the wake-up sequence of the agents is from the last order to settle to the entry point. The minimal time for the deployment and filling phase depends on the minimal number of agents that must enter the region, , and the (minimal) time between successive entries, ∆ . Thus, the lower bound of the deployment and filling phase is given by ( − 1)Δ . Hence: The main drawback of limiting the gradient steepness to 1 in SLLG is that may stop the advancement of the mobile agents prematurely. This is best explained using an example. We focus in Figure 30 on the two black ovels that surround the cells occupied by both a mobile agent and a settled agent with a step count of 10. In both cases the mobile in the cell can't move up the gradient although the region is not nearly filled since the gradient is 5 rather than 1. This slows the advance of other, incoming mobile agents. It is compounded by the fact that the local rules give precedence to staying in place over retracing when the movement up the gradient is prevented due to a mobile agent (see block 8 in the SLLG flowchart). The resulting "traffic jam" is released only when the settled agents in the surrounding cells become Closed Beacons at which time movement down the gradient is possible and the condition preferring staying in place becomes irrelevant. This problem is unique to SLLG and obviated in the following algorithms. This unwanted consequence increases and ,however, it is most noticeable in its effect on the . Naturally, its severity grows with ∆ since as ∆ increases so does the termination time and accordingly so does the time the mobile agents in the "traffic jam" are stuck with the accompanying energy consumption. This phenomena is also seen in DLLG however it is much less noticeable since inherently the required coverage is by two layers. Figure 30 Single Layer, Limited Gradient -The drawback of limiting the movement to gradient steepness of one

Single Layer, Unlimited Gradient (SLUG)
The SLUG algorithm differs from the SLLG in two crucial aspects. The first is that the gradient steepness the agents can move on is not limited and the second is the ability to move down the gradient over Beacons as well as Closed Beacons. These two differences reflect the preference to move in any given time over staying-in-place. Moving up the gradient without limiting its value to one is used in the Dual Layer, Unlimited Gradient algorithm and results in a faster ascent up the gradient. Moving down the gradient over Beacons as well Closed Beacons means the superfluous agents can continue exploring. This is a significant change from retracing only over Closed Beacons which prevents the superfluous agents from moving over Beacons. However, movement over Beacons is mandatory if a (superfluous) agent is to explore the region. The main drawback is that such agents, when exiting a Closed Beacon sub-region, may temporarily block advancing mobile agent. Experimental results show this rarely occurs and the performance of this algorithm is significantly better than that of the Single Layer, Limited Gradient algorithm.
The transition of a settled agent to the Closed Beacon state in SLUG follows directly from the action rules governing the advance up the gradient. Thus, a settled agent will transition to Closed Beacon only if all neighboring settled agents with a higher step count are already Closed Beacon. This is described in Definition 16 and the relevant flowchart and pseudocode are given in Figure 21 and Figure 22 respectively. The result of the SLUG algorithm, as in the Dual Layer, Unlimited Gradient algorithm, is a directed acyclic graph (DAG) with its root at the entry point and its vertices denoted by their step count. Since a mobile agent in cell may move to any neighboring cell with a higher step count the outgoing degree of cell will be equal to the number of cells with a higher step count.
The flowchart in Figure 31 shows the different behavior types of a mobile agents with the expansion behavior in blocks (1)-(4), advancing up the gradient in blocks (5)- (8) and retracing in blocks (9)- (13). Since the gradient is not limited, the presence of mobile agents is checked first (5). The lowest relevant step count is found only if there are relevant cells to move to and following that the corresponding possible cells to move to (6). The same concept is used when moving down the gradient.

Figure 31
Single Layer, Unlimited Gradientmobile agent flowchart Each block is numbered and referred to by this number in the pseudocode below Initialization: for all agents ∈ located at t=0 at the agent source set S = ( 1 , 2 ) = ("mobile",0)    Do SLUG -settled agent action rules ( Figure 22 ) End Figure 33 Single Layer, Unlimited Gradient pseudocodemobile agent -part 2

Example
The coverage process using the SLUG algorithm in a region with 18 cells is described in Figure 34. Figure 34 shows the agents' distribution at different times during. As in previous examples, in order to distinguish between the different entities, colors are used as follows -empty cells are black, obstacles are white, and mobile agents are green "X"-s. Cells filled by a Beacon are yellow while cells filled by a Closed Beacon are brown. In both cases the step count is in red. Of note is the funneling of the mobile agents to the empty parts of the region in Figure 34(d), and the return of the superfluous agents toward the entry point in Figure 34

Algorithm Analysis & Performance
The extensive experimental show that the termination time in SLUG is linear with the size of the region for ∆ > 1 and regardless of the topology of the region. Moreover, for ∆ = 1 the termination time is upper bounded by the termination time for ∆ = 2. Additionally, the termination time is linear with ∆ for ∆ > 1 and indeed ≤ . Based on these results we propose the following conjecture.

Single Layer, Depth First (SLDF)
Depth first search was used in previous research to explore regions but with different assumptions about an agent's capabilities or region. For example in [39] a multi robot DFS is used to explore only tree-type regions. This approach is expanded in [40] to more general regions but with robots having unlimited memory. In [41] the authors present an upper bounds for the number of moves traversed by k agents implanting a distributed DFS protocol that solves a related problem -the Labelled Map Construction problem. The agents in that research are anonymous, asynchronous but again have unlimited memory and assumed to be initially dispersed in the graph. Similarly, in [42] strategies for the exploration of a graphs by 1+ agents (D denoting the diameter of the graph) are given. Again, the agents are assumed unlimited memory, as do the vertices. A similar problem, deploying agents in a region such that all points of the region are visible to at least one agent, is discussed in [43]. The region is assumed simply connected and the agents to have a unique ID thus simplifying the traversal of the resulting tree. In this research, however, the region's topology is not limited, the agents are initially located outside the region and the agents have limited memory and sensing ranges.
The depth-first exploration strategy used in this algorithm differentiates it from all the algorithms described previously. In depth-first exploration the objective is to search "deeper" first and consequently the agents move as far as possible along the gradient before settling and expanding the covered region. In this algorithm the two metaconcepts described above are combined with the depth-first exploration strategy. Agents fill (and thus explore) the region along a single trajectory until further exploration is impossible. At which point the exploration continues from the closest branching point (i.e., a cell with a Beacon inside). This process repeats itself until the entire region is covered. Thus, at any time there is exactly one directed path along which the agents move up the gradient. Consequently, the step counts of settled agents are equal to the distance from the empty point. Explicitly, mobile agents move up the gradient of step counts projected by the settled agents as much as possible before settling and becoming Beacons. When a mobile agent reaches the end of the gradient, (i.e. the last settled agent projecting a step count) and senses an empty cell, it will settle in it. Thus, a main difference in the action rules implementing SLDF and those of other Single Layer Coverage algorithms is which action is done as a first priorityadvancing up the gradient in SLDF versus settling in the SLUG and SLLG. When an agent can neither advance nor settle, the agent will move to a cell with a lower step count thereby retracing its path. When retracing, the agent will only move above settled agents whose state is Closed Beacon in order to prevent the mutual interference between the agents moving up and those moving down the gradient. The transition of a settled agent to the Closed Beacon state in SLDF follows directly from the action rules governing the advance up the gradient and is thus the same as in SLLG (a mobile agent may move only to neighboring cells with a step count greater by exactly one than its current step count) and thus described in Definition 19. Intuitively the result of Single Layer, Depth First algorithm is a spanning tree of the region with its root at the entry point (or a spanning forest if there is more than one entry point). This is because at any time step the mobile agents advance over exactly one path.

End If End If End If
Else /* if the agent is not mobile Do SLLG -settled agent action rules ( Figure 28) /* see explanation above End Figure 36 Single Layer, Depth First algorithmmobile agent pseudocode

Example
Using the same region as in the previous examples, an example of a coverage process using the Single Layer, Depth First is given Figure 37. The start of the backward propagating closure is clearly seen in Figure 37(c). The larger number of superfluous agents, compared to the SLLG example above, is result of the longer coverage time. The larger spatial distribution of those agents is common in runs in which the Backward Propagating Closure proceeds faster than the retracing by the superfluous agents. Figure 37 Single Layer, Depth First -Example. The snapshots of the process are ordered left to right, top to bottom. Color code: empty cells are black, obstacles are white, cells filled by a Beacon agent are yellow and cells filled with a Closed Beacon are brown, the step count in red and mobile agents are green "X"-s

Algorithm Analysis & Performance Lemma 2:
The upper bound on the termination time of a coverage process using the SLDF algorithm on the region R with a single entry point is given by: We derive the expressions for the upper bound by first proving that SLDF generates a spanning tree over R, next show that the termination time of a spanning tree is upper bounded by the termination time of a linear graph with respect to a dual layer coverage process. Finally, define a new "virtual algorithm" composed of Dual Layer, Limited Gradient and Backward Propagating Closure (see proof of Lemma 1) over a linear graph and show its termination time upper bounds the termination time when using SLDF. Proposition 6: The SLDF algorithm generates a spanning tree, T, of a region R with single entry point at time . Proof: Agents enter the region R from the entry point. At time = 1, the tree T(1) includes only the entry point. At every subsequent time step mobile agents advance up the gradient. Suppose at time = there is an empty cell, . that is adjacent to cell ∈ ( ) occupied by a settled agent, in state Beacon, with the largest step count at time = . According to the SLDF action rules the mobile agents advance from the entry point to hence by + ∆ a mobile agents will move from to and we'll get ∈ ( + ∆ ). Note that can't be adjacent to a Closed Beacon since this contradicts the definition of Closed Beacon (i.e., no empty neighboring cells). Suppose the empty cell, also neighbors the cell ∈ ( ) that is occupied by a settled agent, in state Beacon, but not with the largest step count at time = . Advance of agents from to is prohibited by the SLDG action rules. Hence the cell will have an in-degree of exactly 1 which is the definition of tree and ( ) = ( ( )). ∎ Proposition 7: The termination time of the coverage process over a spanning tree ( , ) using the DLLG is upper bounded by: Proof: The DLLG action rules allow agents to move only up the gradient. In a spanning tree the movement of agent at time step = up the gradient depends solely on the relative wake up times of the agents ahead of it and the spaces (i.e., settled agents without a mobile agent) between them. The filling of a branch in a tree does not delay the filling of any other branch since the agents continue moving up the gradient and superfluous agents cannot enter the vertex at which the branching occurs. Using the adversarial scheduler defined in Definition 12: The distance of agent from the entry point is given by δ(EP, j). Definition 13, the termination time of the DLLG algorithm over a directed tree is maximal when the tree is a linear graph (tree). The reason, in a linear graph all the agents ahead of agent affect its movement whereas in all other trees the number is smaller by definition. From Proposition 3 we have the expression for the termination time of the DLLG algorithm over a linear graph. ∎ In the proof of Lemma 1 we defined a notional algorithm called "DLLG with BPC" that is an upper bound on the termination time of a region. We apply this notional algorithm on a linear region since according to Proposition 7 its termination time upper bounds that of a spanning tree of the same cardinality. The termination time of our notional algorithm is the sum of the termination time of the DLLG algorithm and run time of the BPC algorithm over said region. We thus get:

Single Layer, Tree Traversal (SLTT)
The SLTT algorithm differs from the other algorithms described above in the way mobile agents are guided. Instead of moving on a gradient of step counts, in the SLTT algorithm the mobile agents follow "arrows" as described in [44]. The "arrows" are projected by the settled agents and signal the last direction an agent moved prior to settling in its own local reference frame. The SLTT extends the algorithm in [44] and generates a single layer coverage instead a dual layer coverage using the Backward Propagating Closure meta-concept described above. As in the SLLG and SLUG algorithms, the top priority of an agent is to settle and become a beacon. At every time step a mobile agent that cannot settle, tries to move forward according to the arrows. A mobile agent will only move to a cell with its arrow indicating that the settled agent inside it also moved in that direction. When a settled agents has several neighboring empty cells, following mobile agents will branch out in the different directions. In order to describe the SLTT algorithm explicitly we first define the state of an agent using arrows (instead of step counts).
In accordance with Definition 2, the state, , of agent is determined by the combination of its physical state (i.e., mobile or settled) and Arrow. Definition 20: The Arrow of agent at time step = , denoted by ( ), is the direction the agent selected at step = . The Arrow can take any of the 4 values 1 to 4 depicted in Figure 4. Note that the Arrow signaled by agent is the last direction selected by prior to settling. Definition 21: The state of an agent using the SLTT algorithm is defined by the 2tuple S = ( 1 , 2 ) where 1 s has a value from the set {mobile, Beacon, Closed Beacon} and 2 is the Arrow. Based on the above definitions we can now write that an agent will advance when in at least one of its neighboring cells the Arrow projected by neighboring settled agent is pointing in the same (relative) direction as the enumerated cell with respect to agent . This removes the need for a common reference frame (or even chirality) between the agents. In Figure 38 this is the case with the neighboring cells 1 and 2. An agent will retrace when in at least one of its neighboring cells the Arrow signaled by a neighboring cell is in the opposite direction to the enumerated position of that cell. This geometric relationship is translated to whether the difference between the Arrow direction and the number of the cell is exactly two (in absolute terms). In Figure 38 this is the case with neighboring cell 3. The flowchart in Figure 39 resembles that of SLLG with 2 major changes. First, the use of Arrows instead of step counts (mainly) manifests itself in blocks (5) and (9) that describe the action rules for advancing either from or towards the entry point. The second is a change in the mechanism of the Backward Propagating Closure meta-concept. In the BPC meta-concept described above a settled agents changes its state depending on the step count of its neighboring settled agents. While this definition is irrelevant (since there are no step counts in SLTT) the basic idea is kept. A settled agent using SLTT transitions to Closed Beacon when all its children are Closed Beacon and there are no empty neighboring cells as defined below. The dependency only on the children and not all neighbors means that transition to Closed Beacon using SLTT can be faster compared to the previous implementations of the Backward Propagating Closure. This behavior is corroborated by the experimental results. Definition 22: The state of the settled agent a located at will change to Closed Beacon if: (1) ̌= ̂ with a. ̌= {̌← ℎ . 2 = | = 1: 4} b. ̂← ℎ . 1 = " "| = 1: 4} (2) ≠ 0| = 1: 4 The change is in the first condition and the updated flowchart and algorithm are given in Figure 40 and Figure 43 respectively. The algorithm analysis and specifically the upper bound on the time are relevant since the underlying concept is not changed. Nevertheless, this modified definition greatly effects the performance of SLLT as is shown in the following section.
The result of the SLTT algorithm is a spanning tree since, trivially, the directions of movement from two cells can't match the direction of movement of a single destination cell.
Direct implementation of the SLTT action-rules requires agents that can store as well as project their Arrow. Since the signaling is by the beacons to the flying agents, multiple lights facing upwards controlled by color, intensity, etc., seems the most logical solution [7, p. 252]. In the case of a quadcopter, the lights at the ends of the rotor booms can be used for this. Moreover, a finite memory of 2 bits is required to store the Arrow.

Figure 38
Single Layer, Tree Traversal algorithmrelative direction of movement. The black numbers enumerate the neighboring cells. The red arrows denote the last direction the agent settled in each of the neighboring cells moved. Single Layer, Tree Traversal algorithm-mobile agent flowchart Each block is numbered and referred to by this number in the pseudocode below /* select a cell from [7] ← ; 1 ← " "; 2 ← ( ) /*move to selected cell and set as the /*direction to move to Else ← ; 1 ← " "; 2 ← 2 /* stay in place [8] End If  /* select a cell from [11] ← ; 1 ← " "; 2 ← ( ) /*move to selected cell and set as the /*direction to move to Else /* [12] ← ; 1 Figure 43) End

Algorithm Analysis
The Single Layer, Tree Traversal algorithm generates a spanning tree as described above and the action rules dictate that mobile agents retrace their movement only along settled agents in Closed Beacon state. Hence the analysis performed of the Single Layer, Depth First algorithm applies to this algorithm. Consequently, the upper bound is described in Lemma 2.

The traversal rules and the underlying graph
Different local action rules are used in the various algorithms to define the movement of the mobile actions. They differ from one another by the how loose they are in the sense of how much they limit the movement of an advancing mobile agent to adjacent neighboring cells. At one extreme is the random walk in which an agent does not have a notion of what "advance" is and can therefore move to all neighboring cells. At the other extreme are the Single Layer, Tree Traversal and Depth First algorithms in which the agent is limited to a gradient steepness of one and can move only to children of the current settled agent. Another way to look at the traversal rules is based on the outdegree of each settled agent. The outdegree of each settled agent, in the Dual Layer, Random Walk algorithm, is the same as that of the cell in R and it is bounded by 4. In all other algorithms, however, the outgoing degree of a settled agent is bounded by three and depends on the aforementioned action rules. The exploration and coverage process, in all algorithms, implicitly generates a directed acyclic graph (DAG) over the region R (in the case of the Single Layer, Tree Traversal and Depth First the underlying graph is a spanning tree which is a subset of the DAG). The number of edges in a DAG is related to the outdegree of each of its vertices which in this problem are the settled agents. Denoting by D (or T) the underlying DAG (or spanning tree) we can thus write the following general relationship: In the following section we will review this relationship using simulation results.

On the fault tolerance of the Single Layer Coverage algorithms
Based on the discussion above of the Single Layer Coverage algorithms we can now discuss the fault tolerance of these algorithms. When discussing search and rescue scenarios the tolerance to such failures is critical. Not only are the drones themselves relatively fragile, the environment, in the form of ceiling collapse etc. may greatly increase the probability of such failures. We define a fault as a mechanical or electrical failure of the drone that results in its ceasing to operate. If at the time of the failure the drone is mobile it will fall and may cause the failure of a settled agent † .
The objective of the fault tolerance capability of the algorithms is for the coverage process to terminate correctly (as defined above) in finite time. In the following paragraphs we review possible failure modes, the adaptations to the local action-rules and resultant swarm behavior.
1. Failure of mobile drones. The failed drones will fall however the coverage process will only be delayed. That is because mobile drones sense the step count at every action cycle rather than store it. Moreover, mobile agents only sense the environment and do not signal any other agent. Therefore, the failure of a mobile agent will not affect the underlaying graph structure being generated nor any agent.

2.
A mobile agent is blown aside to another cell. As explained above the mobile agent will not affect the settled agents however this failure mode is further divided into three separate cases. In the first, the new position is an empty cell in which case the agent will settle down and project a step count of "1" (the same behavior of the first agent to enter the region). The process will continue correctly since agents always move up the gradient and the BPC depends only on neighboring agents with a higher step count. In the second case, the agent is blown over a cell occupied only by a settled agent.
The mobile agent will behave correctly in its next action-cycle since decisions are made using only locally sensed information. In the third case the agent is blown into a cell occupied by a mobile agent. In this case they will both fail however as explained above the proves will continue correctly. Summing, in all three cases, when a mobile agent is blown off the path the process terminates correctly however the termination time may be increase. 3. Failure of a settled agent. This failure mode is divided into two casesdepending on the current state of the process. Specifically, whether the settled agent in an area of Beacons or Closed Beacons. In the first case there are still mobile agents advancing in the region hence a mobile explorer will (at some time step) sense the (now) empty cell. This raises the question what will this mobile project after settling? The specific answer depends on the type of algorithmis it gradient based or arrow based. However, in either case its crucial to maintain the connectivity of the region. If it's a gradient based algorithm the step count will be equal to the lowest step count of the surrounding settled agents incremented by 1. This assures movement is possible from the failure site to the entry point. If it is SLTT then the mobile agent will select the arrow direction leading to the failure site.
In the second case the area surrounding the failed settled agent is filled by Closed Beacons. When a settled agent senses that a previously occupied neighboring cell is now empty it will change its state to Beacon and the failure will propagate to the entry point due the Backward Propagating Closure that will cause a cascading of the change through the region. As a result, mobile agents will start to enter the region (since now the entry point is in state Beacon) and advance up the gradient until reaching the failure site. Note that the above discussion of failures of settled is indifferent as to the cause (partial ceiling collapse or being hit by a falling mobile agent). The above discussion shows the Single Layer Coverage algorithms are fault tolerant to failures of dronesmobile and settledalike. The mutual interaction between different failures is only partially discussed and merits further research.

Results and Discussion
Seven different exploration algorithms were presented in sections 4 and 5 above. In this section the performance of the algorithms according to the metrics defined above is experimentally evaluated. In the first two sub-sections, the effects of the region (size and topology) and time between successive entries (i.e., ) on the performance are evaluated for each family of algorithms separately. Putting aside the Dual Layer, Random Walk algorithm, the algorithms differ from one another by the traversal rules, whether or not the BPC meta-concept is used and the rules for retracing. Dual Layer, Limited Gradient (DLLG) and Dual Layer, Unlimited Gradient (DLUG) use different traversal rules (limited versus unlimited movement on the gradient) however neither uses Backward Propagating Closure nor allows moving down the gradient. Single Layer, Unlimited Gradient (SLUG), Single Layer, Limited Gradient (SLLG) and Single Layer, Tree Traversal (SLTT) all use greedy type expansion but with different traversal rules. SLUG enables unlimited movement on the gradient, in SLLG the movement is limited to a gradient steepness of 1 and in SLTT the movement is further limited to only those originating from the current cell. In addition, all use BPC but with different retracing rulesin SLUG movement down the gradient is possible on both Beacons and Closed Beacons while in SLLG and SLTT it is possible only on Closed Beacons. The fourth SLC algorithm, Single Layer, Depth First (SLDF), uses a depth first exploration strategy unlike the other three single layer algorithms with retracing limited to Closed Beacons. The effect of these factors along with the effect of the entry point location on the performance is investigated in the third part of this section.
The results are derived from a simulator developed and implemented by the authors using the NetLogo programming language. Three different regions-a line, a square and a repeating multi-connected region -were investigated for both the effect of size and topology. An additional three regions, representing more complex and real-life regions were also investigated. The topologies are presented in Figure 45 and the list of the regions (size and topology) tested is detailed in Table 1. Each data point in the all the following graphs is the average of fifty runs unless specifically noted. Figure 45 Regions used in the simulations. The regions in sub-figures (a)-(c) are used to investigate the effect of region shape. The bottom three regions represent more realistic regions and first appeared in [45]. The walls are marked in white, the empty cells in black and the entry point is at the upper-left corner and marked in blue.

Dual Layer Coverage algorithms
The number of agents as a function of time , ( ), from sample runs of the three Dual Layer Coverage algorithms -DLRW, DLLG, DLUG -is presented in Figure 46. A linear region with 120 cells, the entry point at the left terminal cell and = 1 is used. The horizontal axis is the time while the vertical axis is the number of agents. The major difference between the algorithms is in the effective rate of agents' entry. The slope is linear-like in DLUG and DLLG indicating that the number of times the entry of an agent to the region is blocked (because the entry point is occupied) is nearly constant. On the other hand, in DLRW the slope (i.e., the entry rate) monotonously decreases indicating that as the number of agents inside the region increases so does the probability that there will be a mobile agent in the entry point blocking the entry of additional agents. Table 2 summarizes the termination time and total energy of the three DLC algorithms in the coverage process of linear regions. Clearly, the termination times and total energy consumption of the DLRW algorithm are significantly larger than those of the DLLG and DLUG algorithms. Consequently, in the rest of this section the discussion on the DLC algorithms will focus on the DLLG and DLUG algorithms.   The theoretical analysis in section 4 predicts the termination time is linear with region size and for ≥ 2. Thus, we start by looking experimentally into the differences in the performance of the Dual Layer Coverage algorithms for = 1 and = 2 . The effect of the region size on the termination time and the total energy with = 1 is depicted in Figure 47. The lower bound and the upper bound (based on Conjecture 1 and 2) are shown in Figure 47(a) in black. With respect to the termination time, all the results are within the bounds supporting both Conjectures. It is noteworthy that the termination times of the linear regions are the longest for a given size and very close to the upper bound. Moreover, the termination times of DLLG and DLUG are very close and in most regions the difference is imperceptible. In Figure 47 (b) the total energy consumption is shown and while in most regions is similar there is a definite difference in the square regions. Given the random nature of the process, in a large, unobstructed region such as a square there is a higher probability that a mobile agent will move over a gradient greater than one compared to more obstructed regions such as the saw-tooth. Such movement will shorten the trajectories of the agent and reduce their energy consumption. Consequently, the main insight from Figure 47 is that the looser traversal rules in DLUG mostly effect the . When ≥ 2 the termination times, for a given region size, should all depend exclusively on the regions size. This understanding is supported by the results in sub- Figure 48(a) for all the regions. Additionally, from Figure 48(b) the difference in the total energy between DLLG and DLUG is largest in the square regions and this fact supports the insight gained from the plots for = 1. Polynomial trendlines of the 2nd order with an intercept of 0 are shown for the total energy. The fit is good indicating the total energy may be a quadratic function of the region size. The effect of on the termination time in the DLC algorithms is shown in Figure  49. Figure 49(a) shows the termination time as a function of using Dual Layer, Limited Gradient algorithm and similarly Figure 49 Figure 52 shows the total energy for the different regions using = 4, 8 and 16. The energy consumption of the different algorithms is denoted by the markers and trendlines for both algorithms are denoted by the dotted lines. A 2 nd order polynomial is used with the intercept point set to 0 hence of the form: = 2 2 + 1 . This model was selected based on the notion that at least agents participate in the process and the time an agent is mobile is approximately the distance it travels which is bounded by n and thus the total energy is proportional to 2 . The good approximation is clear from the high values of 2 in Figure 52 and Figure 48(b) . As evident, doubling of results in close to a doubling of the 2 coefficient hinting that is a linear function of as well as a quadratic function of 2 when ≥ 2. These results merit further research.  Figure 52 shows the total energy for the different regions using = 4, 8 and 16. The energy consumption of the different algorithms is denoted by the markers and the trendlines for both algorithms are denoted by the dotted lines. A 2 nd order polynomial is used with the intercept point set to 0 hence of the form: = 2 2 + 1 . This model was selected based on the notion that at least agents participate in the process and the time an agent is mobile is approximately the distance it travels which is bounded by n and thus the total energy is proportional to 2 . The good approximation is clear from the high values of 2 in Figure 52 and Figure 48(b). As evident, doubling of results in close to a doubling of the 2 coefficient hinting that is a linear function of as well as a quadratic function of 2 when ≥ 2. These results merit further research.

The Single Layer Coverage algorithms
The bounds on the termination time of the Single Layer Coverage algorithms differentiate between the case of = 1 and ≥ 2 . We therefore start by examining the behavior of the algorithms for = 1 and for = 2 as shown in Figure 53 and Figure 54 respectively. The termination times in all the regions, as shown in sub- Figure  53(a), are lower than the upper bounds predicted by Lemma 1 and Conjecture 3 they are however further from the upper bound then in the Dual Layer Coverage algorithms (Figure 47(a) and Figure 48(a)). Additionally, for both = 1 and 2 the , and in the linear regions are the same regardless of the algorithm used (also observed in the DLC algorithm). This is because in linear regions the gradient is always one and coincides with the directions of the arrows in the tree traversal algorithm. In the other regions the differences in performance between the four algorithms is clear, especially for = 2. SLUG shows the best performance i.e., lowest values) followed by SLTT, SLLG and lastly SLDF. The relative order in interesting since SLUG has the richest DAG while SLTT is a tree. The reason behind this phenomenon is discussed later in this section. In Figure 53(d) and Figure 54(d) the maximum specific energy consumption (max ( ) ) is presented. It is clear that SLLG out-performs SLTT in this metric in both = 1 and 2 . This means that in the examined scenarios the required minimal energy of an agent using SLLG is lower than that of SLLT however overall SLTT is more energy efficient compared to SLLG. In the following figures the effect of on the three macro performance metrics is investigated. In Figure 55 the termination time is shown as a function of for the various Single Layer Coverage algorithms. While the linear dependency of the termination time on is clearly seen the termination times of the different algorithms are not the same. Figure 56 presents the same data only now given as the ratio of the termination time to the region size along with the theoretical upper bound. It is readily apparent that the ratio is linear with . Furthermore, in all the algorithms that use greedy type exploration -SLUG, SLTT and SLDF -the lines corresponding to the linear regions overlap and are consistently higher than the lines for the other regions. This indicates that in both algorithms the linear case is the worst case. In SLDF, however, all the lines practically merge indicating weak sensitivity to the topology as is expected in depth-first exploration in which the underlying graph is a depth-first tree. The effect of on the number of agents used in the process is shown in Figure  57 as the ratio between the number of agents used and the region size. This normalized representation of N enables easy comparison between the different regions. As all the linear regions used exhibit the same dependency on they are plotted as one curve. We see in all the sub-figures a similar trend of a decrease in the number of agents as increases. This is because the Close indication has more time to propagate as increases and thus better funneling of the entering agents to the empty parts of the region is achieved. Furthermore, the ratio converges to 1 (i.e., ≈ ) at = 16. In other words, further increase in will yield negligible reductions in the number of agents used. It is interesting to see that the steepness of the gradient (i.e., the rate the number of agents decreases for a unit increase in ) differs from one algorithm to another algorithm and in some cases between the different types of regions in a given algorithm. The simpler the region is for exploration (with the linear region being an extreme case) the swifter the reduction in the number of agents and vis-versa. In addition, the effect of the region on the ratio is much smaller in SLDF and the behavior closely resembles that of the linear regions. Both are due to the depth-first exploration strategy. . This finding is surprising since SLUG has the loosest traversal rules and richest DAG compared to SLTT which is limited to traversal on a tree. Additionally, and regardless of , all the SLC algorithms give the same results when the region is linear. In all sub-figures, a trendline of the total energy as a function of region size in the linear regions is presented. It is clear from the trendlines that the total energy in linear regions upper bounds the total energy in all other regions. Moreover, it is a quadratic function of (as was noted above for = 2). Comparison of the results with those of the Dual Layer Coverage algorithms ( Figure 52) shows that in the DLC algorithms increases with while in the SLC algorithms it decreases. This is due to two reasons. First, in the DLC algorithms increasing increases the time that stationary mobile agents (i.e., those that advanced up the gradient and then stopped) consume energy. Second, in the SLC algorithms increasing results in the more effective funneling of the mobile agents to the relevant parts of the region. This is due to improved propagation of the Close indication.

Effect of the entry point location
The effect of the entry point location on the performance was investigated using three regionstwo simple, connected regions of approximately 420 cells and complex region #1 with 636 cells. To the best of the authors knowledge there are no previous results on the matter. The different locations in each region are marked and enumerated in the figures below with the original entry point denoted by "o". At each entry point location, the termination time and total energy were measured using the two Dual Layer Coverage algorithms and four Single Layer Coverage algorithms described above. Below each figure the termination time and total energy are given for each of the locations as both the absolute values and more importantly as the ratio of the measured quantity to the same quantity at the original location. Points (a)-(d) in region Complex #1 are characterized by an outdegree ‡ of 2, points (e)-(h) with an out degree of 3 and points (i)-(l) with an out degree of 4. The main takeaways are: 1. In a given region, SLDF is indifferent to the location of the entry point with regard to both the termination time and total energy. 2. The termination time and total energy are more effected by the proximity of the entry point location to the geometrical center of the region than the outdegree of the cell. This is clearly seen when comparing the termination times and total energies associated with entry points of d and l in the complex region. It's clear that while the out-degree of d is 2 compared to 4 in l the termination time and total energy are noticeably better in d compared to l. It should be pointed that in some regions (e.g., the square) the change in both metrics due to moving the entry point from the corner to the center of the region is quite small. Practically this means that, if possible, rescue workers should strive to place the entry point near the geometric center of the region. 3. Predominantly the DLC algorithms behave alike in all combinations of regions/entry points evaluated as do the four SLC algorithms. 4. In all cases the theoretical upper bound on the termination time is correct. for an entry point to the total energy using the original entry point

Effect of the traversal rules
The effect of the looseness of the traversal rules on both and is shown in Figure 65 as the ratio (of both metrics) between the different Dual Layer Coverage algorithms. Using the DLC algorithms gives the clearest perspective on the effect of the traversal rules since this is the only difference between the algorithms. In this comparison we also look at the two-layer coverage algorithm which inspired Single Later, Tree Traversal and is described in [44]. We naturally name it -Dual Layer, Tree Traversal (DLTT). The agents in that algorithm generate a directed tree over the region hence the traversal rules in this algorithm are the most limited of the three. In all the plots, the metric of the Dual Layer, Unlimited Gradient algorithm is in the denominator since DLUG has the loosest traversal rules hence when the ratio is greater the 1 it indicates DLUG has better performance and vis-versa when the ratio is less than 1. Figure 65(a) shows the ratio of the termination times when = 1 ratio (when ≥ 2 the in all three DLC algorithms is the same as shown above). It is clear from the ratio of between DLLG and DLUG that the effect of the traversal rules is minor regardless of the region type. However, when looking at the ratio of between DLTT and DLUG the effect of the traversal rules is both noticeable and dependent upon the region type. In other words, traversal on a DAG decreases the compared to traversal on a tree while the effect of the number of edges in the DAG on is negligible. Similarly, Figure 65 for several values of . The effect of the traversal rules on is more pronounced between DLTT on the one hand and DLLG and DLUG on the other. Moreover, while the ratio is almost not dependent on it is upon the topology of the different regions. To summarize, the traversal rules effect both the termination time and the total energy and this is due to the associated underlying graph with the most significant change caused when the underlying graph structure is a tree versus a DAG.

Effect of the Backward Propagating Closure
In this section the performance improvements achieved by using the Backward Propagating Closure meta-concept are reviewed. The main difference between the DLC and SLC algorithms is due to this concept that simultaneously generates a deterministic indication of termination to an external observer, funnels the advancing agents to the relevant parts of the region and enables the return of the superfluous agents to the entry point/s. The improvements due to the BPC concept are investigated by using the ratio of the three performance metrics when using a DLC algorithm and when using the complementary SLC algorithm (e.g., / ) for = 1, 2 and 4. By using the ratios rather than the absolute values the improvement is immediately obtained. Specifically, the higher the ratio the bigger the improvement in , and N due to the BPC meta-concept. Several facts are readily apparent from Figure 66 that shows the ratios of the number of agents used.
1. There is a significant reduction in N which increases as increases. 2. The reduction in the number of agents used in the linear regions is independent of region size or traversal rules but depends on . This means that for a given , is linear with size since the number of agents in the DLC algorithm is always 2 . 3. For a given , the ratio / is always the largest of the three ratios. This means that the reduction in is maximal in SLUG (since the number of agents in the DLC algorithm is always 2 ) or in other words the contribution of the BPC is maximal in SLUG. 4. In most cases / is greater than / which means that the BPC is more effective (in reducing N) in SLTT then in SLLG. At first glance this is surprising since traversal in SLTT is more constrained compared to SLLG and it was shown above that DLLG out-performs DLTT (Figure 65). The reason for above result is the different definition of Closed Beacon used in SLTT compared to SLTT. Transition of a settled agent in SLLG to Closed Beacon in most cases depends on at least as many neighboring cells as in SLTT if not more. This is a direct outcome of Eq.  Figure 67 shows the ratios of the termination times of comparable DLC and SLC algorithms. In the linear regions the ratio is constant and greater than one for a given which means that the SLC algorithms (on average) terminate faster than the DLC algorithms. However according to the ratio of upper bounds derived in the previous sections the ratio should be smaller than one. The reason for this discrepancy is the use of an adversarial scheduler in the derivation of the expressions. While this assumption gives the upper bounds its probability of occurring is extremely small. Hence, when the wake-up order is uniformly distributed the BPC propagates significantly faster and consequently both the process terminates faster and the number of agents participating the process is smaller. Additionally, for a given and region size, the ratio of / is the largest of the three indicating (again) that the biggest improvement is achieved when using SLUG. The reduction in the total energy due to the BPC concept is clearly seen Figure 68. For a given region size the ratio of of comparable DLC and SLC algorithms is greater than 1 when = 1 and increases with . This increase is the result of the increase in both the energy consumption by the stationary agents in DLC and the effectiveness of the funneling in the SLC algorithm. And again, the greatest improvement is when comparing the SLUG to DLLG. Summing we see that use of the BPC significantly improves performance of the SLC algorithms in addition to giving the user the deterministic indication of termination. In this section the performance of the each of the algorithms was reviewed and compared to the other algorithms. In the DLC algorithms the termination time is linear with respect to size and for ≥ 2 while the total energy is quadratic with the region size with the coefficient of the quadratic term being linear with . In the SLC algorithms the correctness of the upper bound on the termination time is corroborated by the experimental results. A correlation between the looseness of the traversal rules and the termination time was found. In addition, the effect of the entry point location depends mostly on its proximity to the geometrical center of the region and to a lesser degree on outdegree. Most importantly, the benefit of using the BPC meta concept was investigated quantitively and found to be significant.

Conclusions
Seven algorithms based on two meta-concepts are described in this paper. All the algorithms are based on the meta-concept of dual use agents -as mobile explorers and as settling agents that function as beacons. The Single Layer Coverage algorithms also utilize a second meta-conceptthe Backward Propagating Closure.
Good correlation is found between the theoretical bounds of the termination time and the experimental results. Moreover, the experimental results led to several conjectures about the termination time in algorithms in which the upper bounds are yet to be analytically developed. The primary effect on the termination time is the region size, however in the SLC algorithms the effects of region topology (esp. the number of holes) and the entry point location are not negligible.
The termination time shortens as the sensed data and complexity of the algorithms increases. With the DLRW being the simplest algorithm and only the presence of the settled agents used to guide the mobile agents the termination times are correspondingly the worst. A large improvement is seen with the introduction of the step count as a means to guide the exploration with a corresponding increase in the sensing requirements and the algorithm's complexity. Use of the Backward Propagating Closure meta concept in the SLC algorithms further reduces the number of agents used, total energy and the termination time.
Further work remains in deriving explicit, theoretical bounds on the termination time. This is especially true regarding the case of = 1 and/or the unlimited steepness version of the algorithms. Another issue that merits further research is the effect of multiple entry points on the various metrics. While the algorithms presented were designed with multiple entry points in mind, both the mathematical analysis and numerical experiments in this research dealt with the case of a single door.
The Single Layer Coverage algorithms are fault tolerant with a couple of minor modification however the topic as a whole and specifically the interaction between the different failure modes merits further research.