There has been evidence that least-commitment planners can efficiently handle planning problems that involve difficult goal interactions. This evidence has led to the common belief that delayed-commitment is the "best" possible planning strategy. However, we recently found evidence that eager-commitment planners can handle a variety of planning problems more efficiently, in particular those with difficult operator choices. Resigned to the futility of trying to find a universally successful planning strategy, we devised a planner that can be used to study which domains and problems are best for which planning strategies. In this article we introduce this new planning algorithm, FLECS, which uses a FLExible Commitment Strategy with respect to plan-step orderings. It is able to use any strategy from delayed-commitment to eager-commitment. The combination of delayed and eager operator-ordering commitments allows FLECS to take advantage of the benefits of explicitly using a simulated execution state and reasoning about planning constraints. FLECS can vary its commitment strategy across different problems and domains, and also during the course of a single planning problem. FLECS represents a novel contribution to planning in that it explicitly provides the choice of which commitment strategy to use while planning. FLECS provides a framework to investigate the mapping from planning domains and problems to efficient planning strategies.

The Association for the Advancement of Artificial Intelligence held its 1994 Fall Symposium Series on November 4-6 at the Monteleone Hotel in New Orleans, Louisiana. This article contains summaries of the five symposia that were conducted: (1) Control of the Physical World by Intelligent Agents, (2) Improving Instruction of Introductory AI, (3) Knowledge Representation for Natural Language Processing in Implemented Systems, (4) Planning and Learning: On to Real Applications, and (5) Relevance.

The paradigms of transformational planning, case-based planning, and plan debugging all involve a process known as plan adaptation - modifying or repairing an old plan so it solves a new problem. In this paper we provide a domain-independent algorithm for plan adaptation, demonstrate that it is sound, complete, and systematic, and compare it to other adaptation algorithms in the literature. Our approach is based on a view of planning as searching a graph of partial plans. Generative planning starts at the graph's root and moves from node to node using plan-refinement operators. In planning by adaptation, a library plan - an arbitrary node in the plan graph - is the starting point for the search, and the plan-adaptation algorithm can apply both the same refinement operators available to a generative planner and can also retract constraints and steps from the plan. Our algorithm's completeness ensures that the adaptation algorithm will eventually search the entire graph and its systematicity ensures that it will do so without redundantly searching any parts of the graph.

The Workshop on Comparative Analysis of AI Planning Systems, held during the 1994 national AI conference, was lively and interesting. Both the theoretical and practical sides of the AI planning community were represented. Several papers contributed to the theoretical analysis of planning algorithms, and others showed the first steps toward convergence between such theoretical work and practical work on the system engineering aspects of working planners.

Recent developments have clarified the process of generating partially ordered, partially specified sequences of actions whose execution will achieve an agent's goal. This article summarizes a progression of least commitment planners, starting with one that handles the simple STRIPS representation and ending with UCPOP, a planner that manages actions with disjunctive precondition, conditional effects, and universal quantification over dynamic universes. Along the way, I explain how Chapman's formulation of the modal truth criterion is misleading and why his NP-completeness result for reasoning about plans with conditional effects does not apply to UCPOP.

Fall 1994, 63-75 Abbott, Kathy, see Orlando, Nancy AI and NP-Hard Problems: 1993 Spring Alterman, Richard, see Hendler, James Abhyankar, R. B. Review of Computing Symposium Report.

Kambhampati presented theoretical planning systems is difficult. Although national AI conference, was lively It was noted that comparing planners encoding expert knowledge is at the and interesting. Both the theoretical is similar in difficulty to comparing heart of HTN planning, there and practical sides of the AI planning programming languages (in fact, the remains a considerable gap to bridge community were represented, input specifications to a planner can in using expert planning knowledge and both sides seemed to understand be viewed as a programming language). Shlomo Zilberstein (University Third, it was generally acknowledged Several papers contributed further of Massachusetts) presented a that common plan representations to the theoretical analysis of number of evaluation measures. A algorithms or through empirical An integrated system that executes common representation would allow studies (Christer Backstrom, or uses the generated plans formal comparisons among widely Linkoping University, Sweden; Subbarao should be evaluated instead of simply different planning technologies.

For many years, the intuitions underlying partial-order planning were largely taken for granted. Only in the past few years has there been renewed interest in the fundamental principles underlying this paradigm. In this paper, we present a rigorous comparative analysis of partial-order and total-order planning by focusing on two specific planners that can be directly compared. We show that there are some subtle assumptions that underly the wide-spread intuitions regarding the supposed efficiency of partial-order planning. For instance, the superiority ofpartial-order planning can depend critically upon the search strategy and the structure of the search space. Understanding the underlying assumptions is crucial for constructing efficient planners.

This report stems from an April 1994 meeting, organized by AAAI at the suggestion of Steve Cross and Gio Wiederhold.1 The purpose of the meeting was to assist ARPA in defining an agenda for foundational AI research. Prior to the meeting, the fellows and officers of AAAI, as well as the report committee members, were asked to recommend areas in which major research thrusts could yield significant scientific gain -- with high potential impact on DOD applications -- over the next ten years. At the meeting, these suggestions and their relevance to current national needs and challenges in computing were discussed and debated. An initial draft of this report was circulated to the fellows and officers. The final report has benefited greatly from their comments and from textual revisions contributed by Joseph Halpern, Fernando Pereira, and Dana Nau.

The Association for the Advancement of Artificial Intelligence (AAAI) held its 1994 Spring Symposium Series on 19-23 March at Stanford University, Stanford, California. This article contains summaries of 10 of the 11 symposia that were conducted: Applications of Computer Vision in Medical Image Processing; AI in Medicine: Interpreting Clinical Data; Believable Agents; Computational Organization Design; Decision-Theoretic Planning; Detecting and Resolving Errors in Manufacturing Systems; Goal-Driven Learning; Intelligent Multimedia, Multimodal Systems; Software Agents; and Toward Physical Interaction and Manipulation. Papers of most of the symposia are available as technical reports from AAAI.