-
Notifications
You must be signed in to change notification settings - Fork 20
Area Coverage
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. Examples in this article assume we are working with the agent
with .id of 1.
Each algorithm is initiated with a different command (device.{.id}.command). The area to cover is
specified in argument 0 (device.{.id}.command.0="region.0"). Either a region or a search area can be
used to specify the location to cover. If an algorithm expects a region but gets a search area,
then the convex hull of the search area will be used. If an algorithm expects a search area but
gets a region, then a search area consisting of the single search area will be used.
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.
| Key | Value |
|---|---|
| command | "urac" |
| command.0 | region to cover |
This is the simplest of the area coverages. It selects the next waypoint from a uniform random distribution over the region.
| Key | Value |
|---|---|
| command | "urec" |
| command.0 | region 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.
| Key | Value |
|---|---|
| command | "pwrac" |
| command.0 | 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. This algorithm reduces to Uniform Random Area Coverage
if a region is used for command.0.
Computed coverages perform some initial analysis to determine a series of waypoints before executing any actions.
| Key | Value |
|---|---|
| command | "snake" or "sac" |
| command.0 | 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. This is also known as a lawnmower pattern.
| Key | Value |
|---|---|
| command | "perimeter patrol" or "ppac" |
| command.0 | region to patrol |
Agents travel to the closest vertex of the region. They then move along the edges from vertex to vertex ad infinitum.
| Key | Value |
|---|---|
| command | "waypoints" |
| command.0 | first location |
| command.1 | second location |
| ... | ... |
| command.n | last location |
Agents travel from location to location in the specified order. This reduces to perimeter patrol when the locations are the ordered vertices of a region.
Sensor coverages use some sensor (either physical or virtual) to determine the next waypoint.
| Key | Value |
|---|---|
| command | "local pheremone" |
| command.0 | 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)
| Key | Value |
|---|---|
| command | "min time" or "mtac" |
| command.0 | 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
| Key | Value |
|---|---|
| command | "prioritized min time" or "pmtac" |
| command.0 | 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
The formation coverage algorithm has agents perform area coverage in a formation.
| Key | Value |
|---|---|
| command | "prioritized min time" or "pmtac" |
| command.0 | lead agent |
| command.1 | offset |
| command.2 | members |
| command.3 | modifier |
| command.4 | coverage |
| command.5-n | coverage args |
The first four arguments are identical to those used in the formation algorithm. The first arg is
the id of the agent that will act as the leader in the formation. The second argument is the member
list (e.g. 4,3,5,6,2 specifies that four agents will take part in this algorithm and they are
agents 3, 5, 6, and 2). If the modifier argument is "rotation", then the agents will rotate around
the lead agent. The rest of the arguments initialize the coverage that will be performed.
The table below shows how to setup a formation coverage for uniform random edge coverage in "region.5" led by agent 2 with agents 1, 3, and 5 participating.
| Key | Value |
|---|---|
| command | "pmtac" |
| command.0 | "2" |
| command.1 | "0,0,0" // this will be different for every agent |
| command.2 | "4,2,1,3,5" |
| command.3 | "default" |
| command.4 | "urec" |
| command.5 | "region.5" |