Review
prs-flakey

A Procedural Knowledge Approach to Task-Level Control

Alex J. Champandard on October 25, 2007

When it comes to building powerful decision-making and control systems, robotics research is the best place to turn to for decades of experience. Many of the popular ideas in game AI today can be traced back to robotics controllers.

In particular, this week’s Thursday Theory post on AiGameDev.com looks into a control system known as PRS (specifically, the ‘Lite’ version) developed at the SRI’s AI Center.

Motivation

Ultimately, PRS-Lite is designed to create control systems that are both reactive and purposeful, which is quite a common problem in game AI too. The paper addresses the following problems:

  1. In robotics, many control systems are built for specific problems and hardware. Instead, PRS is a general system, so it’s applicable to games.

  2. Traditional planners are not very efficient and do not fulfill the real-time constraints of games and robots. Moreover, the paper shows how planning isn’t required for purposeful behaviors (except path-finding).

The motivation for such a system is games is that finite state machines are hard to build in a goal-driven way, and it’s hard to write scripts that deal with all possible events.

PRS Interpreter

Figure 1: The structure of the interpreter in the PRS system [2].

Contributions

PRS-Lite contains some very interesting and useful ideas about developing control systems. In particular:

  1. It describes ways to assemble behaviors to achieve specific results while being responsive to unexpected events.

  2. It provides intuitive mechanisms for goal-decomposition, notably to dispatch and monitor lower-level tasks and behaviors.

  3. It allows smooth blends between overlapping low-level processes, since many behaviors are implemented as fuzzy rules.

Specifically, this is achieved by:

  • Building a hierarchy of action primitives using sequences. This allows the designer to build up complexity from the bottom-up.

  • Providing a rich language of behavioral operations: test, execute, assign, wait-for, intend/unintend, if, and, goto, split.

  • Compiling these “schema” specifications into parameterized state machines that can be executed natively.

  • Establishing a a set of best-practices for dealing with concurrent goals, tasks, etc.

Behavior trees, as used today in game AI, only exploit a few of these possibilities, so there are many lessons to be learned from this paper.

Abstract and References

Here’s the abstract of the paper:

Effective task-level control is critical for robots that are to engage in purposeful activity in realworld environments. This paper describes PRSLite, a task-level controller grounded in a procedural knowledge approach to action description. The controller embodies much of the philosophy that underlies the Procedural Reasoning System (PRS) but in a minimalist fashion.

Several features of PRS-Lite distinguish it from its predecessor, including a richer goal semantics and a generalized control regime. Both of these features are critical for supporting the management of continuous processes employed in current-generation robots. PRS-Lite has been used extensively as a task-level controller for a robot whose underlying behaviors are implemented as fuzzy rules. Tasks to which it has been applied include vision-based tracking, autonomous exploration, and complex delivery scenarios.

You can download the paper from the site (PS, 161 Kb).

A Procedural Knowledge Approach to Task-Level Control
K. L. Myers
International Conference on AI Planning Systems, 1996.

For more details about the original PRS architecture, download the manual (PDF, 463 Kb).

User Guide for the Procedural Reasoning System
K. L. Myers
Technical Report, Artificial Intelligence Center SRI International, 1997.

Evaluation & Discussion

Overall, while this paper is already a decade old, many ideas are still useful for modern game AI.

Applicability to games: 7/10
Certain aspects of the architecture are not entirely necessary for games, in particular the support for fuzzy logic for the task activation expressions and the action control. Admittedly, the fuzzy logic does result in smoother behaviors, but in games there’s much less uncertainty to deal with than in robots, so it may not be worth the extra hassle during development.
Usefulness for character AI: 8/10
Despite being over a decade old, this paper’s most useful contribution to character AI is support for concurrent behaviors. It provides techniques for dealing with a “forest of directed graphs” each synchronizing and working with each other. Admittedly, integrating these ideas into a game would require building up some experience, but the ideas in this paper are a great place to start.
Simplicity to implement: 9/10
The actual implementation of PRS-Lite is merely 500 lines of Lisp code. Granted, that may correspond to 10k lines of C++, but the concepts are simple and simple to implement. Behavior trees are similarly attractive for this reason; it doesn’t take very long to get up and running. The FSM compiler described in the paper would probably the most time to write.

What do you think of this approach to creating a decision-making and control system?

Discussion 1 Comments

netking on August 5th, 2008

Hehe! I've been designing an AI system that's similar to this for about a year now. It uses action descriptions and such to break down tasks and information. I'm just getting ready to turn my notes into code. Working of an AI system for a year, with no previous experience with AI is rough, but now that I've seen this, I've got a bit more confidence in my design decision. Good to see I'm not the only one trying to make self-supporting AI :-D Oh btw, this is my first comment here. Tons of good info. Thanks.

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!