Information Technology Reference
In-Depth Information
Each agent,
a ∈ A
, is autonomous and independent decision maker which is de-
scribed by the touple
a
=
{p
a
(
t
)
,ρ
a
,d
[
a
max
} ,
(1)
and, similarly, agent
θ ∈ Θ
by the touple
θ
=
{q
θ
(
t
)
,ρ
θ
,d
[
θ
max
} ,
(2)
where
ρ
a
∈
R
>
0
and
ρ
θ
∈
R
>
0
are a fixed transmitting (communication) range (radius)
of agent
a
's and agent
θ
's wireless transceiver for limited range communication respec-
tively.
d
[
a
max
and
d
[
θ
max
are the maximum movement distance (maximum step size) of
agent
a ∈ A
and agent
θ ∈ Θ
respectively, at the beginning of time period
t
.Atany
time period
t
, each agent
a
knows its position
p
a
(
t
) and the position
q
θ
(
t
) of each oppo-
site group's agent
θ ∈ Θ
.Let
c
aθ
(
t
) be the (Euclidean) distance between the positions
of agents
a
and
θ
.
Examples of such a two-group agent setup can be found in mobile sensor networks
and in unmanned aerial vehicles (UAVs) where mobile agents can move to follow and
track mobile targets, the position of which is globally known to all the agents (through,
e.g., global positioning system).
As the agents of both groups move in the environment toward their preferred target
agents, the conditions of the relative proximity of the agents of two groups in the envi-
ronment change so that the closest agent
a
(
θ
) in one period can become more distant
than some other agent which was further away in the period before. In each period
t
,
each agent
a
is able to communicate to a set of agents
C
a
(
t
)
⊆ A
(belonging to the
same connected component of its own group) reachable in a multi-hop fashion within
the communication graph; at any time period
t
, the latter is a random geometric graph
(RGG) [4], that is the undirected graph
G
a
(
t
)=(
A, E
a
(
t
)) with vertex set
A
randomly
distributed in some subset of R
2
, and edge set
E
a
(
t
) with edge (
i, j
)
∈ E
a
(
t
) if and
only if
p
i
(
t
)
− p
j
(
t
)
2
≤ ρ
a
.
(3)
The exact same logic applies to the agents of the opposite group
Θ
which are able to
communicate to a set of agents
C
θ
(
t
)
⊆ Θ
reachable in a multi-hop fashion within the
communication graph
G
θ
(
t
)=(
A, E
θ
(
t
)). In this way, two agents of a same group
which are not within the communication range of each other can communicate over a
third agent within the same group (communication relay point) in a multi-hop fashion
as long as the latter is placed within the communication range of the both. Therefore,
agent
a
together with the set of agents communicating with the same induce a connected
subgraph (connected component) of
G
a
(
t
). The same principle stands for agent
θ ∈ Θ
and its communicating agents resulting in a connected component of
G
θ
(
t
).
We consider the problem of dynamic assignment of two groups of mobile agents:
A
to
Θ
,and
Θ
to
A
where each agent of one group has to be assigned to at most one mobile
target agent of the opposite group. The total traveled distance of all agents which move
towards their assigned targets has to be dynamically minimized. We assume that no a
priori global assignment information is available and that agents are collaborative and
only receive information through their local interaction with the environment and with
the connected agents in the communication graph of the same group. Agents commu-
nicate the assignment data and negotiate with the agents of the same group while there
