AIC Seminar Series

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 2006.

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
SRI International is an independent, nonprofit corporation. Privacy policy