17 references, last updated Tue Mar 28 10:31:37 2000
Agent-based computing represents an exciting new synthesis both for Artificial Intelligence (AI) and, more generally, Computer Science. It has the potential to significantly improve the theory and the practice of modeling, designing, and implementing computer systems. Yet, to date, there has been little systematic analysis of what makes the agent-based approach such an appealing and powerful computational model. Moreover, even less effort has been devoted to discussing the inherent disadvantages that stem from adopting an agent-oriented view. Here both sets of issues are explored. The standpoint of this analysis is the role of agent-based software in solving complex, real-world problems. In particular, it will be argued that the development of robust and scalable software systems requires autonomous agents that can complete their objectives while situated in a dynamic and uncertain environment, that can engage in rich, high-level social interactions, and that can operate within flexible organisational structures.
Social insects--ants, bees, termites and wasps--exhibit a collective problem-solving ability (Deneubourg and Goss, 1989; Bonabeau et al., 1997). In particular, several ant species are capable of selecting the shortest pathway, among a set of alternative pathways, from their nest to a food source (Beckers et al., 1990). Ants deploy a chemical trail (or pheromone trail) as they walk; this trail attracts other ants to take the path that has the most pheromone. This reinforcement process results in the selection of the shortest path: the first ants coming back to the nest are those that took the shortest path twice (to go from the nest to the source and to return to the nest), so that more pheromone is present on the shortest path than on longer paths immediatly after these ants have returned, stimulating nestmates to choose the shortest path. Taking advantage of this ant-based optimizing principle combined with pheromone evaporation to avoid early convergence to bad solutions, Colorni et al. (1991, 1992, 1993), Dorigo et al. (1996), Dorigo and Gambardella (1997a, 1997b; Gambardella and Dorigo, 1995) and Gambardella et al.(1997) have proposed a remarkable optimization method, Ant Colony Optimization (ACO), which they applied to classical NP-hard combinatorial optimization problems, such as the traveling salesman problem (Lawler et al., 1985), the quadratic assignment problem (Gambardella et al., 1998) or the job-shop scheduling problem (Colorni et al., 1993), with reasonable success. More applications are described by Bonabeau et al. (1998). The parameters of the ACO algorithms developed in these papers were hand-tuned. In the present letter we demonstrate the good performance of ACO algorithms when parameters are selected using a systematic procedure. More precisely we use a genetic algorithm (Goldberg, 1989) to evolve ACO algorithms. A simple implementation of this approach, tested on the traveling salesman problem (TSP), resulted in: (1) increased convergence speed (compared to the performance of the best hand-tuned ACO algorithm) toward the optimal solution for a 30-city problem (Whitley et al., 1989), and (2) several very good floating point solutions for a 51-city problem (Eilon et al., 1969). Our results suggest that it might be possible to systematically find parameters that significantly increase the performance of ACO algorithms, and confirm that ACO is more than an exotic metaheuristic as it compares well with existing algorithms on popular benchmark problems.
In several species of ants, workers cooperate to retrieve large prey. Usually, one ant finds a prey item, tries to move it, and, when unsucessful for some time, recuits nestmates through direct contact or chemical marking. When a group of ants tries to move large prey, the ants change position and alignment until the prey can be moved toward the nest. A robotic implementation of this phenomenon is described. Although the robotic system may not appear to be very efficient, it is an interesting example of decentralized problem-solving by a group of robots, and it provides the first formalized model of cooperative transport in ants.
The CMUnited-98 simulator team became the 1998 RoboCup simulator league champion by winning all 8 of its games, outscoring opponents by a total of 66-0. CMUnited-98 builds upon the successful CMUnited-97 implementation, but also improves upon it in many ways. This article describes the complete CMUnited-98 software, emphasizing the recent improvements. Coupled with the publicly-available CMUnited-98 source code, it is designed to help other RoboCup and multi-agent systems researchers build upon our success.
We consider the problem of how to design large decentralized multi-agent systems (MAS's) in an automated fashion, with little or no hand-tuning. Our approach has each agent run a reinforcement learning algorithm. This converts the problem into one of how to automatically set/update the reward functions for each of the agents so that the global goal is achieved. In particular we do not want the agents to ``work at cross-purposes'' as far as the global goal is concerned. We use the term artificial COllective INtelligence (COIN) to refer to systems that embody solutions to this problem. In this paper we present a summary of a mathematical framework for COINs. We then investigate the real-world applicability of the core concepts of that framework via two computer experiments: we show that our COINs perform near optimally in a difficult variant of Arthur's bar problem (and in particular avoid the tragedy of the commons for that problem), and we also illustrate optimal performance for our COINs in the leader-follower problem.
Social insects provide us with a powerful metaphor to create decentralized systems of simple interacting, and often mobile, agents. The emergent collective intelligence of social insects--swarm intelligence--resides not in complex individual abilities but rather in networks of interactions that exist among individuals and between individuals and their environment. In particular, a recently proposed model of division of labor in a colony of primitively eusocial wasps, based on a simple reinforcement of response thresholds, can be transformed into a decentralized adaptive algorithm of task allocation. An application of such an algorithm is proposed in the context of a mail company, but virtually any type of flexible task allocation can be described within the same framework.
Agent architectures need to organize themselves and adapt dynamically to changing circumstances without top-down control from a system operator. Many researchers provide this capability with complex agents that emulate human intelligence and reason explicitly about their coordination, reintroducing many of the problems of complex system design and implementation that motivated increasing software localization in the first place. Naturally occurring systems of simple agents (such as populations of insects or other animals) suggest that this retreat is not necessary. This paper summarizes several studies of such systems, and derives from them a set of general principles that artificial agent-based systems can use to support overall system behavior significantly more complex than the behavior of the individuals agents.
Gaining wide acceptance for the use of agents in industry requires both relating it to the nearest antecedent technology (object-oriented software development) and using artifacts to support the development environment throughout the full system lifecycle. We address both of these requirements using AUML, the Agent UML (Unified Modeling Language)-a set of UML idioms and extensions. This paper illustrates the approach by presenting a three-layer AUML representation for agent interaction protocols: templates and packages to represent the protocol as a whole; sequence and collaboration diagrams to capture inter-agent dynamics; and activity diagrams and state charts to capture both intra-agent and inter-agent dynamics.
We describe a framework and equations used to model and predict the behavior of multi-agent systems (MASs) with learning agents. A difference equation is used for calculating the progression of an agent's error in its decision function, thereby telling us how the agent is expected to fare in the MAS. The equation relies on parameters which capture the agent's learning abilities, such as its change rate, learning rate and retention rate, as well as relevant aspects of the MAS such as the impact that agents have on each other. We validate the framework with experimental results using reinforcement learning agents in a market system, as well as with other experimental results gathered from the AI literature. Finally, we use PAC-theory to show how to calculate bounds on the values of the learning parameters