Affiliations: Embedded Systems Unit, Fondazione Bruno Kessler, Via Sommarive 18, Trento, Italy
Correspondence:
[*]
Corresponding author: A. Micheli, Embedded Systems Unit, Fondazione Bruno Kessler, Via Sommarive 18, 38123 Trento, Italy. E-mail: [email protected].
Note: [1] This paper is based on the PhD Thesis work in [41] titled “Planning and Scheduling in Temporally Uncertain Domains” that won the “Marco Cadoli” award for the best PhD dissertation granted by the Italian Association for Artificial Intelligence. The article summarizes the thesis contribution concerning temporal networks scheduling and discusses the current status on this line of research as well as several promising future directions.
Abstract: Many Planning and Scheduling systems are designed assuming that the system under control is able to decide the duration of all the activities being executed. However, in many application scenarios this assumption is not acceptable because the actual timing of actions is not under direct control of the plan executor. Hence, new Planning and Scheduling techniques are needed to deal with this temporal uncertainty explicitly. In this paper, we summarize and systematize a series of works in which we addressed this uncertainty problem in the realm of temporal network scheduling. We show how Satisfiability Modulo Theory (SMT) solvers can be exploited to quickly solve different kinds of query in this setting. In particular, we focus on the framework of Disjunctive Temporal Networks with Uncertainty and address the three degrees of controllability for the fully-disjunctive class of problems, solving several open problems in the literature and experimentally showing the performance of the developed techniques. Finally, we outline and discuss several foreseeable directions of research in this field.
Keywords: Scheduling under uncertainty, temporal problems with uncertainty, temporal uncertainty, Satisfiability Modulo Theory
