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.

Real-time problem solving is not only reasoning about time, it is also reasoning in time. This ability is becoming increasingly critical in systems that monitor and control complex processes in semiautonomous, ill-structured, real-world environments. Many techniques, mostly ad hoc, have been developed in both the real-time community and the AI community for solving problems within time constraints. However, a coherent, holistic picture does not exist. This article is an attempt to step back from the details and examine the entire issue of real-time problem solving from first principles. We examine the degrees of freedom available in structuring the problem space and the search process to reduce problem-solving variations and produce satisficing solutions within the time available. This structured approach aids in understanding and sorting out the relevance and utility of different real-time problem-solving techniques.

Within a simple test-bed, application of feed-forward neurocontrol for short-term planning of robot trajectories in a dynamic environment is studied. The action network is embedded in a sensorymotoric system architecture that contains a separate world model. It is continuously fed with short-term predicted spatiotemporal obstacle trajectories, and receives robot state feedback. The action net allows for external switching between alternative planning tasks. It generates goal-directed motor actions - subject to the robot's kinematic and dynamic constraints - such that collisions with moving obstacles are avoided.