Information Technology


ITAS: A Portable, Interactive Transportation Scheduling Tool Using a Search Engine Generated from Formal Specifications

AAAI Conferences

This report describes a prototype application of Kestrel Institute's research on the transformationai development of high-performance transportation schedulers. 1 The system, ITAS, for In-Theater Transportation Scheduler, is designed to assist human schedulers of airplanes who work to produce daily flight 1This research was supported by ARPA/Rome Laboratories under Contracts F30602-91-C-014 (BBN) and F30602-91-C-0043 (Kestrel).


Event-Based Decompositions for Reasoning about External Change in Planners

AAAI Conferences

An increasing number of planners can handle uncertainty in the domain or in action outcomes. However, less work has addressed building plans when the planner's world can change independently of the planning agent in an uncertain manner. In this paper, I model this change with external events that concisely represent some aspects of structure in the planner's domain. This event model is given a formal semantics in terms of a Markov chain, but probabilistic computations from this chain would be intractable in real-world domains. I describe a technique, based on a reachability analysis of a graph built from the events, that allows abstractions of the Markov chain to be built to answer specific queries efficiently. I prove that the technique is correct. I have implemented a planner that uses this technique, and I show an example from a large planning domain.


Local Planning of Ongoing Activities

AAAI Conferences

An agent that learns about the world while performing its jobs has to plan in a flexible and focused manner: it has to reflect on how to perform its jobs while accomplishing them, focus on critical aspects of important subtasks, and ignore irrelevant aspects of their context. It also has to postpone planning when lacking information, reconsider its course of action when noticing opportunities, risks, or execution failures, and integrate plan revisions smoothly into its ongoing activities. In this paper, we add constructs to RPL (Reactive Plan Language) that allow for local planning of ongoing activities. The additional constructs constitute aa interface between RPL and pla.uning processes that is identical to the interface between RPL Structured reactive plans are written in RPL (Reactive Plan Language), which provides constructs for sequencing, conditionals, loops, local variables, and subroutines. The language also contains high-level concepts (interrupts, monitors) that can be used to synchronize parallel actions, to make plans reactive, etc. Planning: XFRM applies a planning technique called transformational planning of reactive behavior: the robot controller retrieves routine plans for the robot's jobs from a plan library. Planning processes revise structured reactive plans to avoid flaws in the robot's routine behavior that become predictable as the robot learns new information.


Modeling Planning Tasks

AAAI Conferences

The analysis of planning systems in terms of the different algorithms they use needs to be complemented by a study of how these systems represent and use available knowledge -- in other words, of their prob- /era solving methods. This is an essential aspect in finding out how to engineer a planning system and obtain a desired performance in an application and its engineering. One analysis of this type has been made in (Valente 1995). However, that analysis was incomplete, because it concentrated on the organization of the domain knowledge used by the system. Another equally important aspect is the way this knowledge is used in the planning process. These two are complementary aspects in the description of a problem-solving method. In this paper, we will depart from and complement Valente's analysis by providing a more detal]ed discussion on planning tasks, providing a general, high-level task. Keywords: classical planning, comparison of planning problem-solving methods, knowledge-level analysis Introduction There is a large amount of research in the planning community on the design and analysis of planning algorithms, with particular emphasis on their efficiency.


Online Planning Simulation Scott D. Anderson

AAAI Conferences

Experimental Knowledge Systems Laboratory University of Massachusetts Amherst, MA 01003-4610 cohen@cs, umass, edu Abstract MESS is a substrate for building simulation environments suitable for testing plans and online or realtime planners. The article describes the design of MEss, how simulations are built and how online planners integrate with the substrate. MEss supports activities, defined as processes over some time interval, and interactions between activities and other simulation events. MEss interfaces with TCL, which is a portable, extensible definition of computation time, enabling MESS to be used for platform-independent simulations of real-time planning. MESS has been used to re-implement the PHOENIX testbed, which simulates forest fires and planning for firefighting agents. As planners become more sophisticated, they will solve increasingly large planning problems involving, for example, the movement and actions of thousands of vehicles, over many hours and under changing conditions. It is extremely difficult to inspect such elaborate plans and determine, for example, their probability of success, the extent to which their goals will be satisfied, and so forth. Nevertheless, such evaluation is critical to a scientific understanding of how and how well a sophisticated planner works. We believe simulation is necessary to evaluate planners: plans are run man)" times in the space of conditions that they were meant to handle, and various dependent variables are measured and statistically analyzed.


