Planning and Scheduling in Temporally Uncertain Domains

Micheli, Andrea (2016) Planning and Scheduling in Temporally Uncertain Domains. PhD thesis, University of Trento.

[img]PDF - Doctoral Thesis
Restricted to Repository staff only until 9999.

2594Kb

Abstract

Any form of model-based reasoning is limited by the adherence of the model to the actual reality. Scheduling is the problem of finding a suitable timing to execute a given set of activities accommodating complex temporal constraints. Planning is the problem of finding a strategy for an agent to achieve a desired goal given a formal model of the system and the environment it is immersed in. When time and temporal constraints are considered, the problem takes the name of temporal planning. A common assumption in existing techniques for planning and scheduling is controllability of activities: the agent is assumed to be able to control the timing of starting and ending of each activity. In several practical applications, however, the actual timing of actions is not under direct control of the plan executor. In this thesis, we focus on this temporal uncertainty issue in scheduling and in temporal planning: we propose to natively express temporal uncertainty in the model used for reasoning. We first analyze the state-of-the-art on the subject, presenting a rationalization of existing works. Second, we show how Satisfiability Modulo Theory (SMT) solvers can be exploited to quickly solve different kinds of query in the realm of scheduling under uncertainty. Finally, we address the problem of temporal planning in domains featuring real-time constraints and actions having duration that is not under the control of the planning agent.

Item Type:Doctoral Thesis (PhD)
Doctoral School:Information and Communication Technology
PhD Cycle:27
Subjects:Area 01 - Scienze matematiche e informatiche > INF/01 INFORMATICA
Area 09 - Ingegneria industriale e dell'informazione > ING-INF/05 SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
Area 01 - Scienze matematiche e informatiche > MAT/01 LOGICA MATEMATICA
Uncontrolled Keywords:Temporal Planning with Uncontrollable Durations, Scheduling under Uncertainty, Temporal Problems with Uncertainty, Temporal Uncertainty, Satisfiability Modulo Theory
Funders:Fondazione Bruno Kessler
Repository Staff approval on:03 Feb 2016 11:19

Repository Staff Only: item control page