-
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.
- Introduction
- Common Characteristics
- Random Coverages
- Computed Coverages
- Sensor Coverages
- Formation Coverage
Each algorithm is initiated with a different algorithm (agent.{.id}.algorithm). The area to cover is
specified in args member area (agent.{.id}.algorithm.args.area="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.
Each algorithm has an option time argument at the end of the listed arguments. After an algorithm has executed for the specified amount of time, the algorithm marks itself as finished and the algorithm ceases. This option is disabled by either leaving out the option or passing 0 for the argument.
The entire process can be summarized as:
while(time still available)
if(current position is approximately equal to target position)
pick new target position
move to target position
The functions called are analyze, plan, generate_new_position, and execute. analyze
checks if the specified amount of time has passed. If it has, then the algorithm marks the
algorithm status variable as finished and the functions returns the FINISHED value. This function
is virtual and can be overwritten.
plan checks if the current location is approximately equal to the target location. Approximately
equal is defined using the get_accuracy method in platform. If the locations are approximately
equal, then a new target location is picked by calling generate_new_position.
generate_new_position is a pure virtual function in Base_Area_Coverage. Custom area coverage
algorithms inheriting from Base_Area_Coverage need only fill in this function to inform the
algorithm where to go next to have a functioning area coverage algorithm.
execute calls the platforms move function with the target location. The platform move function
must not block and must be resilient to successive calls with the same target location argument.
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 |
|---|---|
| algorithm | "urac" |
| algorithm.args.area | 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 |
|---|---|
| algorithm | "urec" |
| algorithm.args.area | 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 |
|---|---|
| algorithm | "pwrac" |
| algorithm.args.area | 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 algorithm.args.0.
Computed coverages perform some initial analysis to determine a series of waypoints before executing any actions.
| Key | Value |
|---|---|
| algorithm | "snake" or "sac" |
| algorithm.args.area | 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 |
|---|---|
| algorithm | "perimeter patrol coverage" or "ppac" |
| algorithm.args.area | 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 |
|---|---|
| algorithm | "waypoints coverage" |
| algorithm.args.0 | first location |
| algorithm.args.1 | second location |
| ... | ... |
| algorithm.args.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. The difference is this will only go through the list of waypoints once.
Waypoints coverage uses Base_Platform::get_accuracy() to determine if the platform has reached the intended waypoint. If it has reached the waypoint, then the next location is selected as the new target. Upon reaching the last location in the argument list, the algorithm finished status is set and analyze returns a FINISEHD value.
Sensor coverages use some sensor (either physical or virtual) to determine the next waypoint.
| Key | Value |
|---|---|
| algorithm | "local pheremone" |
| algorithm.args.area | 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 |
|---|---|
| algorithm | "min time" or "mtac" |
| algorithm.args.area | 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 |
|---|---|
| algorithm | "prioritized min time" or "pmtac" |
| algorithm.args.area | 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 |
|---|---|
| algorithm | "formation coverage" |
| algorithm.args.head | lead agent |
| algorithm.args.offset | offset |
| algorithm.args.group | group name |
| algorithm.args.modifier | modifier |
| algorithm.args.coverage | coverage |
| algorithm.args.coverage.args | coverage args |
The first four arguments are identical to those used in the formation algorithm. The first arg is
the id (e.g., agent.0) of the agent that will act as the leader in the formation. The second argument is the agent's offset from the lead agent. The third argument is the
group name (e.g. group.group1), which specifies that members of group1 will take part in this algorithm and they are
in the fixed list or transient group. 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 |
|---|---|
| algorithm | "formation coverage" |
| algorithm.args.head | "agent.2" |
| algorithm.args.offset | "0,0,0" // this will be different for every agent |
| algorithm.args.group | "group.formation" |
| algorithm.args.modifier | "default" |
| algorithm.args.coverage | "urec" |
| algorithm.args.coverage.args.area | "region.5" |