Preface

AAAI Conferences

The second conference (AIPS-94) was held at the University of Chicago in June 1994 and was organized by Kristian Hammond. This conference was held in Edinburgh, Scotland on May 29th - 31st 1996. Planning: formulating a course of action, and related fields such as scheduling or reasoning about actions have a long research tradition in AI, with many researchers world wide working in them. It is one of the aims of this conference to bring a number of these related themes together and this has been reflected by the selection of a number of scheduling papers, with the aim of promoting discussion between the two communities. An additional aim of the conference is to promote the application of planning technologies in the real world, as a number of initiatives have shown the time is now ripe to start applying planning and scheduling technologies and seeing the benefits of many years of research.


A Framework for Automatic Problem Decomposition in Planning

AAAI Conferences

Partial order plan-Our framework of domain decomposition has a number of similarities with abstract planning theory. Planning with abstraction starts with a hierarchy of abstract spaces, each having its own operators. An abstract plan is constructed at each abstraction level, in a top-down fashion. Each successively higher level of abstraction is a simplified version of the original space. In the robot-box example, plans for moving boxes might be constructed before plans for both moving boxes and opening doors.


AIPS94-058.pdf

AAAI Conferences

Case-based reasoning (CBR)(Riesbeck, Schank, 1989) has been applied to a wide diversity of areas such as military strategic planning (Goodman, 1989), conceptual design (Sycara, Navinchandra, 1991), and assembly planning (Pu, Reschberger, 1991). However, few papers have been published in applying CBR in manufacturing process planning. All the systems developed in the domain of mechanical design and manufacturing did not have rigorous simulation mechanisms, therefore, could not have powerful and complete case adaptation modules. This paper introduces the case adaptation in a case-based process planning system. In order to convert the design of a mechanical part om the blue print to a real part, a manufacturing process plan which contains all the detailed instructions of each machining process needs to be generated.


Learning Planning Operators by Observation and Practice Xuemei Wang

AAAI Conferences

The work described in this paper addresses learning planning operators by observing expert agents and subsequent knowledge refinement in a learning-by-doing paradigm. The observations of the expert agent consist of: 1) the sequence of actions being executed, 2) the state in which each action is executed, and 3) the state resulting from the execution of each action. Planning operators are learned from these observation sequences in an incremental fashion utilizing a conservative specific-to-general inductive generalization process. In order to refine the new operators to make them correct and complete, the system uses the new operators to solve practice problems, analyzing and learning from the execution traces of the resulting solutions or execution failures. We describe techniques for planning and plan repair with incorrect and incomplete domain knowledge, and for operator refinement through a process which integrates planning, execution, and plan repair. Our learning method is implemented on top of the PRODIGY architecture(Carbonell, Knoblock, & Minton 1990; Carbonell et al. 1992) and is demonstrated in the extended-strips domain(Minton 1988) and a subset the process planning domain(Gil 1991).


Opportunities: A unifying framework for planning and execution

AAAI Conferences

The real world is regular enough to make advance planning worthwhile, yet unpredictable enough to make planning to the last detail impossible. An autonomous agent must therefore strike a balance between planning ahead and reacting to changes. For example, a robot on a strange planet must determine which areas to explore, where to take soil samples, what routes to take, and so on. The right chokes will depend on details concerning the terrain encountered, the atmospheric conditions, and the results of tests performed on earlier samples--factors that cannot, in general, be predicted in sufficient detail to allow firm decisions to be made in advance. On the other hand, undirected wandering makes little sense: enough will be known in advance to make some decisions that will make a productive mission more likely.