Information Technology Reference
In-Depth Information
a bound on the number of conflicts. If failing to solve a node within that bound, the over-
all solving procedure will backtrack to the lowest possible level restarting the search.
However, additional solutions to this problem still need to be investigated.
Among the advancements offered by the J-
TRE
software infrastructure w.r.t. to pre-
vious timeline representation frameworks, such as the T
RF
[5], we underscore the fol-
lowing: (i) the “unification” of the concept of
flaw
(i.e., a plan inconsistency) into a
single entity that is uniformly treated (and reasoned upon) throughout the whole J-
TRE
infrastructure. In J-
TRE
, flaw analysis and management is no longer spread across spe-
cialized reasoners depending on the flaw type, thus allowing to introduce more effective
search heuristics that exploit the cross-comparisons among flaws of different types; (ii)
the possibility to express constraint of increasing complexity among different domain
parameters (e.g., modeling the dependency between resource quantity to be produced
and the production activity duration, etc.); (iii) the introduction of the consumable re-
sources among the timeline types.
4
A Timeline-Based Planner Portfolio
Depending on the underlying available technology, the flaw solving procedure can de-
cide if creating a branch on the search tree or adding disjunctions to the underlying
constraint reasoner. Information from constraint reasoning can be exploited in flaw se-
lection and flaw resolution strategies.
Several scenarios can arise from having a single search space node with all possible
disjunctions to having a huge search space in which each node has its own constraint
reasoner.
4.1
Arc Consistency and Timeline-Based Planning: J-TRE
(ac)
Our first attempt at solving timeline-based planning problem has required the develop-
ment of a simple
arc consistency
algorithm (namely AC-3 [16]) for solving
Constraint
Satisfaction Problems
(CSP) and manage numeric variables (i.e., time-points, production
amounts, etc...). The CSP problem is defined as:
-
Asetof
variables
X
=
.
-
For each variable
x
i
, a finite set
D
i
of possible values (its
domain
). For our pur-
poses we consider only numeric variables so we can represent the domain through
a simply couple
[
lb,ub
]
representing all possible values between
lb
and
ub
(bound
consistency).
-
Asetof
constraints
restricting the values that the variables can simultaneously take.
{
x
1
,...,x
n
}
A
solution
to a CSP is an assignment of a value from its domain to every variable, in
such a way that all constraints are satisfied at once.
For each variable
x
i
, the algorithm maintains a
watch list
of constraints “watching”
x
i
. A queue data structure maintains all variables whose domain has been updated.
While the queue is not empty, a variable is selected from the queue and propagation
