Information Technology Reference
In-Depth Information
of the agents' transmitting range (radius): the larger the range, the less likely it is that
the network becomes disconnected. From a communication-theoretic perspective, the
critical transmitting range (CTR) for connectivity is a minimum common value of the
agents' transmitting range that produces a connected communication graph in order to
achieve and maintain network connectivity. At CTR, all global data is available to each
agent. Under this value, starts the creation of detached connected components and when
the value of communication range is zero, the agents communicate only over the tar-
get states (free or occupied). If communication range is under CTR and, therefore, the
information at the disposal of agents (decision makers) is not up-to-date and complete,
then we naturally expect to achieve a poor group decision making and lower levels of
cooperation and hence assignment performance.
In this paper, we consider the problem of dynamic assignment of two groups of
mobile agents with the objective of minimization of the total distance of movement
of both. Each agent of one group has to be assigned to at most one mobile target
agent of the opposite group. We propose a dynamic auction algorithm with mobility
for multi-agent coordination since the classical Bertsekas' auction algorithm [2] will
not guarantee an optimal or even feasible assignment with insufficient communication
range for complete communication graph, and certain modifications are necessary. To
respond to this open issue, in [12], was presented a distributed and dynamic version of
Bertsekas' auction algorithm [2] for the case when one group of mobile agents moves
toward the targets placed on static positions in the environment. The algorithm finds
minimum total length routes from agents' initial to distinct final positions (targets) in
the multi-agent target assignment problem with a disconnected communication graph.
In the present work, we go a step forward and present a modified auction algorithm
for the case when both the robots and their targets are mobile agents that if assigned to
one another, move closer until they don't intercept. Through this algorithm, we explore
the connection between the assignment solution of two mobile agent groups and the
sparsity of communication graph varying from a connected communication graph to
the case with only isolated vertices. Furthermore, we investigate how the lack of com-
munication network connectedness among agents and the varying quantity of the infor-
mation exchanged among communicating agents in the negotiation process influences
the assignment solution. We prove through simulations that in the context of dynamic
unpredicted environments and the communication range insufficient to maintain con-
nected communication network, the policy of no exchange of assignment information,
resulting in a selfish behavior, is the most adequate policy.
The paper is organized as follows. In Section 2 we treat a related work. In
Section 3, problem formulation and definitions are presented. In Section 4, the mod-
ified distributed auction algorithm for the case of mobile agents and their targets and
disconnected communication graph is presented. Section 5 contains simulation results
demonstrating the performance of the presented auction algorithm. The conclusions are
found in Section 6.
2
Related Work
Market-based coordination approaches have been implemented in many multirobot sys-
tems (e.g., [5,14,1,3,8,11,12,20]). Robot-agents in a market-based multi-agent system
