Information Technology Reference
In-Depth Information
are designed as self-interested participants in a virtual economy in which they nego-
tiate on the target cost [3], maximizing their individual rewards and minimizing their
individual costs.
In a general case of the multi-robot task assignment (MRTA) problem, any robot
agent can be assigned to a task which consists of a target location that needs to be
visited by a robot. A formal analysis and review of the MRTA problem and algorithms
can be found in e.g., [6,7]. Approaching the MRTA problem through a market-based
mechanism can be found in, e.g., [3,10,8].
Dynamic task reallocation allows robots to change their behavior in response to
environmental changes or actions of other robots in order to improve overall system
performance. There are a number of task allocation algorithms and most of them re-
quire a complete communication graph among agents (e.g., [20,2,1,1,8,9,10,13,14,19]).
Coordination algorithm for task allocation that uses only local sensing and no direct
communication between robots was presented in [11]. In a real-world distributed multi-
robot operation, updated shared information is necessary in all the applications requir-
ing cooperative and coordinated multiple robot task assignment. A multi-agent system
in which agents have limited communication capabilities achieves an optimal target
assignment solution if the global information is up- to-date and at the disposal of all
decision makers (agents) at least in a multi-hop fashion; sufficient condition for optimal
solution is that the communication graph among agents is connected [20,19]. Dynamic
breaking and (re)-establishment of communication links among robots can be due to
e.g., unpredicted environmental obstacles, wireless transceiver imperfections, fading or
robots drifting beyond the range of the wireless radios link bandwidth, delays, need for
encryption, message mis-ordering, as well as range constraints due to physical setup of
the network or to the power limitations on communications [9].
The critical transmitting range (CTR) for connectivity is a minimum common value
of the agents' transmitting range that produces a connected communication graph. At
CTR, all global data is available to each agent and if the communication range is lower
than CTR, agents' decisions are sub-optimal due to the lack of updated information.
Critical transmitting range was a topic of diverse works, e.g., [15,16,17,18]. In [16],
CTR in an obstacle free area of limited size was proven to be ρ M = c ln n/ ( πn ) for
some constant c ≥ 1,where n is the number of network nodes (agents) and M is some
kind of node mobility.
Within the context of two mobile groups of agents, the correlation between the dy-
namics of the solution of the distributed multi-agent target assignment problem in re-
spect to the variation of the agents' communication range under the critical transmitting
range, has not been explored so far to the best of our knowledge.
3
Problem Formulation and Definitions
Considering a time horizon made of T time periods, given are two distinct groups, each
one made of n collaborative mobile robot agents: group A = {a 1 ,...,a n }
and group
Θ = 1 ,...,θ n }
, both represented by points in the plane. The agents are positioned,
w.l.o.g., in a square environment E =[0 ,l ] 2 R 2 of side length l> 0, with p a ( t ) ∈ E
being the position of agent a ∈ A at the beginning of time period t
=1 ,...,T ,and
q θ ( t ) ∈ E being the position of agent θ ∈ Θ at time t =1 ,...,T .
Search WWH ::




Custom Search