This week’s Thursday Theory article on AiGameDev.com covers a landmark paper in AI planning from the early 1970s. So the “New Approach” mentioned in the title is basically… *gasp* 37 years old! However, don’t be fooled by this seemingly type-written paper. The ideas and techniques described here not only have inspired most modern planners, but they are also simple to understand and implement within modern games.
The recent incursion of planning techniques into the world of game development can be attributed in part to the ideas behind STRIPS. In fact, the AI in the acclaimed first-person shooter F.E.A.R. is partly based on this technology. Other game studios and middleware companies are following suit.
STRIPS stands for the Stanford Research Institute Problem Solver, developed by Richard Fikes and Nils Nilsson from the AI Center at SRI International — as it is known now. This post also draws from Chris Cocosco’s 1998 review of the original paper too, as referenced below.
STRIPS is rooted in robotics. The challenge was to build a system for controlling the robot Flakey (photo) capable of:
Performing tasks like moving objects or navigating around an environment with multiple rooms.
Solving problems in real-time efficiently on the very limited hardware of the time.
Research has progressed a lot in these areas over the years, particularly in the processing of low-level sensors and actuators, but STRIPS still retains many advantages for such high-level robot AI. That’s one of the reasons it is well suited to games.
Generally speaking, there are two major contributions in this paper — both of which have remained at the heart of the AI planning community even today:
A representation language for planning problems (see this article). The basic idea is that a world model is modified by operators, which have a set of preconditions and side effects. The side effects are either lists of facts that are added or deleted from the world model. For example, a shoot operator would require a gun, and have as side effect a damaged target (added) and no longer have a loaded bullet (deleted).
The use of two different search algorithms: the first for doing the planning itself which figures out what should be done next on a high-level, and the second for working out what is currently true in the world and if the goals have been satisfied. For example, one algorithm would be responsible for working out the series of operators for assassinating a target, and another search algorithm would work out if the goal has been achieved by looking at the facts in the world model.
In practice, there are also quite a few ideas in the implementation that are worth taking note of:
The planner uses a strategy known as means-end. This works by looking at what needs to change in the world model, and selecting an appropriate operator to perform this task. For example, if the goal position is different then use a move-to operator. This helps drive the search forward more efficiently.
Also, since A* was invented at the SRI AI center, STRIPS makes use of it by applying a heuristic to help select which node in the search graph to work on next. Intuitively, this means the algorithms expands plans that seem the most promising.
The system uses dependency tracking to figure out pre-conditions for all the operators in a plan. When something unexpected happens, the system knows if replanning is necessary or not, and for which reason.
It’s the combination of these ideas that made the system efficient enough to run in realtime for controlling the robot. When applying STRIPS into your game, keep these tricks in mind too.
Figure 2: An example search tree derived from STRIPS.
Abstract & References
It’s not an abstract in the modern sense, but here’s the official introduction to the paper:
“This note describes a new problem-solving program called STRIPS (STanford Research Institute Problem Solver). The program is now being implemented in LISP on a PDP-10 to be used in conjunction with robot research at SRI. Even though the implementation of STRIPS is not yet complete, it seems to us important to discuss some of its planned features so that they can be compared with other on-going work in this area.
STRIPS belongs to the class of problem solvers that search a space of “world models” to find one in which a given goal is achieved. For any world model, we assume there exists a set of applicable operators each of which transforms the world model to some other world model. The task of the problem solver is to find some composition of operators that transforms a given initial world model into one that satisfies some particular goal condition. This framework for problem solving, discussed at length by Nilsson, has been central to much of the research in Artificial Intelligence. A wide variety of different kinds of problems can be posed in this framework.
Our primary interest here is in the class of problems faced by a robot in rearranging objects and in navigating. The robot problems we have in mind are of the sort that require quite complex and general world models compared to those needed in the solution of puzzles and games. Usually in puzzles and games, a simple matrix or list structure is adequate to represent a state of the problem. The world model for a robot problem solver, however, needs to include a large number of facts and relations dealing with the position of the robot and the positions and attributes of various objects, open spaces, and boundaries.”
You can download the paper from the website:
STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving R. E. Fikes and N. J. Nilsson Artificial Intelligence 2 (3--4), 1971. Download PDF (1.5 Mb)
Also, you may be interested in a more modern interpretation of the ideas in the original paper:
A Review of STRIPS Chris A. Cocosco 1998 Download PDF (161 Kb)
In practice, here’s how it all applies to artificial intelligence in game development.
- Applicability to games: 7/10
- Parts of STRIPS (the planner) are almost a perfect match for many aspects of game logic, especially for software engineering purposes. Such a design helps with modularity of the code. However, as specified in this paper, a full STRIPS solution is not ideal for games. Few games require the complexity of the theorem prover, and games that are complex enough will suffer from performance issues.
- Usefulness for character AI: 8/10
- NPC behaviors can certainly benefit from the additional automation and modularity brought by a planner. Some games may not see an obvious increase in “intelligence” by using this solution, but the AI will be more robust because of it (compared to more procedural approaches like scripts).
- Simplicity to implement: 7/10
- The full implementation of STRIPS including the theorem prover and the planner requires some time and experience with first-order logic. However, for most games a simple A* based search would be sufficient (which is very simple to implement). The only challenge remaining is to make it efficient enough for real-time performance!
Many improvements have been made to the STRIPS algorithm since it was invented, ranging from simple tricks that can speed up the search to major improvements using the underlying representation.
Figure 3: A flowchart of the STRIPS algorithm. Click to enlarge.
Despite being over a third of a century old, this research is (somehow) still at the cutting edge of game AI. You’ll be seeing more games using this algorithm in 2008. However, most games will not use (or require) the full STRIPS implementation; they’ll keep the planner and ditch the theorem prover. It’s just not efficient enough to represent the world as a list of first-order predicates.
Instead, developers use a simple C/C++ data-structure or bitfield to represent the world. Then it becomes much more efficient to store the different states of the world and manipulate them with operators. In particular, see the F.E.A.R. SDK for inspiration and insights into how this was done in practice.
Once you have the basic representation efficient enough, then you can start to worry about catching up with the decades of improvements that have been made in planning research!
What do you think about STRIPS and its application to game AI? Post a comment below.