Developing a Performance Evaluation Tool for Distributed Problem-Solving Strategies

摘要

Distributed problem solving (DPS) is the subfield of Multi-Agent Systems (MAS) concerned with using systems of agents to solve large-scale, distributed problems like data interpretation in sensor networks. A key issue for these systems is coordination of the agents' action, and methods for producing effective coordination strategies remains an active area of DPS research. Because there are not yet approaches that can automatically produce such strategies for most real-world DPS applications, some human engineering is often still necessary. As a result, there is a need for tools to support such human engineering. The type of tool we envision would allow a proposed strategy to be easily modeled, at various levels of abstraction, and allow incomplete specification of both the inter and intra-agent order of actions. After this, the tool would be able to analyze various properties of the strategy, such as the possibility of deadlock. It should also be able to determine the best possible time performance, and as a side effect, determine additional ordering constraints needed to guarantee best performance. This paper reports on research to develop key elements needed for such a tool. In particular, we have investigated the use of pi-calculus as a formal language for defining multi-agent coordination strategies for DPS, as well as techniques for evaluating the time performance of such strategies defined with pi-calculus.