My PhD thesis titled "Planning and Scheduling in
Temporally Uncertain Domains" has been successfully
defended at the University of Trento, Italy on January, 19th 2016.
The thesis won the following awards and recognitions:
The thesis and the relative additional materials are available from the buttons below.
@phdthesis{micheli_thesis,
author = {Andrea Micheli},
title = {Planning and Scheduling in Temporally Uncertain Domains},
school = {University of Trento},
year = 2016,
month = 1,
note = {Fulltext available at \url{https://andrea.micheli.website}}
}
Any form of model-based reasoning is limited by the adherence of the
model to the actual reality. In temporal planning applications,
complex constraints and synchronizations are required, but often the
actual timing of actions is not under direct control of the plan
executor. For this reason, planning models must be able to express
temporal uncertainty to model this lack of control.
In this thesis, we focus on the temporal uncertainty issue in
scheduling and in temporal planning. 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 planning in domains featuring real-time constraints and
durations where some of the actions have a duration that is not under
the control of the planning agent.
Temporal Problems Representation
Consider this simple STNU example:

(Dashed lines are contingent links, orange nodes are uncontrollale)
The textual representation we use is the following:
5 4
A1 c
A2 c
X c
C1 u
C2 u
1 c A1 C1 1 3
1 c A2 C2 1 10
1 f C2 C1 -3 8
1 f X C1 6 12
The first line states that there are 5 time points and 4 constraints
Then, we have one line for each time point declaring its unique name
and whether it is controllable (c) or uncontrollable (u) Then, we have
one line for each constraint in the form
N [cf] (TP1 TP2 l
u)+
where
- N is the number of disjuncts for this constraints
(always 1 for a STNU)
- 'c' is for 'contingent' and 'f' stands for
'free'
- then we have N
constraints in the form "TP1 TP2 l u" where TP1 and TP2 are time point
names, l can be a float number or '-inf', u can be a float number or
"+inf". The meaning is the constraint TP2 - TP1 \in [l, u]
Strong Controllability Material
- The benchmarks and the encoders can be downloaded from the following URL:
constraints2013.tar.bz2 (774 MB)
- The PVYS implementation can be downloaded from the following URL:
pvys.tar.bz2 (2.5 MB)
Weak Controllability Material
- The benchmarks, the encoders and the strategy synthesis tool can
be downloaded from the following URL:
aij-weakcontr.tar.bz2 (641 MB)
Dynamic Controllability Material
- The benchmark and the synthesis and validation tools can be
downloaded from the following URL:
aaai16.zip (9.5 MB)
STPUD Material