Formal Framework for Analysis of Adaptation in Multi-Agent Systems (ADAPT2)

University Of Southern California, Los Angeles CA

Investigators

Abstract

This research will develop a general framework for mathematical analysis of collective behavior of adaptive multi-agent systems. Adaptation is an essential requirement for autonomous multi-agent systems functioning in uncertain dynamic environments, for example, distributed robot teams, modules in an embedded system, nodes in a sensor network, or software agents. Adaptation allows agents to change their behavior in response to changes in the environment or actions of other agents. Mathematical analysis of adaptive systems will enable researchers to design more robust systems, and to predict, control and understand their behavior. The research will study agents that make decisions autonomously based on local information, which comes either from interactions with other agents or from the local environment. In particular, this project will examine different classes of adaptive behavior, such as adaptation through reinforcement and adaptation through communication via spatially extended fields. Reinforcement learning is a powerful framework where an agent learns optimal actions through a trial and error exploration of the environment and by receiving rewards for good actions. Collective adaptation can also take place in systems in which agents are coupled through external fields, for example, through markers they deposit in the environment. Although adaptation and learning have long been the focus of the artificial intelligence community, there is relatively little work examining how a group of adaptive agents will act. The difficulty arises from the fact that agents adapt in the presence of other adaptive agents. Often it is not a priori clear how the system will act or even if adaptation will achieve the desired goals. In addition, the designer has very little guidance about what individual agent characteristics are required to guarantee the desired collective behavior. The lack of a formal understanding of these problems has prevented researchers from taking full advantage of this powerful design paradigm. The mathematical analysis to be performed in this research will help answer these questions. There is a critical need for better foundations and tools for analyzing multi-agent behavior and verifying control mechanisms for multi-agent systems. The lack of such tools stands in the way of wider deployment of such systems, especially robots and embedded systems. Experiments and simulations that are necessary to validate control algorithms are time consuming and costly. Quantitative understanding provided by the mathematical models to be developed in this project will lead to more robust and efficient control algorithms and greater deployment of such systems in the field.