Adaptive Constraint-Based Agents in Artificial Environments

[INTRODUCTION]   [AI for Games]   [Agents]   [Planning]   [Search Paradigms]   [Search Frameworks]   [Conclusion]

[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]


(Related publication: [PUBLink])

This section recapitulates on the main design decisions for EXCALIBUR's agents and draws conclusions for further development needs.

The agents must be able to exhibit sophisticated behavior and find solutions even for unforeseen situations. A planning system is therefore needed to guide an agent's behavior.

The system will be fully based on the constraint programming paradigm. This allows the agent's behavior problem to be represented by a declarative high-level specification that can be easily maintained. The application of high-level constraints allows domain-specific knowledge to be exploited for the search process.

Many planning systems already incorporate some kind of constraint handling. They can be grouped into the following categories:

None of these approaches makes it possible to represent the planning completely within constraint programming. The problem here is the restrictiveness of conventional formulations for constraint satisfaction problems because all the elements and their relations, i.e., the constraint graph, have to be specified in advance. But plans are highly variable and it is not possible to predict which actions will be used in which combination. The partially observable computer-game environment of an agent poses a further problem here because there are an unknown number of objects. An extension of CSP formulations must therefore be developed that can handle variable constraint graphs. This is done in Chapter [Structural Constraint Satisfaction].

The next problem faced, if constraint programming is to be applied to computer games, is that only a very small portion of CPU power is left for the necessary computations - and there is more than one agent to be guided. Computation here is not a matter of hours, days or seconds but rather clock-ticks. This is one reason for applying local-search techniques in an agent's planning system. The iterative optimization of local search enables the agent's anytime reaction and fast adaptation to changes in the environment. The more computation time there is available, the more elaborate the agent's plan will get.

The current approaches that combine local search with constraint satisfaction use only very basic constraint types, corresponding rather to SAT- or OR-based local-search approaches. The drawback of these approaches is that they fail to take a global view of the problem and are unable to provide appropriate search guidance. The use of higher-level constraints for local search is needed, which is also more in line with the fundamental principles of constraint programming. Chapter [Using Global Constraints for Local Search] addresses this problem.

Besides the extensions of the constraint programming framework mentioned above, the use of constraint programming for planning requires that appropriate high-level constraints be available to model planning problems, which must include the handling of temporal and other resources. Chapter [Model] describes the basic constraint types for specifying planning problems and their use. In addition, issues of probabilities and incomplete knowledge are treated on the modeling level.

[INTRODUCTION]   [AI for Games]   [Agents]   [Planning]   [Search Paradigms]   [Search Frameworks]   [Conclusion]

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek