Since the early 1970s, the AI planning community has been closely concerned with the design of artificial agents; in fact, it seems reasonable to claim that most innovations in agent design have come from this community. Planning is essentially automatic programming: the design of a course of action that, when executed, will result in the achievement of some desired goal. Within the symbolic AI community, it has long been assumed that some form of AI planning system will be a central component of any artificial agent. Perhaps the best-know early planning system was STRIPS [Fikes and Nilsson, 1971]. This system takes a symbolic descripion of both the world and a desired goal state, and a set of action descriptions, which characterise the pre- and post-conditions associated with various actions. It then attempts to find a sequence of actions that will achieve the goal, by using a simple means-ends analysis, which essentially involves matching the post-conditions of actions against the desired goal. The STRIPS planning algorithm was very simple, and proved to be ineffective on problems of even moderate complexity. Much effort was subsequently devoted to developing more effective techniques. Two major innovations were hierarchical and non-linear planning [Sacerdoti, 1975][Sacerdoti, 1974]. However, in the mid 1980s, Chapman established some theoretical results which indicate that even such refined techniques will ultimately turn out to be unusable in any time-constrained system [Chapman, 1987]. These results have had a profound influence on subsequent AI planning research; perhaps more than any other, they have caused some researchers to question the whole symbolic AI paradigm, and have thus led to the work on alternative approaches that we discuss in section 3.2.
In spite of these difficulties, various attempts have been made to construct agents whose primary component is a planner. For example: the Integrated Planning, Execution and Monitoring (IPEM) system is based on a sophisticated non-linear planner [Ambros-Ingerson and Steel, 1988]; Wood's AUTODRIVE system has planning agents operating in a highly dynamic environment (a traffic simulation) [Wood, 1993]; Etzioni has built `softbots' that can plan and act in a UNIX environment [Etzioni et al., 1994]; and finally, Cohen's PHEONIX system includes planner-based agents that operate in the domain of simulated forest fire management [Cohen et al., 1989].