[ 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:

• Planning with Constraint Posting:
  During a conventional planning process, constraints can be posted. Constraint satisfaction is used here as an add-on to check the satisfaction of restrictions such as numerical relations. For example, MACBeth [PUBLink] and the planning procedure of Jacopin and Penon [PUBLink] apply this scheme. Another approach is implemented in the Descartes system [PUBLink], which uses constraint postings not only for numerical values, but also for postponing some of the decisions of action choice.
• Maximal Graphs:
  A restricted planning problem is encoded as (so-called conditional) CSP. The CSP is constructed such that it includes all possible plans up to a certain number of actions, which can be activated or deactivated. parcPLAN [PUBLink], CPlan [PUBLink], the approach of Rintanen and Jungholt [PUBLink] and GP-CSP [PUBLink] follow this line. The advantage of this procedure is that decisions can easily be propagated throughout the CSP. However, the optimal size (e.g., the number of actions) is not known in advance, so a stepwise expansion of the CSP structures must be performed if no solution can be found. However, maximal structures scale very badly and are only feasible for small and only slightly variable structures, which is not the case with most planning problems.

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.

For questions, comments or suggestions, please contact us.

Last update:
May 19, 2001 by Alexander Nareyek