ProjectBlog: Search Planning Historical Developments Research Review

Blog: Search Planning Historical Developments Research Review

Udacity Artificial Intelligence and Specializations Nanodegree Program

This research review is about three important historical developments, which are STRIPS, PDDL, and GRAPHPLAN, in the field of AI planning and search. The representation of planning problems, which are states, actions, and goals, should make it possible for planning algorithms to take advantage of the logical structure of the problem. The key is to find a language that is expressive enough to describe a wide variety of problems, but restrictive enough to allow efficient algorithms to operate over it. [2]

The basic representation language of classical planners is known as the STRIPS language. STRIPS stands for STanford Research Institute Problem Solver. AI planning arose from investigations into statespace search, theorem proving, and control theory and from the practical needs of robotics, scheduling, and other domains. STRIPS (Fikes and Nilsson, 1971), the first major planning system, illustrates the interaction of these influences. STRIPS was designed as the planning component of the software for the Shakey robot project at SRI. Fikes and Nilsson (1993) give a historical retrospective on the STRIPS project and a survey of its relationship to more recent planning efforts. [1][2]

PDDL, Problem Domain Description Language (Ghallab et al., 1998), was introduced as a computerparsable, standardized syntax for representing STRIPS, ADL, and other languages. PDDL has been used as the standard language for the planning competitions at the AIPS conference, beginning in 1998. A systematic analysis was carried out by Ernst et al. (1997), who also developed an automatic “compiler” for generating propositional representations from PDDL problems. [2]

The heuristics can suffer from inaccuracies. A special data structure called a planning graph can be used to give better heuristic estimates. A solution directly from the planning graph can be extracted using a specialized algorithm such as the one called GRAPHPLAN. Avrim Blum and Merrick Furst (1995, 1997) revitalized the field of planning with their GRAPHPLAN system, which was orders of magnitude faster than the partial-order planners of the time. Other graph planning systems, such as IPP (Koehler et al., 1997), STAN (Fox and Long, 1998) and SGP (Weld et al., 1998), soon followed. Weld (1994, 1999) provides two excellent surveys of modern planning algorithms. It is interesting to see the change in the five years between the two surveys: the first concentrates on partial-order planning, and the second introduces GRAPHPLAN and SATPLAN. [2][3]


  1. Richard E. Fikes, Nils J. Nilsson (Winter 1971). “STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving”.
  2. 2. Stuart J. Russell, Peter Norvig (2010), Artificial Intelligence: A Modern Approach (3rd Edition).
  3. 3. Weld, D. S. (1999). “Recent advances in AI planning”. AI Magazine, 20 (2), 93–122.

Source: Artificial Intelligence on Medium

Leave a Reply

Your email address will not be published. Required fields are marked *

Back To Top

Display your work in a bold & confident manner. Sometimes it’s easy for your creativity to stand out from the crowd.