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

The EXCALIBUR agent architecture presented here focuses on the goal-directed behavior computation of the agent. By contrast, most of the existing architectures for autonomous agents focus on communication protocols and interaction, but do not specify how to compute the behavior of the individual agents (e.g., Reticular Systems' AgentBuilder [PUBLink] and SRI International's Open Agent [PUBLink]).

The agent's reasoning about its behavior is based on the paradigm of local search. The iterative repair procedure of local search techniques provides the agent with an efficient anytime reasoning that enables an agent to produce fast reactions as well as sophisticated action plans. Generic agent systems like the Australian Artificial Intelligence Institute's dMARS [PUBLink] [PUBLink], Bits & Pixels' IaFactory, MASA's DirectIA SDK or the Soar/Games AI engine [PUBLink] provide only very simple predefined reasoning schemes. Today's planning systems, on the other hand, focus on deliberative refinement reasoning and are hardly ever able to perform reactive actions. Unlike hybrid systems that involve a reactive and a deliberative module, our EXCALIBUR agents feature a continuous transition between reaction and deliberation. The priority of a plan's feature to be repaired is given by a cost/goal function. Similar approaches are realized in the GERRY system [PUBLink] and ASPEN [PUBLink] [PUBLink].

Local search's independence of the search history and the quick single repair steps also facilitate an uncomplicated handling of the environment's dynamics with interleaved sensing, planning and execution. This capability is very important for an agent, given the quickly changing environment in computer games.

The whole architecture was embedded in a constraint programming framework, which makes the approach highly declarative and modular and the developed methods applicable to other search problems. However, several extensions of the CP framework were necessary to achieve sufficient efficiency and expressiveness. The first extension realizes an adequate integration of local search. The concept is based on the use of global constraints and preserves the constraint programming framework's properties of declarativeness and variable applicability. Domain-dependent knowledge to guide and accelerate search can be integrated using the global constraints in a plug-and-play manner.

The second extension of constraint programming was necessary to realize a search free from predefined bounds, e.g., plans of a certain length. This feature is important to favor optimization criteria like resource-related properties, and even more important for handling open worlds, in which the agent must reason about an arbitrary number of objects in the world. This was enabled by the concept of structural constraint satisfaction, which enhances conventional constraint satisfaction by providing the opportunity to formulate problems in which the constraint graph is not given in advance. Unlike other planning systems that use productions/rules to change the graph as part of the search (e.g., [PUBLink]), modeling planning as an SCSP allows us to specify the problem in a declarative manner and enables the corresponding productions to be deduced automatically. The automatic method guarantees that local-search methods can potentially find all valid plans, which is not normally the case with hand-tailored solutions.

Existing planning systems do not use resource-based criteria as primary optimization goals; instead, most still focus on minimization of the plan length. This approach is quite curious because a plan-length property is irrelevant for real-world problems. Nevertheless, the current planning approaches within search frameworks like OR and SAT also follow this plan-length focus by restricting themselves to the search for plans of a predefined length, expanding this limit if they cannot find a valid plan. This is also true for constraint-based planning approaches like CPlan [PUBLink]. Some systems apply separate planning and scheduling phases (e.g., the RETSINA agent [PUBLink]), but this prevents them from considering interactions between the decisions regarding planning and resource assignment.

The resource focus is also reflected in the planning model and allows us to use and optimize temporal, spatial and all other kinds of resources. Furthermore, the model is expressive enough to handle incomplete knowledge and information gathering.

To conclude, the presented agent architecture features:

• Real-Time Reasoning: The local-search approach enables the system to provide very primitive plans (reactions) for short-term computation horizons, while longer computation times are used to improve and optimize the agent's behavior.
• Dynamics: The iterative repair/improvement steps make it possible to easily interleave sensing, planning and execution.
• Resource Focus: The search can be conducted in a way that focuses on the satisfaction and optimization of resource-related properties.
• Incomplete Knowledge: The model is not restricted to the closed-world assumption and enables an agent's incomplete knowledge to be dealt with.
• Domain Knowledge: Even though the model supports full domain-independent planning, domain-specific heuristic knowledge can be easily integrated by way of the global constraints.
• Software Engineering: The system is based on the general search framework of constraint programming and can be easily changed, extended, maintained and reused.

The EXCALIBUR architecture represents a significant step toward realization of intelligent agents for computer games. Not only genres like computer role-playing games and strategy games can benefit from this. For games like first-person shooters, too, increasing efforts are being made to include sophisticated behavior for their bots. Of course, the technology is not restricted to computer games. Other application areas include internet agents, factory robots, autonomous spacecraft and many more.

The basic architecture is completed, and in the near future, we will focus our attention on enhancing the EXCALIBUR agents with methods of cooperation/coordination/communication and learning.

For questions, comments or suggestions, please contact us.

Last update:
May 20, 2001 by Alexander Nareyek