Automated planning and scheduling

Introduction

Planning is considered as the process that determines the sequential order of actions that must be carried out to achieve a goal, and scheduling consists of identifying whether adequate resources are available to carry out the plan, specifying the date and time of the tasks to be performed. Planning and scheduling solutions can be both long-term and short-term, which adds complexity when creating them.

Automated planning and scheduling is a very active field of research within the area of Artificial Intelligence, focusing on the optimization of sequences of actions that should be executed by intelligent agents. Unlike classical classification and control problems, planning solutions are complex and have to be discovered and optimized in a multidimensional space. In static and deterministic environments that can be easily modeled, automatic planning can be performed a priori (i.e., solutions can be found and evaluated before the execution). However, in unknown, dynamic and nondeterministic environments, action sequences need to be reviewed and adapted during their execution, which adds significant complexity to the solution of the problem.

The automatic planning and scheduling of space missions, ground-based observatories and astronomical instruments has become of strategic importance for several reasons: to coordinate the operation of multiple instruments or observatories located at different points of the Earth; the dynamic and fast reaction to changes in the environment or to astronomical phenomena; maximizing scientific return and minimizing operating costs; etc. Automated planning and scheduling is a branch of Artificial Intelligence that responds to these challenges, increasing the autonomy and efficiency of these scientific infrastructures.

Generally, the planning and scheduling of astronomical observations has more than one parameter that needs to be optimized, resulting in a Multi-objective Optimization Problem that can be defined as the problem of finding a vector of decision variables satisfying constraints and optimizing a vector function whose elements represent the objective functions. These functions form a mathematical description of performance criteria that are usually not disjoint (i.e., they are in conflict with each other). Hence, the term “optimize” refers to find a solution that yields acceptable values for all objective functions.
 

Focus

The purpose of our research is two-fold: first, to propose, analyze and develop techniques aimed on building efficient plans (with a scope that can range from years to a day) fulfilling all the constraints of the problem that can be predicted; and second, to define and implement processes that adapt the ideal plans reacting dynamically to unexpected situations in a short period of time (in the order of a few seconds).
 

The first research line is framed in the field of global search devoted to automated planning and scheduling for constraint-based problems. Particularly, we mainly focus on scheduler systems based on Evolutionary Algorithms (e.g., Genetic Algorithms, Multiobjective Evolutionary Algorithms), which are Artificial Intelligence techniques that emulate natural evolution by means of combining potential solutions using selection, combination and mutation operators. The goal of Evolutionary Algorithms is to efficiently explore a large amount of potential solutions in order to find near-optimal solutions. A solution is considered near-optimal (or efficient) when it fulfills all problem constraints and it highly optimizes the objectives defined by the problem (i.e., maximization of the time observing objects, minimization of idle time, maximization of completed proposals). In this sense, we pay special attention to Multiobjective Evolutionary Algorithms, which are recognized as one of the most valuable and promising approaches to addressing complex and diverse problems of multi-objective optimization.
 

The second research line is focused on defining dispatcher algorithms based on astronomical heuristics that repair the ideal plans avoiding intensive calculations in order to provide a response in a few seconds. This step requires a great understanding of the problem where the process is being applied in order to define rules that model the reaction that scientists/engineers/operators expect in particular situations, without leaving aside the optimization obtained by the scheduler system.

  • M. Perger, A. Garcia-Piquer, I. Ribas, J. C. Morales, et al., “The HADES RV Programme with HARPS-N@TNG II. Data treatment and simulations”. Astronomy & Astrophysics, 598(A26), 2017.
  • J. Caballero, J. Guàrdia, L. M. del Fresno, M. Zechmeister, E. de Juan, F. Alonso-Floriano, P. Amado, J. Colomé, M. Cortés-Contreras, A. Garcia-Piquer, L. Gesa, et al., “CARMENES: data flow”. In Proceedings of SPIE, Observatory Operations: Strategies, Processes, and Systems VI, pp. 99100G-99100G, International Society for Optics and Photonics, 2016.
  • F. Vilardell, G. Artigues, J. Sanz, Á. Garcia-Piquer, J. Colomé, I. Ribas, “Using Robotic Operating System (ROS) to control autonomous observatories”, In Proceedings of SPIE, Software and Cyberinfrastructure for Astronomy IV, 9913, SPIE Astronomical Telescopes+ Instrumentation, pp. 99132V, 2016.A. Garcia-Piquer, I. Ribas, and J. Colomé. “Artificial intelligence for the echo mission planning tool”. Experimental Astronomy, pp. 1–24, 2014.
  • A. Garcia-Piquer, J. Guàrdia, J. Colomé, I. Ribas, L. Gesa, J. C. Morales, et al., “CARMENES Instrument Control System and Operational Scheduler”. In Proceedings of SPIE, Software and Cyberinfrastructure for Astronomy III, pp. 915221. International Society for Optics and Photonics, 2014.
  • A. Garcia-Piquer, I. Ribas, and J. Colomé, “Artificial Intelligence for the EChO Long-Term Mission Planning Tool”. In Proceedings of SPIE, Observatory Operations: Strategies, Processes, and Systems V, pp. 91491U. International Society for Optics and Photonics, 2014
  • J. Colome, P. Colomer, J. Guàrdia, et al., “Research on schedulers for astronomical observatories”. In Proceedings of SPIE,  Observatory Operations: Strategies, Processes, and Systems IV, vol. 8448, pp. 84481L, International Society for Optics and Photonics, 2012.
Senior Institute members involved

A. Garcia, J. Colomé.
 
Institute of Space Sciences (IEEC-CSIC)

Campus UAB, Carrer de Can Magrans, s/n
08193 Barcelona.
Phone: +34 93 737 9788
Email: ice@ice.csic.es
Website developed with RhinOS

Síguenos


An institute of the Consejo Superior de Investigaciones Científicas

An institute of the Consejo Superior de Investigaciones Científicas
Affiliated with the Institut d'Estudis Espacials de Catalunya

Affiliated with the Institut d'Estudis Espacials de Catalunya