We describe an application of a dynamic replanning technique in a highly dynamic and complex domain: the military aeromedical evacuation of patients to medical treatment facilities. U.S. Transportation Command (USTRANSCOM) is the U.S. Department of Defense (DoD) agency responsible for evacuating patients during wartime and peace. Doctrinally, patients requiring extended treatment must be evacuated by air to a suitable medical treatment facility. The Persian Gulf War was the first significant armed conflict in which this concept was put to a serious test. The results were far from satisfactory -- about 60 percent of the patients ended up at the wrong destinations. In early 1993, the DoD tasked USTRANSCOM to consolidate the command and control of medical regulation and aeromedical evacuation operations. The ensuing analysis led to TRAC2ES (TRANSCOM regulating and command and control evacuation system), a decision support system for planning and scheduling medical evacuation operations. Probably the most challenging aspect of the problem has to do with the dynamics of a domain in which requirements and constraints continuously change over time. Continuous dynamic replanning is a key capability of TRAC2ES. This article describes the application and the AI approach we took in providing this capability.

STAN is a Graphplan-based planner, so-called because it uses a variety of STate ANalysis techniques to enhance its performance. STAN competed in the AIPS-98 planning competition where it compared well with the other competitors in terms of speed, finding solutions fastest to many of the problems posed. Although the domain analysis techniques STAN exploits are an important factor in its overall performance, we believe that the speed at which STAN solved the competition problems is largely due to the implementation of its plan graph. The implementation is based on two insights: that many of the graph construction operations can be implemented as bit-level logical operations on bit vectors, and that the graph should not be explicitly constructed beyond the fix point. This paper describes the implementation of STAN's plan graph and provides experimental results which demonstrate the circumstances under which advantages can be obtained from using this implementation.

This article introduces a generic framework for constraint-directed search. The research literature in constraint-directed scheduling is placed within the framework both to provide insight into, and examples of, the framework and to allow a new perspective on the scheduling literature. We show how a number of algorithms from the constraint-directed scheduling research can be conceptualized within the framework. This conceptualization allows us to identify and compare variations of components of our framework and provides new perspective on open research issues. We discuss the prospects for an overall comparison of scheduling strategies and show that firm conclusions vis-a-vis such a comparison are not supported by the literature. Our principal conclusion is the need for an empirical model of both the characteristics of scheduling problems and the solution techniques themselves. Our framework is offered as a tool for the development of such an understanding of constraint-directed scheduling and, more generally, constraint-directed search.

Here scheduling, where we have fast, heuristic we identify a few properties of a real task and scheduling algorithms that yield dramatic produce mathematical abstractions of these speedups over traditional methods; decision properties. Again, both of those steps are perfectly making, where we have expert systems as standard good as initial exploration. But then we tools in many companies and products; work with the mathematical abstractions and and financial forecasting, where we don't hear never come back to the issues that came up in much about what people are doing, but Wall the original task. In some cases, new subfields Street firms seem to hire AI researchers at a of research have arisen based solely on this level rapid rate. of abstraction, and work becomes farther On the perception side, robots with vision and farther removed from the original motivating are revolutionizing manufacturing.

To remain competitive, enterprises must become increasingly agile and integrated across their functions. Enterprise models play a critical role in this integration, enabling better designs for enterprises, analysis of their performance, and management of their operations. This article motivates the need for enterprise models and introduces the concepts of generic and deductive enterprise models. It reviews research to date on enterprise modeling and considers in detail the Toronto virtual enterprise effort at the University of Toronto.

This article studies the problem of modifying the action ordering of a plan in order to optimise the plan according to various criteria. One of these criteria is to make a plan less constrained and the other is to minimize its parallel execution time. Three candidate definitions are proposed for the first of these criteria, constituting a sequence of increasing optimality guarantees. Two of these are based on deordering plans, which means that ordering relations may only be removed, not added, while the third one uses reordering, where arbitrary modifications to the ordering are allowed. It is shown that only the weakest one of the three criteria is tractable to achieve, the other two being NP-hard and even difficult to approximate. Similarly, optimising the parallel execution time of a plan is studied both for deordering and reordering of plans. In the general case, both of these computations are NP-hard. However, it is shown that optimal deorderings can be computed in polynomial time for a class of planning languages based on the notions of producers, consumers and threats, which includes most of the commonly used planning languages. Computing optimal reorderings can potentially lead to even faster parallel executions, but this problem remains NP-hard and difficult to approximate even under quite severe restrictions.

We examine the computational complexity of testing and finding small plans in probabilistic planning domains with both flat and propositional representations. The complexity of plan evaluation and existence varies with the plan type sought; we examine totally ordered plans, acyclic plans, and looping plans, and partially ordered plans under three natural definitions of plan value. We show that problems of interest are complete for a variety of complexity classes: PL, P, NP, co-NP, PP, NP^PP, co-NP^PP, and PSPACE. In the process of proving that certain planning problems are complete for NP^PP, we introduce a new basic NP^PP-complete problem, E-MAJSAT, which generalizes the standard Boolean satisfiability problem to computations involving probabilistic quantities; our results suggest that the development of good heuristics for E-MAJSAT could be important for the creation of efficient algorithms for a wide variety of problems.

To effectively generate a fast and consistent apartment construction project network, Hyundai Engineering and Construction and Korea Advanced Institute of Science and Technology developed a case- and constraint-based project-planning expert system for an apartment domain. The system, FAS-TRAK- APT, is inspired by the use of previous cases by a human expert project planner for planning a new project and the modification of these cases by the project planner using his/her knowledge of domain constraints. This large-scale, case-based, and mixed-initiative planning system, integrated with intensive constraint-based adaptation, utilizes semantic-level metaconstraints and human decisions for compensating incomplete cases imbedding specific planning knowledge. The case- and constraint-based architecture inherently supports cross-checking cases with constraints during system development and maintenance.

To effectively generate a fast and consistent apartment construction project network, Hyundai Engineering and Construction and Korea Advanced Institute of Science and Technology developed a case- and constraint-based project-planning expert system for an apartment domain. The system, FAS-TRAK- APT, is inspired by the use of previous cases by a human expert project planner for planning a new project and the modification of these cases by the project planner using his/her knowledge of domain constraints. This large-scale, case-based, and mixed-initiative planning system, integrated with intensive constraint-based adaptation, utilizes semantic-level metaconstraints and human decisions for compensating incomplete cases imbedding specific planning knowledge. The case- and constraint-based architecture inherently supports cross-checking cases with constraints during system development and maintenance. This system has drastically reduced the time and effort required for initial project planning, improved the quality and completeness of the generated plans, and is expected to give the company the competitive advantage in contract bids for new contracts.

The format of the conference will include paper presentations, invited speakers, panel discussions, workshops, and planning and scheduling competitions.