[ 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])

Autonomous agents have become a key research area in recent years. The basic agent concept incorporates proactive autonomous units with goal-directed behavior and communication capabilities. These properties are becoming increasingly important, given the ongoing automation of human work. Users do not have to specify the way something is to be executed but rather the goal that is to be achieved. A reasonable way to pursue these goals must be found by the agents themselves. The agents do not have to act individually but can cooperate and perform coordinated group actions. Applications in electronic commerce, industrial process control and the military sector are only the precursors of numerous forthcoming applications.

The EXCALIBUR project focuses on autonomous agents that can act in a goal-directed manner under real-time constraints and incomplete knowledge, being situated in a dynamic environment where resources may be restricted. The real-time requirement means that an agent must be able to react within a small upper bound of response time, like milli- or microseconds. This is very important in dynamic environments, in which the agent must take external events into account. In addition, the agent's knowledge may be incomplete in many ways. Our main concern will not be with non-determinism, i.e., different possible outcomes of actions; instead we will focus on the system's ability to handle a partially observable environment, i.e., where the closed-world assumption does not hold and a potentially infinite number of objects exist. Furthermore, the agent's actions may be constrained with respect to various resources, like food, energy or money, and an agent may have optimization goals related to these resources. To satisfy these very high requirements, this project enhances and combines paradigms like planning, constraint programming and local search.

The application domain of this project is computer games, which fit the problem context very well since most of them are played in real time and provide a highly interactive environment where environmental properties are constantly changing. Low-level environment-recognition problems - like the processing of visual information and the spectrographic analysis of a noise - can be ignored, given the high-level environment information from the game engine, and the domain is variable enough to model all kinds of problem examples. In addition, these techniques are in great demand by the computer-games industry. This project therefore represents a useful combination of scientific contributions and application demands.

Chapter [Introduction] elaborates the research subject, describes previous approaches, compares them and draws conclusions for the techniques applied. The main contributions of this project (so of now) are presented in Chapters [Using Global Constraints for Local Search], [Structural Constraint Satisfaction]and [The Planning Model].

To realize a declaratively formulated and efficiently executable search for an agent's behavior plan, the framework of constraint programming is applied as the basic paradigm throughout the project. Since dynamics and real-time computation must be supported, a combination of constraint programming with local search is developed in Chapter [Using Global Constraints for Local Search]. An inclusion of domain-dependent knowledge to guide and accelerate search is achieved by so-called global constraints. These techniques form the basis for the real-time computation of an agent's behavior, while preserving the properties of declarativeness and variable applicability.

The problem of reasoning about an arbitrary number of objects in an agent's world and about an arbitrary structure of the agent's plan is tackled in Chapter [Structural Constraint Satisfaction]. The framework of constraint programming is not normally designed for this purpose and is therefore enhanced by adding the ability to handle problems in which the search for a valid structure is part of the search process. The concept is combined with the local-search approach treated in Chapter [Using Global Constraints for Local Search]. The techniques described in Chapter [Structural Constraint Satisfaction] establish the basis for ensuring that the search for an agent's plan can be carried out free from restrictions, like considering only a predefined number of objects in the world, and make it possible to guide the search toward interesting features like the optimization of resource-related properties.

The concepts and techniques treated in Chapters [Using Global Constraints for Local Search] and [Structural Constraint Satisfaction] were not specifically designed for the planning domain only and are applicable to a whole range of other domains like configuration and design. Chapter [The Planning Model] applies them to an agent's behavior planning, introducing the agent's planning model. The model focuses on resources and also allows a limited handling of an agent's partial knowledge.

The interplay of all parts - the realization of an autonomous agent - is demonstrated in Chapter [Application]. Some general solving heuristics are presented and applied to the Orc Quest problem and variations of the Logistics Domain. Real-time computation, a plan property's optimization and the handling of dynamics are demonstrated.

Chapter [Conclusion] provides a preliminary conclusion.

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek