Area Coverage

Introduction

A swarm is instructed to move over an area while taking sensor measurements. The algorithm controlling movement is referred to as the Area Coverage algorithm and each can use different input modes to determine the next waypoint.

---

Common Characteristics

device.1.command="cover";
device.1.command.0="urac";
device.1.command.1="region.0";

Area coverage is initialized with the cover command (device.1.command="cover"). The specific algorithm to execute is in argument 0 (device.1.command.0="urac") and the area to be covered is specified in argument 1 (device.1.command.1="region.0"). Either a region or a search area can be used to specify the location to cover. If an algorithm uses a region but gets a search area, then the convex hull of the search area will be used. If an algorithm uses a search area but gets a region, then a single region search area will be used.

---

Random Coverages

Random coverages use some random distribution to determine the next waypoint. A point is selected from some probability distribution. Upon reaching the waypoint, the next waypoint is selected.

Random Area Coverage

|| argument 0 || "urac" || || argument 1 || region to cover ||

This is the simplest of the area coverages. It selects the next waypoint from a uniform random distribution over the search area. If a search area is provided in argument 1, then the convex hull of the regions included in the search area is used as the area to search.

Uniform Random Edge Coverage

Argument	Value
0	"urec"
1	region or search area to cover

An edge of the convex polygon is selected using a uniform random distribution. The next waypoint is then selected also using a uniform random distribution over the selected edge. As with Uniform Random Area Coverage, if a search area is provided in argument 1, then the convex hull of the regions included in the search area is used as the area to search.

Priority Weighted Random Area Coverage

Argument	Value
0	"pwrac"
1	search area to cover

The next waypoint is selected as a function of the area of the region and the priority of the region. For example, given regions A and B of equal area with A.priority=10 and B.priority=5, a point in region A will be selected twice as often. Given regions C and D with C.area=1, C.priority=1, D.area=5, and D.priority=5, there will be on average 25 selections of a point in region D for every selection in region C.

---

Computed Coverages

Computed coverages perform some initial analysis to determine a series of waypoints before executing any actions.

Snake Area Coverage

Argument	Value
0	"snake" or "sac"
1	region to cover

Parallel lines are traveled over the entire area. The longest edge is selected as the first traversal points and then offset parallel lines are traversed until the area is covered (also known as lawnmower pattern). This provides the fastest possible coverage as every step adds to the covered area and no points are covered twice.

---

Sensor Coverages

Sensor coverages use some sensor (either physical or virtual) to determine the next waypoint.

Local Pheremone Coverage

Argument	Value
0	"local pheremone"
1	region to cover

Each discretized cell in the area is initialized to have no pheremone in each discretized cell. At each time step, the agent selects the neighboring cell (using 8-way connectivity) with the lowest pheremone density, updates the pheremone in that cell, then moves to it. The pheremone value set in a cell in this algorithm is the current time.

cur = current position
next_position = cur
min_cover = DBL_MAX
foreach cell i in neighbors (cur):
  if i.last_covered < min_cover:
    next_position = i
    min_cover = i.last_covered
next_position.last_covered = current time
move (next_position)

Min Time Coverage

Argument	Value
0	"min time"
1	region to cover

Each discretized cell in the area is initialized to 0. At each time step, the drone increments the utility for every cell in its local knowledge base, finds the cell that gives the highest utility path, then travels to that cell. The utility of each cell on the path is then reset to 0.

cur = current position
next_position = cur
max_utility = 0
foreach cell i in area:
  cell_utility = 0
  foreach cell j in area:
    if j in path (cur, i):
      cell_utility = cell_utility + j.utility
  cell_utility = cell_utility / distance (i,j)
  if cell_utility > max_utility:
    next_position = i
    max_utility = cell_utility

foreach cell i in path (cur, next_position):
  i.utility = 0

Prioritized Min Time Coverage

Argument	Value
0	"prioritized min time" or "pmtac"
1	search area to cover

Each discretized cell in the area is initialized to 0. At each time step, the drone increments the utility for every cell in its local knowledge base, finds the cell that gives the highest utility path, then travels to that cell. The utility of each cell on the path is then reset to 0.

This is nearly identical to Min Time Coverage with the exception that cell utility is multiplied by its priority. The priority of a cell is the maximum of the priority of each region it belongs to.

cur = current position
next_position = cur
max_utility = 0
foreach cell i in area:
  cell_utility = 0
  foreach cell j in area:
    if j in path (cur, i):
      cell_utility = cell_utility + j.utility * j.priority
  cell_utility = cell_utility / distance (i,j)
  if cell_utility > max_utility:
    next_position = i
    max_utility = cell_utility

foreach cell i in path (cur, next_position):
  i.utility = 0