Special issue on planning: an introduction

Reasoning about actions is a pervasive form of human activity. The ability to establish goals and plan courses of action to achieve them is a prominent characteristic of intelligent behavior. During the last several years, interest in planning research within the artificial intelligence community has been increasing. Areas as diverse as factory automation, natural-language understanding, and mobile robots have recognized the need for planning. Reasoning about actions is necessarily ubiquitous. If a computing system is to have some effect on the world, whether it be by having a robot physically move an object, or a computer program send a piece of electronic mail or delete a file, then intelligent behavior requires the system to reason about the effects of its actions. If the problem can be simplified so that planning courses of action is not necessary, then the resulting behaviors will also be simple. Thus, reasoning about actions is one of the core problems to be addressed if we are to create intelligent systems. However, the planning problem is extremely difficult and progress over the last few decades has been slow. Chapman has only recently shown that determining the truth of a proposition in a planning system which allows unordered actions is NP-complete, even with a fairly simple representation language. In addition, a useful planner may have other combinatonal problems to address in addition to the basic one of determining whether or not a proposition is true. For example, assigning resources, replanning after unexpected events, determining how parallel actions interact with each other, and the deduction of context-dependent effects can all be combinatonal problems. This issue contains six papers describing recent results on the planning problem. Five of these six papers build upon the state-based representations and planning techniques that have formed the mainstream of A1 planning research. The sixth paper, Lansky’s “Localized event-based reasoning for multiagent domains,” proposes a new approach that is event-based rather than state-based. While several recent A1 representations have been using events to a greater extent, Lansky’s system is based strictly on-an event-based temporal logic. This approach appears to be well-suited for certain types of problems, such as multiagent domains. Another focus of Lansky’s work is the localization of planning search spaces in order to eliminate the combinatorics of interactions between all possible actions. The system permits ports through which events in different local groups can interact with each other. This is a promising approach, but it remains to be seen how real domains can be partitioned into localized planning spaces. Drummond’s paper describes a heuristic for state-based planners that can be used to choose between alternative plan modifications. A property of plans called temporal coherence is defined. The proposed heuristic is that the planner refuse to investigate any alternatives that are not temporally coherent. This heuristic preserves completeness in the sense that at least one valid solution is guaranteed to be in the space that is