STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving

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-lO 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.