APSI
Advanced Planning & Scheduling Initiative

Results

The project produced a software framework for developing planning solutions and three different case studies to demonstrate the validity of the proposed approach, i.e. using AI technologies for space mission planning and scheduling.

Technology

APSI was developed in Java as an Eclipse-based plug-in architecture. It implements advanced planning and scheduling solutions based on constraint programming, local search, and mixed-initiative approach.

Development Team

To make best use of the vast knowledge in the field of AI in the two year period that the study was scheduled for, the project was performed by a consortium composed of four members, an industrial partner and three academic partners, all well versed in the field of AI planning and scheduling techniques. VEGA was the prime contractor in the study overseeing the whole project with the academic partners being the Institute of Cognitive Science and Technology of the Italian National Research Council of Italy (ISTC-CNR), the French Aerospace Lab ONERA, and the Aerospace Department of the Politecnico di Milano

---

Description

The final objective of the APSI project is to enhance operations by providing an AI experimental platform which allows rapid development of AI based tools for planning, scheduling and optimisation processes. The APSI study established a time-line representation framework with AI techniques and approaches in mind. This ultimate goal was achieved by

• trying to bridge the gap between advanced AI planning and scheduling techniques and the world of space mission planning and operations, by identifying typical operational planning problems that can be resolved by these techniques;
• designing and implementing a prototype framework for supporting the development of space-oriented AI-based planning applications;
• demonstrating the resolution of planning problems using AI-based techniques within the framework in three case studies.

The usage of AI technology and techniques within the field of planning and scheduling for space is growing. There are already many classical planning and scheduling applications used within the European Space Agency and in other agencies around the world. Some of these being very manual in nature and some being very automated tools. Currently only a handful make use of advanced AI techniques. In most cases these systems and procedures can be enhanced by the use of AI techniques at various stages of the planning and scheduling cycle. This is where the APSI study comes in who’s aim is to provide a framework to support the development of new and existing AI technologies within the space planning and scheduling domain by providing a core underlying AI modelling infrastructure.

The APSI framework provides a mechanism to allow mission specific information representing the planning problem to be modelled in a common and consistent way. This representation can be reasoned on using AI techniques. The main mechanisms are:

• AI Model-Based Approach
  • Re-usability
  • Flexibility and adaptability
• Time-line-Based Modelling
  • Relevant to real-world applications: space, mission operations, robotics, manufacturing, etc.
  • Capability of scheduling problem representation and solution
• Component-Based Design
  • Software reuse
  • Rapid prototyping of space applications
  • Simplified software design and development

Mars Express Science Planning Opportunities Construction Kit (MrSPOCK)

The problem to be tackled was to generate a pre-optimised skeleton plan for Mars Express Long Term Planning of science and maintenance windows. The case study has been supported by the Mars Express mission planning team based at ESOC in Darmstadt, Germany.
It is aimed at the pre-optimisation of the long term planning of maintenance windows and down-link opportunities during the nominal Medium Term Planning. In particular it focuses on:

• Minimising the iterations between Science Team and Mission Planning Team, taking into account a very detailed scenario and several co-existing constraints
• Providing the ability to explore the solution space according to different optimisation functions
  • maximise planned science
  • maximise total UpLink/DownLink (UL/DL) time

The optimisation procedure used for MrSPOCK has been based on Genetic Algorithms (GA). GA is a well-known and effective computational paradigm for function optimisation inspired from the study of population genetics. This was considered an appropriate approach due to the multi-objective nature of the planning problem. Indeed the GA is combined with a constructive heuristic procedure that instantiates the temporal plan which represent the complete and detailed output of MrSPOCK.

There were initially many teething problems encountered, this being the first case of the three test case scenarios and really the first time that the framework was fully exercised in the context of an application. Due to these issues the development of MrSPOCK took the longest of the three cases. This experience permitted the team to gain fruitful know-how for the design and implementation of new tool approaches that has been exploited for the remaining two cases.

APSI INTEGRAL Mission Scheduler (AIMS)

The second case was supported by the INTEGRAL (INTErnational Gamma-Ray Astrophysics Laboratory) long term planning team of the Integral Science Operations Centre (ISOC) based at ESAC in Madrid, Spain.
The main aim was to optimise the satisfaction of the scientific objectives expressed in the yearly announcements of opportunities. These announcements of opportunities, or AO’s as they are commonly called, are generated by the user community prior to the commencement of the next long term planning period which nominally covers one year. Not only do AO’s for the next planning period have to be considered but also AO’s from the previous planning period which were not scheduled are included, with increased priority.

To solve this optimisation problem, the APSI INTEGRAL MISSION Scheduler (AIMS) uses a local search algorithm that combines the best ideas from the state-of-the-art local search algorithms such as hill-climbing, tabu-search, and simulated annealing. This local search algorithm uses the underlying APSI framework to maintain flexible consistent schedules within each revolution and to determine the amount of observation time that can be added to the observations already scheduled within a revolution. In other words, the APSI framework is used to efficiently manage the basic scheduling constraints and the local search algorithm, built on top of it, is used to manage the optimisation criterion and specific constraints.

XMM-Newton Mission APSI Scheduler (XMAS)

The last case study was supported by the XMM-Newton long term science planning team, also based in ESAC, Madrid.
Following detailed analysis of the XMM-Newton planning problem, it could be seen that the planning required was very similar to that developed for the INTEGRAL tool. There were some subtle differences between the two missions though. Long-term planning for the XMM-Newton mission required a more dynamic initial plan with a lower filling factor to allow for the provision of short term changes to be made to the plan without major re-planning of the long-term plan. For these reasons it was decided to develop the XMM-Newton Mission APSI Scheduler (XMAS) based on the AIMS tool.

---

Publications

• Steel, R., Niézette,M., Cesta, A., Fratini,S., Oddi, A., Cortellessa, G., Rasconi, R., Verfaillie, G., Pralet, C., Lavagna, M., Brambilla, A., Castellini, F., Donati, A. and Policella, N. Advanced Planning and Scheduling Initiative: MrSPOCK AIMS for XMAS. In IJCAI Workshop on AI for Space. Pasadena, CA, (also poster session at IWPSS-09, 6th International Workshop on Planning and Scheduling for Space, and communication at ESAW-09, European Ground System Architecture Workshop), 2009
• Cesta, A., Cortellessa, G., Fratini, S., and Oddi, A. MrSPOCK: a Long-term Planning Tool for MARS EXPRESS. In IWPSS-09, 6th International Workshop on Planning and Scheduling for Space, Pasadena, CA, 2009
• C. Pralet and G. Verfaillie. AIMS: A Tool for Long-term Planning of the ESA INTEGRAL Mission. In IWPSS-09, 6th International Workshop on Planning and Scheduling for Space, Pasadena, CA, 2009
• M. Lavagna and F. Castellini. Advanced Planning and Scheduling Initiative’s XMAS tool: AI for automatic scheduling of XMM-Newton long term plan. In IWPSS-09, 6th International Workshop on Planning and Scheduling for Space, Pasadena, CA, 2009
• Donati, A., Policella, N., Cesta, A., Fratini, S., Oddi, A. Cortellessa, G., Pecora, F., Schulster, J., Rabenau, E., Niezette, M., Steel, R.Science Operations Pre-Planning and Optimization using AI constraint-resolution - the APSI Case Study 1. In SpaceOps-08. Proceedings of the 10th International Conference on Space Operations, Heidelberg, Germany, May 12-16, 2008