Design and Mathematical Analysis of Agent-based Systems
K. Lerman
Information Sciences Institute
Univ. of Southern California
Marina del Rey, CA 90292-6695
April 7, 2000
Abstract
Agent-based systems that are composed of simple locally interacting agents but which demonstrate
complex group behavior offer
several advantages over traditional multi-agent systems. A well-designed
complex agent-based systems is an e.cient, robust, adaptive and stable
system. It has very low communication and computational requirements,
meaning that there are virtually no constraints on the system size. The
simplicity ofagent interactions also makes it amenable to quantitative
mathematical analysis. In addition to offering predictive power, mathematical
analysis enables the system designer to optimize system performance.
To date, there have been relatively few implementations of complex
agent-based systems, mainly because of the di.culty of determining what
simple agent strategies will lead to desirable collective behavior in a large
system. We claim that there exists a set of primitive agent strategies, similar
to the basis behaviors in behavior-based robotics, from which complex group
behavior can be designed. Moreover, these simple primitive
strategies naturally lend themselves to mathematical description, making a
quantitative study of agent-based systems possible. We present a
case study of coalition formation to show that two simple behaviors, dispersion
and aggregation, can lead to coalition formation in a multi-agent
system under some conditions. We use this system to illustrate the process
by which a mathematical description of the agent-based system is
created and analyzed, and discuss the insights the analysis provides for
designing coalition forming agents.
(Full Text)