Raney, B. (2005) Learning Framework for Large-Scale Multi-Agent Simulations. Dissertation, ETH Zurich, Switzerland.

Abstract

Many types of engineering problems involve planning an infrastructure or environment used by people. This can include designing something new, or modifying an existing infrastructure. In these planning problems, the challenge is generally to meet the needs and desires of the individuals using the system, while balancing the needs of the system as a whole. This is a difficult task because each person that uses the system has his or her own individual requirements and preferences, and they may conflict with those of other people. In addition, people can learn and adapt, meaning they can alter their behavior in response to changes in the system. Planners must take this into account, by including the behavior of the people into the planning process.
Simulation is a technology in which a model of reality is implemented on a computer and run forward in time. One type of simulation implements a model represented by a sets of discrete behavioral rules, which is suitable for problems involving phenomena occurring from the action of many individuals. In addition, “multi-agent systems” is a powerful technique for problems involving the interaction of many individuals. This technique uses entities called agents that represent individual components of the system. Each agent has its own goals, abilities, and resources, and acts on its environment based on its personal perceptions of that environment. The combination of rule-based simulation with multi-agent systems yields multi-agent simulation (MAS), which is a computer model that represents a collection of agents and their environment, as well as the behavior, actions and interactions of the agents within that environment.
This dissertation presents the design and implementation of a MAS framework for running simulations related to planning problems involving large numbers of people. The framework is applied to two planning problems. The primary application is transportation planning. The framework is described in terms of travelers in a regional or metropolitan transportation system that have their own daily plan of activities and travel. In this simulation, the agents represent travelers, and they learn to build good plans in order to achieve their goals and to get the best use out of the transportation system. Such problems can involve millions of travelers, so special attention is paid to making the framework support large-scale problems. A preliminary application of the framework to a second application in the field of architecture is presented. This work involves planning the interior of office buildings. The architectural elements of a building, as well as that building’s users become the agents. The elements learn to arrange themselves in a way that is pleasing to the users, while and the users evaluate the resulting building layout.
Agents’ actions can cause changes in their environment, which can then cause them to alter their actions. This causes a feedback loop between the simulation of agents’ decisionmaking and the simulation of the environment, which must be resolved. The framework does so using the technique of relaxation, which repeatedly alternates execution between two layers of the system. In the strategic layer, agents make decisions about their actions based on their knowledge about the environment. The physical layer represents the environment, and executes the agents’ strategic decisions, simulating their effects on the environment and each other.
Three implementations of the framework and included feedback system are presented, each of which deals with certain challenges encountered in the design and implementation of the framework. The first implementation presented is a simple and straightforward one based on an existing transportation planning package called TRANSIMS. The second of these adds a unique component called the agent database, which stores past and present strategies for all agents in the system, along with measures of the performance of each strategy. During each iteration of the relaxation sequence, the agent database allows agents to add strategies to their repertoire via the strategy generation modules, or reuse previous strategies. The first agent database is implemented using MySQL, a relational database management system, to keep track of agents’ memories of their strategies. The second version of the agent database is implemented as a simplified object-oriented database, built using C++, which stores the agent data in computer memory and in a flexible data structure. In addition, XML (eXtensible Markup Language) technology is used to record the hierarchical structure of data that represent agents and their plans.
The implementations of the transportation and architecture frameworks are validated with test scenarios, and the framework for transportation planning is validated through application to real-world planning problem. It is used to simulate approximately 1 million travelers using the roadways throughout Switzerland during the morning peak period from 6:00 AM to 9:00 AM. It is shown to produce results at least as realistic as a more traditional and non agent-based “assignment” model, but can provide much more information than the traditional models about the behavior of the individual travelers.

thesis_raney.pdf 2.85 MB