Information Technology Reference
In-Depth Information
Value of Incomplete Information in Mobile Target
Allocation
Marin Lujak
1
, Stefano Giordani
2
, and Sascha Ossowski
1
1
University Rey Juan Carlos, Madrid, Spain
2
Dip. Ingegneria dell'Impresa - University of Rome “Tor Vergata”, Italy
Abstract.
In this paper, we consider a decentralized approach to the multi-agent
target allocation problem where agents are partitioned in two groups and every
member of each group is a possible target for the members of the opposite group.
Each agent has a limited communication range (radius) and individual prefer-
ences for the target allocation based on its individual local utility function. Fur-
thermore, all agents are mobile and the allocation is achieved through a proposed
dynamic iterative auction algorithm. Every agent in each step finds its best tar-
get based on the auction algorithm and the exchange of information with con-
nected agents and moves towards it without any insight in the decision-making
processes of other agents in the system. In the case of connected communication
graph among all agents, the algorithm results in an optimal allocation solution.
We explore the deterioration of the allocation solution in respect to the decrease
of the quantity of the information exchanged among agents and agents' vary-
ing communication range when the latter is not sufficient to maintain connected
communication graph.
1
Introduction
In dynamic multi-robot target assignment, multirobot planning and execution requires
cooperative and coordinated control of each robot's actions. Resources must be used
as efficiently as possible to minimize the cost and time of execution and to maximize
the benefit and efficiency of a multi-robot team. Completing the mission in an arbitrary
feasible way does not necessarily make a multi-robot mission performance satisfactory.
For these reasons, algorithms that can adequately correspond to the changing communi-
cation network topologies are an important topic of the collaborative robotics research.
Typically these algorithms rely on modeling the systems as graphs, where every robot
is a node and edges correspond to communication links between pairs of robots defined
according to a pre-specified communication model [13].
A multi-agent system in which agents have limited communication capabilities may
achieve 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; suf-
ficient condition for optimal solution is that the communication graph among agents
is connected [20,19]. Recall that a graph is said to be connected, if for every pair of
nodes there exists a path between them; otherwise it is disconnected and formed of
more than one connected component. The ability to form a single connected commu-
nication graph as well as the frequency of its disconnections depends on the choice
