AIC Seminar Series
Communication Management in Distributed Sensor Interpretation
|Jiaying Shen||University of Massachusetts, Amherst|
Notice: hosted by Roger Mailler
Date: 2006-04-20 at 16:00
Location: EJ228 (Directions)
Distributed Sensor Interpretation (DSI) problems have been the
subject of considerable research within the cooperative MAS community
because advances in sensor technology are leading to the deployment of large
networks of sophisticated sensors. In a DSI system, data is collected from
different sensors and must be integrated to produce the best interpretation.
Distributed approaches to DSI emphasize not only distributed collecting of
data, but also distributed processing of data. However, in virtually all
real-world DSI systems the agents must exchange data, local results, and/or
other information to develop a solution with acceptable quality. Unless
communication among the agents is appropriately limited, the cost of
communication may negate much of the benefit of distributed processing.
Unfortunately, the state-of-the-art in MAS is such that there are not yet
formal design methods that allow one to evaluate a potential DSI domain and
determine the optimal coordination strategy. I believe that this is a
serious issue that will hinder the deployment of many important applications
of sensor networks.
My work is one of the first attempts to address this issue. I formalized the
communication problem in DSI with a Distributed Bayesian Network and solved
the question of what to communicate with a decentralized Markov Decision
Process (DEC-MDP). With this model, one is able to generate a communication
strategy for a given DSI problem such that only minimum communication cost
is needed to achieve a required confidence level in the interpretation task.
This is different from the previous work in this area, which either focuses
on finding a globally optimal solution while ignoring the cost of
communication, or studies the tradeoff between solution quality and
communication cost only from a statistical view.
Though general communication can be naturally modeled with a DEC-MDP,
techniques need to be developed to address the complexity issue before the
system can be scaled up. I approach this problem from two perspectives.
First, I proposed an algorithm to automatically generate a set of abstract
communication actions such that when the abstract information is transferred
between the agents, the goal of the system is more likely to be reached. By
allowing only abstract communication actions in certain states, both the
expected communication cost required and the time needed to solve the
DEC-MDP are reduced. Second, I established that the interaction present
among the agents is the cause of the high complexity of a DEC-MDP. This
understanding is crucial to identifying new and more tractable models as
well as developing appropriate approximations to otherwise intractable
problems. I proved that deciding a distributed MDP whose interaction history
contains information of a size polynomial in the number of states is
NP-complete, and that deciding a non-polynomially encodable distributed MDP
is harder than NP. This is the first time that a well defined condition has
been identified that can distinguish between multi-agent problems in NP and
those that are strictly harder than NP. It is an important step in mapping
out the complexity hierarchy of multi-agent systems. The significance of
this theoretical result also has a more practical side. Most multi-agent
systems are provably harder than NP and solving them optimally is not
possible. This work provides theoretical guidance in understanding how the
approximations in a model limit the search space and reduce the complexity.
Jiaying Shen is a Ph.D. candidate in the Computer Science
department at the University of Massachusetts, Amherst, where she is advised
by Prof. Victor Lesser. Her research lies in the field of Multi-Agent
Systems and she is particularly interested in deeply understanding
interactions between agents through both formal analysis and experimental
evaluation in real world applications. She received her Bachelor’s degree in
Computer Science and Engineering from from Shanghai Jiao Tong University in
China. In May 2002, she received my MS in Computer Science from University
of Massachusetts, Amherst, and expects to receive her Ph.D. in the summer of
Please arrive at least 10 minutes early in order to sign in and be escorted to the conference room. SRI is located at 333 Ravenswood Avenue in Menlo Park. Visitors may park in the visitors lot in front of Building E, and should follow the instructions by the lobby phone to be escorted to the meeting room. Detailed directions to SRI, as well as maps, are available from the Visiting AIC web page.
©2014 SRI International 333 Ravenswood Avenue, Menlo Park, CA 94025-3493