Reviewed by
David L. Sallach
Argonne National Laboratory
USA
Contemporary social agent simulation has been made possible by computer innovations, including object-oriented programming and visualisation techniques. Constraint programming, which has been developed and incorporated into computer languages during the last few decades, makes higher-order software development techniques available to agent research. This development results in potential algorithmic and knowledge representation advantages. The further refinement of distributed constraint satisfaction makes this line of innovation even more relevant to the simulation of multiple agents and their interaction.
The book that is the focus of the present review provides a concise overview of distributed constraint satisfaction algorithms and issues. It will thus help agent modellers to draw upon this emerging technology. Topics in this slim volume are tightly drawn and clearly presented, thus providing, as the subtitle implies, a foundation for understanding distributed constraint satisfaction. The problems to which constraint satisfaction techniques are applied include recognition, scheduling, resource allocation and multi-agent truth maintenance. A number of search algorithms are generalised to versions supporting distributed interaction that allow "agents to act concurrently and asynchronously without any global control" (p. 133), while still guaranteeing completeness.
At this point, the suggestion that constraint-based capabilities may provide advantages to social agent simulation involves a certain stretch. Constraint programming originates as an analytical tool designed, mostly, to solve optimisation problems. Advanced implementations involve sophisticated user interfaces that support human experts in framing the problem and guiding them towards a solution. Contemplating agent-based applications where it is expected that software agents can frame and solve local problems in terms of constraints necessitates an evolution from analytical tool to autonomous agency, and from optimisation to more fluid forms of satisficing. Yokoo's presentation has the strength of covering at least part of this ground.
The discussion begins with standard examples of constraint-based problems such as N queens, scheduling and graph colouring, illustrating how distributed algorithms can provide solutions. It then turns to mapping multi-agent systems issues, such as truth maintenance, into a constraint-based framework. All such early examples depend on common definitions and consistency criteria that make them more appropriate for an analytical tool than for a social modelling framework.
Later, the book begins to introduce capabilities that would be required by social forms of co-operation such as allowing each agent multiple local variables (pp. 101-111), the exchange of agent assumptions (pp. 93-100) and the relaxation of solution definitions so that, instead of finding an optimal solution, the agents settle for outcomes within a solution region (pp. 36-37). The latter might be conceived as satisficing and/or, in terms of complexity theory, exploring the reachability of relevant attractor basins. Either formulation is much closer to the requirements of social processes where goals are multiple, interacting and evolving over time.
In order for the utility of distributed constraint satisfaction for social simulation to be known, there will need to be extensive tool-specific experimentation and practice. Only then can the compatibility of tools and requirements be fully assessed. In this process of experimentation, one of the most pressing issues is support for endogenous, emergent constraints. Constraint-based analytical tools have been completely under the control of human experts, and have not needed to support the endogenous emergence of objectives, constraints and solutions. This issue is not addressed by Yokoo, and how satisfactorily the current generation of constraint satisfaction tools can meet this challenge is not yet known.
The focus of this review has been primarily on constraints as an advanced form of programming and as an effective level of abstraction. The ultimate contribution of constraint models for social simulation is still open. However, what Yokoo does is partially to bridge the gap between a valuable set of technical concepts and tools and a new and challenging problem domain. He introduces capabilities that will be helpful to social modelling and will serve as a foundation for further progress. Most importantly, he provides a clear, accessible introduction to the domain and thus opens the door to further dialogue and experimentation.
Return to Contents
of this issue
© Copyright Journal of Artificial Societies and Social Simulation, 2005