Using Complex Network Effects for Communication
Decisions in Large Multi-robot Teams
Yang Xu, Xuemei Hu, Yan Li, Dong Li, and Mengjun Yang
School of Computer Science and Engineering
University of Electronic Science and Technology of China
Chengdu, Sichuan, P.R.China
xuyang@uestc.edu.cn
ABSTRACT
Sharing information is critical to multi-robot team coordi-
nation when rob ots are widely deployed in a dynamic and
partially observable environment. To be efficient, robots
should balance well between broadcasting information and
reserving limited bandwidth so that only the right informa-
tion should be broadcast to the interested receivers. Robots’
communication decision is normally modeled as a multi-
agent decision theoretical problem. However, when the team
expands to very large, the solution is classified as NEXP-
COMPLETE. In this paper, in addition to building heuristic
approaches to solve the decision theoretical problem based
on the information context to be broadcast, we put forward
a novel context-free decision model that allows fast commu-
nication decision by considering complex network attributes
in large teams. Similar to human society, information should
b e broadcast if the action can make a go od information cov-
erage in the team. We analyze how complex network at-
tributes can improve communication in a broadcast network.
By putting forward a heuristic model to estimate those com-
plex network attributes from robots’ local view, we can build
decision models either from robots’ experiences or from their
lo cal incoming communications. Finally, we incorporate our
algorithm in well-known information sharing algorithms and
the results manifest the feasibility of our design.
Categories and Subject Descriptors
I.2.11 [Artificial Intelligence]: Distributed Artificial In-
telligence -Intelligent Agents, Multiagent Systems.
Keywords
Complex network; Information Sharing; Coordination;
1. INTRODUCTION
Coordinating large groups of robots or unmanned vehi-
cles in a dynamic and partially observable environment is
comp elling in various domains such as urban search and res-
cue [1], planet exploration [2] and military operations [3]. In
such applications, information sharing is necessary because
rob ots have to share their observations and intentions so
Appears in: Alessio Lomuscio, Paul Scerri, Ana Bazzan,
and Michael Huhns (eds.), Proceedings of the 13th Inter-
national Conference on Autonomous Agents and Multiagent
Systems (AAMAS 2014), May 5-9, 2014, Paris, France.
Copyright
c
2014, International Foundation for Autonomous Agents and
Multiagent Systems (www.ifaamas.org). All rights reserved.
that their mutual beliefs as well as joint activities towards
the best team performance can be reached [4]. In a mobile
rob ot team, robots use wireless connections to broadcast
information to their neighbors. But when the team scales
up, communication bandwidth becomes a serve bottleneck.
Rob ots then are required to balance well between broadcast-
ing valuable information and reserving limited bandwidth.
Their decision is hard because robots in this scenario are
normally highly distributed and have only a partial view of
the team. Without a complete knowledge on what the others
know, robots may not be able to make rational decisions [5].
The information sharing problem on how to decide to
broadcast valuable information in large robot teams has
b een intensively studied in recent years. In the computer
network research community, researchers have focused on
how to avoid redundant information coverage overlay no
matter what the information is. Typically, Scalable Broad-
cast Algorithm (SBA) [6] shares information and avoids robots
rebroadcasting if most of their neighbors already have it.
Low-Energy Adaptive Clustering Hierarchy (LEACH) [7]
uses static hierarchical protocol and its improved proto-
col [13] combines clustering with predefined forming chains
to proactively share information. Sensor Protocols for In-
formation via Negotiation (SPIN) [8] is a reactive protocol
which avoids redundant data transmission by meta-data ne-
gotiation between neighbors. Robots only need to forward
data to the neighbors who need it. But if no request is
received, robots will prefer to not sending the information.
Information sharing research in AI community starts from
the view of how the information to be shared can help the
rob ot team improve its performance [5]. Therefore, infor-
mation sharing is modeled as a decision theoretical problem
that, for each specific piece of information, robots evalu-
ate the utilities if it were broadcast. When the utility of
broadcasting it is beyond the cost, the robot will broad-
cast. However, with the partial observable capability of
each robot, the information sharing utility calculation is
a typical DEC-POMDP problem with the expand of team
scale [9]. Extra efforts have been done on building heuristic
algorithms to solve this intrinsic NEXP-COMPLETE prob-
lem in each specific coordination domain, such as myopic
decision model [10], and State-Connection-Reward matrix-
based model [11]. Although their p erformances are proven
to be goo d, they are usually hard to be optimized.
In this paper, addition to the information sharing algo-
rithm design in previous studies, we explore how the com-
plex network effects can be used in the robot communication
decision, and put forward an interesting approach to help lo-