Planning and Scheduling in Temporally Uncertain Domains

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.

Grantor dc:publisher

Università degli studi di Trento

Year dc:date

2016

Author dc:creator

• Micheli, Andrea

Contributors dc:contributor

• Cimatti, Alessandro
• Roveri, Marco

• Settore INF/01 - Informatica
• Settore ING-INF/05 - Sistemi di Elaborazione delle Informazioni
• Settore MAT/01 - Logica Matematica

Statement dc:rights

• info:eu-repo/semantics/closedAccess
• license:Tutti i diritti riservati (All rights reserved)

Language dc:language

eng

Identifier

http://dx.doi.org/10.15168/11572_368813
10.15168/11572_368813

OAI identifier oai:identifier

oai:iris.unitn.it:11572/368813