PDF Archive

Easily share your PDF documents with your contacts, on the Web and Social Networks.

Share a file Manage my documents Convert Recover PDF Search Help Contact



MultiRobotAdversarialCoverageAppendix.pdf


Preview of PDF document multirobotadversarialcoverageappendix.pdf

Page 1 2 3 4 5 6 7 8

Text preview


1:

2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

1:

2:
3:
4:
5:
6:

procedure Allocate Areas To Robots(A, R, d)
input: A - list of connected areas, R - the group of robots, d - maximal
area density
S ← {A|A ∈ A ∧ A.level = 0}
. the safe areas
for each robot R ∈ R do
{Find safest paths to all safe areas}
for each area A ∈ S do
PA ← Find Safest Path To Area(A, R.location)
{Find safest non-dense area}
Let A1 , ..., Ak be the areas sorted by PA .cost
i←1
while i ≤ k and R.area = null do
if |A.initial robots| · d ≤ |A.cells| then . check if area is not too
dense with robots
Add R to A.initial robots
else
i←i+1
{Split the areas that are allocated to multiple robots}
for each area A ∈ S do
if |A.initial robots| > 1 then
Split Area Between Robots(A)
else if |A.initial robots| = 1 then
R ← A.initial robots[0]
R.path ← PA
Assign Area To Robot(A, R)

procedure Find Safest Path To Area(A, s)
input: A - a connected area, s - a cell in the grid
output: P - the safest path connecting s to a cell in A
Build the graph H induced from the grid’s cells
Run Dijkstra shortest paths algorithm on H from s
for each cell c ∈ A do
Pc ← the safest path from s to c
return arg minPc cost(Pc )

3