Paper appeared in IEEE Expert - Intelligent Systems and their Applications, Winter 1996 Responsive Planning and Scheduling Using AI Planning Techniques -- Optimum-AIV Austin Tate, 21-Aug-96 Introduction Simple AI planning techniques involving the refinement of higher level actions in a plan into lower level expansions have found their way into many computer systems. However, there is some question over whether more elaborate techniques developed by the AI planning community have achieved the sort of widespread application that is now being seen for AI scheduling techniques. Experience at the Artificial Intelligence Applications Institute at the University of Edinburgh indicates that there are applications of a range of powerful AI planning techniques, but that these are not as yet as widespread as those for more narrowly focussed scheduling and constraint management techniques. This applications note is intended to document one example of a deployed planning aid based on a number of techniques that have been developed by the AI planning community. The primary example to be described is the Optimum-AIV system developed to assist with the project management of the assembly, integration and verification of spacecraft such as ERS-1 at the European Space Agency. As background, AIAI had worked with European partners CRI (Denmark) and Matra Espace (France) on earlier planning systems for ESA -- such as PlanERS -- a mission planer for ERS-1. The same team with the addition of ProgesSpace (France), was asked to build a deployable system as a result of these early demonstrations. AIAI was responsible for the plan representation used and object-oriented designs for the primary planning and test failure recovery planning algorithms. CRI acted as systems integrator and implementor for the whole system. AIAI drew on earlier work with NONLIN (Tate, 1977), O-Plan (Currie and Tate, 1991) and experience in using knowledge rich plan representations to augment commercial process planners, project managers and job shop schedulers on the PLANIT project (Drummond and Tate, 1992 -- a project involving 26 organizations in the UK). Optimum-AIV: Assembly, Integration and Verification of Spacecraft Planning is a key issue in the management of the assembly, integration and verification (AIV) activities of a space project. Not only must technological requirements be met, but cost and time are critical. There are costly testing facilities which must be shared with other projects, and there is a need to plan the coordination between a number of participants (agencies, contractors, launcher authorities, users). A delay caused by one participant normally leads to serious problems for others. Managers at al levels of a space project are concerned with planning, and they control closely the progress of the work. However, it has been difficult to find computer-based planning aids which meet the needs of this application. General purpose project management software cannot represent the wide range of factors to be taken into account, and are too complex to be used to interactively modify plans during project execution (Parrod et. al. 1993). For this reason, the European Space Agency commissioned the Optimum-AIV system which utilizes AI planning representations and techniques. Optimum-AIV, as a deployed system, was concerned with the integration of AI planning methods into an existing project management environment based on the use of the commercial ARTEMIS project management tool (the developer of ARTEMIS was a member of the PLANIT project with AIAI). Much of the project was concerned with user interface and integration issues. However, the plan representation utilized and the algorithms and aids that could be added because of the rich plan representation were an important advance. The applied AI planning techniques adopted complemented those facilities already available via ARTEMIS in a natural way. Details of Optimum-AIV and the techniques are available in Aarup et. al. (1995 -- from which extracts appear in the list of methods below). * Optimum-AIV adopts a partially-ordered plan representation, which supports causally independent activities that can be executed concurrently. * It searches through a space of partial plans, modifying them until a valid plan/schedule is found. * The system employs hierarchical planning. The term hierarchical refers to both the representation of the plan at different levels, and also the control of the planning process at progressively more detailed levels. * During plan specification and generation, the system operates on explicit preconditions and effects of activities that specify the applicability and purpose of the activity within the plans. With this knowledge, it is possible to check whether the current structure of the plan introduces any conflicts between actual spacecraft system states, computed by the system, and activity preconditions, which have been specified by the user. Such conflicts would arise if one activity deletes the effect of another, thus removing its contribution to the success of a further activity. The facility for checking the consistency of the plan logic, by dependency recording, is not possible within existing project management tools, which assume that the user must get this right. * Detailed constraints are associated with the plan. These represent resource and temporal constraints on the activities in the plan as well as a more general class of global activity constraints. The scheduling task in Optimum-AIV is considered as a constraint satisfaction problem solved by constraint-based reasoning. The constraints are propagated throughout the plan, gradually transforming it into a realizable schedule. Invariably not all of the constraints can be met, such that some have to be relaxed via user intervention. * During planning, the system records the rationale behind the plan structure, that is, user decisions on alternatives are registered. This is used to assist during plan repair where the user tries to restore consistency. Information can then be derived about alternative activities, soft constraints that may be relaxed, and potential activities that may be performed in advance. * Test Failure Recovery Plans are available as plan fixes to enable the plan to be brought back on track after the failure of a test during the assembly and integration process. The same AI planning methods used to generate a plan are also used to assist in fixing such problems. Optimum-AIV assists the user in plan repair in an interactive way rather than performing the repair itself. Following an evaluation of Optimum-AIV at ESA, it has been reported (Parrod et. al, 1993) that the system is in use for planning the production of the vehicle equipment bays of the European Ariane 4 launcher. It was reported that the system was chosen by the Araine-4 project team due to the following: * the wealth of information which can be provided to and used by the tool to describe the constraints inherent in the AIV activity. * the quality of support provided by the tool to allow resource conflicts to be resolved. * the clear representation of information and the interactive capabilities which enables engineering management to access several planning scenarios on-line. * the fact that Optimum-AIV provides a single solution to problems of managing the plan, schedule and allocation of resources amongst competing vehicle equipment bays which are concurrently being assembled. Optimum-AIV provides a rich plan representation and aids to allow for the editing of AIV planning information and a wide range of constraints on the process. This information forms a basis for plan generation, checking of plan logic and analysis of plans. Facilities are available to allow for the interactive repair of executing plans when tests indicate failures of components under assembly and integration. Optimum-AIV is an example of a deployed application of a number of AI planning techniques. References Aarup, M., Arentoft, M.M., Parrod, Y., Stokes, I., Vadon, H. and Stader, J. (1994) Optimum-AIV: A Knowledge-Based Planning and Scheduling System for Spacecraft AIV, in Intelligent Scheduling (eds. Zweben, M. and Fox, M.S.), pp. 451-469, Morgan Kaufmann. Currie, K. and Tate, A. (1991) O-Plan: the Open Planning Architecture, Artificial Intelligence Vol. 52, pp. 49-86, Elsevier. Drummond, M.E., and Tate, A. (1992) PLANIT Interactive Planners' Assistant -- Rationale and Future Directions, reprints of working papers to the Alvey Programme PLANIT Community Club distributed in 1986-7. Available as AIAI-TR-108, AIAI, University of Edinburgh. Parrod, Y., Valera, S. (1993) Optimum-AIV, A Planning Tool for Spacecraft AIV, in Preparing for the Future, Vol. 3, No. 3, pp. 7-9, European Space Agency. Also available through http://www.aiai.ed.ac.uk/~pasg/Projects/optimum_home.html Tate, A. (1977) Generating Project Networks, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-77), pp. 888-893, Cambridge, MA, USA, Morgan Kaufmann.