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 ﬁnd a language that is expressive enough to describe a wide variety of problems, but restrictive enough to allow efﬁcient algorithms to operate over it. 
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 ﬁrst major planning system, illustrates the interaction of these inﬂuences. 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. 
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. 
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 ﬁeld 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 ﬁve years between the two surveys: the ﬁrst concentrates on partial-order planning, and the second introduces GRAPHPLAN and SATPLAN. 
- Richard E. Fikes, Nils J. Nilsson (Winter 1971). “STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving”.
- 2. Stuart J. Russell, Peter Norvig (2010), Artificial Intelligence: A Modern Approach (3rd Edition).
- 3. Weld, D. S. (1999). “Recent advances in AI planning”. AI Magazine, 20 (2), 93–122.