Over the years we have given attention to the development of complete architectures for
planning and scheduling that are all based on a core CSP representation. The aim is to have
a number of specialized modules for main idea is summarized in the picture below.
There are three ingredients in a Planning and Scheduling architecture:
- a domain description language which is capable of modelling all the relevant
aspects of the environment in which problems are to be solved;
- a data structure which implements a computational model for the representation of
the domain description language. In general, this is done by means of constraint representation,
which has fomalizable computational properties and is known as CSP (Constraint Satisfaction
Problem) [Montanari 74]. This module is called a constraint database because it maintains
information on the state of the constraints it represents;
- a solving module, which searches for a solution by modifying the problem representation
maintained in the constraint database.
A number of well-known scheduling architectures have been implemented as CSP solvers, among
which OPIS (Smith), SONIA (Le Pape) and HSTS (Muscettola). As shown in the image above, our
CSP solver taxonomy includes also a user-interaction module, through which humans (which we
like to see as solvers them selves) interact with the solving engine in order to
synergetically find solutions to their problems.
The approach based on this schema have produced several complete systems over the years.
Interactive Scheduler: it is a prototype of architectire that is based
on ideas from temporal algorithms (in particular the tabu search described in
[Oddi, Cesta ECP-97]) empowered with an interactive front end that allows users to take simple
guiding choices with respect to different solution alternatives
[Oddi, A., Cesta, A, (2000) Toward interactive scheduling systems for managing medical resources,
Artificial Intelligence in Medicine, 20: 113-138].
O-OSCAR: this is a main effort of our group to develop a reusable architecture for scheduling
problems. The current version aims at offering a support to users in the whole plan life cycle
and is based on the ISES algorthm for project scheduling. A description is given in
[A. Cesta, G. Cortellessa, A. Oddi, N. Policella e A. Susi (2001)
A Constraint-Based Architecture for Flexible Support to Activity Scheduling.
F. Esposito (Ed.), AI*IA 2001: Advances in A. I., LNAI 2175, 2001].
MEXAR:. It is a complete application developed for the ESA mission
Mars Express. It integrates the same functional architecture based on a more specialized CSP
model of the problem to solve. See
[A. Cesta, G. Cortellessa, A. Oddi and N. Policella, A CSP-Based Interactive Decision Aid for
Space Mission Planning, Proceedings of AI*IA-03, Pisa, Italy, September 2003] for further details.