We are interested in the design and analysis of agent-based systems, i.e., systems composed of many interacting autonomous software or embodied artificial intelligent agents. While the vast majority of research in this field has focused on creating ever more complex deliberative agents, a multi-agent system composed of such agents has shortcomings in at least one of the following areas: robustness, stability, adaptability, scalability. Moreover, these systems are usually not amenable to quantitative analysis. We are interested in investigating a fundamentally different approach to the design of agent-based systems in which the agents themselves are simple, but collectively, they are able to accomplish complex tasks. A well-designed complex agent-based system is an efficient, distributed, robust, adaptive and stable multi-agent system. It lacks central control and can recover quickly from agent failure and changes in the environment. Because of its low communications and computational costs, there are virtually no constraints on the system size. Moreover, such systems are often amenable to mathematical analysis, thus making detailed predictions of their behavior possible. Despite their numerous advantages, there have been relatively few implementations of complex agent-based systems to date, with the exception of research by the robotics community. The key challenge in designing a complex agent-based system is the difficulty of reverse-engineering the problem, i.e., determining what individual agent strategies lead to the desired collective behavior. We will look to physical and biological complex systems for inspiration for the design of a complex artificial systems.

Our research goals are two-fold:

Mathematical analysis is important for several reasons: a designer of multi-agent systems can use it to show that the proposed agent strategy leads to the desired group behavior, find the parameters that optimize system performance (collective behavior), and predict the global dynamics of the system. We plan to apply this type of analysis to several software agent and robotic systems.

* This work is supported in part by in part by DARPA under contract number F30602-00-2-0573 and in part by the NSF under Grant No. 0074790


Kristina Lerman (USC/ISI)

Maja Mataric (USC)

Aram Galstyan (USC/ISI

Chris Jones (USC)


Mathematical Analysis & Design

Kristina Lerman and Aram Galstyan (2004), “Automatically Modeling Group Behavior of Simple Agents,” Agent Modeling Workshop, AAMAS-04, New York, NY.

Kristina Lerman and Aram Galstyan (2003) " Agent Memory and Adaptation in Multi-Agent Systems ", International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-03), Melbourne, Australia.

Kristina Lerman and Aram Galstyan (2002) "Two Paradigms for the Design of Artificial Collectives," workshop on Collectives and Design of Complex Systems, NASA/Ames, August 2002.

Kristina Lerman and Aram Galstyan (2001) " A General Methodology for Mathematical Analysis of Multi-Agent Systems ", USC Information Sciences Technical Report ISI-TR-529. ( abstract )

Aram Galstyan and Kristina Lerman (2001) " A Stochastic Model of Platoon Formation in Traffic Flow ", in proceedings of the TASK workshop, Santa Fe, NM, April 2001.

Kristina Lerman (2001) " Design and Mathematical Analysis of Agent-based Systems ", Lecture Notes in Artificial Intelligence (LNAI 1871), pp.222ff, Springer Verlag, Berlin Heidelberg. (abstract )

Kristina Lerman and Onn Shehory (2000) " Coalition Formation for Large-Scale Electronic Markets ", ICMAS-2000, Boston, MA. ( abstract )

Distributed Robotics

Aram Galstyan and Kristina Lerman (2004), “Analysis of a Stochastic Model of Adaptive Task Allocation in Robots,” AAMAS-04, New York, NY.

Kristina Lerman (2003), A model of adaptation in collaborative multi-agent systems, workshop on the Mathematics and Algorithms of Social Insects (MASI-2003), Atlanta, GA.

Kristina Lerman and Aram Galstyan (2003) " Macroscopic Analysis of Adaptive Task Allocation in Robots ", Proc. of Int. Conferrence on Intelligent Robots and Systems (IROS-03), Las Vegas, NV.

Kristina Lerman and Aram Galstyan (2002) " Mathematical Model of Foraging in a Group of Robots: Effect of Interference ", Autonomous Robots 13(2):127--141.

Kristina Lerman, Aram Galstyan, Alcherio Martinoli and Auke Ijspeert (2001) "A Macroscopic Analytical Model of Collaboration in Distributed Robotic
Systems ," Artificial Life 7:4, 375-393. MIT Press

Brian P. Gerkey and Maja J. Mataric (2002) " Sold!: Auction methods for multi-robot coordination ", to appear in IEEE Transactions on Robotics and Automation, to appear in 2002.

Dani Goldberg and Maja J Mataric, (2001) " Design and Evaluation of Robust Behavior-Based Controllers for Distributed Multi-Robot Collection Tasks ", in Robot Teams: From Diversity to Polymorphism, Tucker Balch and Lynne E. Parker, eds.

Dani Goldberg and Maja J Mataric, (2000) " Maximizing Reward in a Non-Stationary Mobile Robot Environment ", Autonomous Agents and Multi-Agent Systems, special issue on the best of Agents 2000 (The Fourth International Conference on Autonomous Agents, Barcelona, Spain, June, 2000).

Minority Games and Boolean Networks

Alejandro Bugacov, Aram Galstyan and Kristina Lerman (2003) " Threshold Behavior in a Boolean Network Model for SAT ", submitted to IC-AI'03, Las Vegas, NV.

Aram Galstyan and Shashikiran Kolar and Kristina Lerman (2003) " Resource Allocation Games with Changing Resource Capacities ", to be presented at the International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-03), Melbourne, Australia.

Aram Galstyan and Kristina Lerman (2002) " Adaptive Boolean Networks and Minority Games with Time-Dependent Capacities ," Physical Review E66, 015103.

Aram Galstyan and Kristina Lerman (2002) " Minority Games and Distributed Coordination in Non-Stationary Environments ," in Proceedings of IJCNN2002, Hawaii, May 2002.




Last updated: June 18, 2001, lerman@isi.edu