This project is part of a larger project for EUMETSAT, the European agency responsible for meteorological satellites, and AIAI were asked by British Aerospace for help in the specification and prototyping of the scheduling component. After an initial feasibility study it was decided to prototype the system using PECOS, an object-oriented constraint programming tool. This approach allowed rapid development while retaining the flexibility to make changes as the problem specification evolved.
A typical problem that the EUMETSAT scheduler has to deal with consists of some 1300 activities over a 14 day period. Activities to be scheduled include regular fixed activities (e.g. image taking every 30 minutes), maintenance activities, and station keeping manoeuvres consisting of series of linked activities which maintain the satellite in its correct position. An important part of the problem was in recognising overconstrained problems (i.e. where it is not possible to meet all the constraints) and dealing with them appropriately.
The various types of activity were represented using classes. Each class of activity has a set of constraints which must be satisfied by all instances of the class (i.e., all activities of that type). The constraints mostly relate to the availability of resources, or to the fact that activities of this class should not be scheduled at the same time as activities of some other class. The availability and condition of resources is modelled by a state-vector which records the state of the resource over time. Activity constraints are written in activity class definitions as simple statements (e.g. (== Radiometer-mode Auto) ). The statement is either a precondition which must be true before the activity starts, or it must hold for the duration of the activity.
These statements are simply a convenient way of expressing the constraints, which may actually be interpreted by the prototype in various ways. For example, a constraint in one activity:
(during (== DATTS-15m-antenna Available))
stated that a particular antenna should be available for the duration of the activity. Since the only activity class which could make the antenna unavailable was Ant-15-Main. (maintenance), the constraint was translated to one stating that the activity should not overlap with any Ant-15-Main activities. Similar checks allowed the prototype to identify constraints which were impossible to satisfy.
In addition to constraints on classes of activities, the data usually constrains the start or end times of individual activities by relating them to other activities, to eclipses or to other events. These constraints also need to be interpreted by the prototype in order to formulate them as appropriate constraints for the tool. Since many of the activities being scheduled need to be monitored by operators at the ground station, there is a further constraint on the minimum gap between such tasks.
In the sample datasets that we worked with scheduling the activities was not found to be particularly difficult since there were generally relatively few activities with much flexibility in their allocation. Difficulty lay more in identifying activities or combinations of activities which were impossible. If an activity has a constraint which can never be satisfied (e.g. a required resource is not available during the activity's time window) the activity has to be dropped. Where two activities with fixed time windows are in conflict over a resource, the priority of the activities is used to decide which one to drop. However if the activities have some flexibility in when they are allocated, determining whether they are possible or not involves considering all of their possible allocations.
The prototype has been developed in the LeLisp version of Pecos and British Aerospace are now in the process of porting it to the C++ version of the tool, in order to integrate the scheduling component with the larger system.
Return to
AIAI information