Information Technology Reference
In-Depth Information
is performed on all constraints of the watch list associated to the variable possibly up-
dating other variables and enqueueing them. The algorithm goes on until the queue
becomes empty (the CSP is arc consistent) or a variable domain becomes empty (the
CSP is inconsistent).
If we consider our CSP as a directed graph with nodes representing variables of
the problem and arcs between variables representing constraints, the worst-case time
complexity of AC-3 algorithm is
O
e
d
3
where
e
is the number of arcs and
d
is the
·
size of the largest variable domain.
It is worth underscoring that two key complexity factors here are: (i) the need to
tackle huge domains (e.g.,
[0
,
+inf]
is a common domain for temporal arguments) and
(ii) possible presence of cyclic networks. A simple update to the algorithm consists in
limiting the number of possible updates of each variable to the number of constraints of
the CSP. Exceeding this limit would obviously determine the existence of a cycle that
incrementally would empty the domain of some variable involved in the cycle itself re-
sulting in an inconsistent CSP. This fact allowed us to move worst-case time complexity
of our AC-3 algorithm to
O
e
min (
e,d
)
3
removing, in most cases, the discouraging
domain size from time complexity.
A further required extension to the AC-3 algorithm is to make it backtrackable. A
queue data structure maintains, for each level, the domain of the variables before being
updated as well as the added constraints. When backtracking, we can restore variable
domains and remove added constraints from watch lists. It is worth noting that this
architecture allows us to maintain a single CSP reasoner for the entire timeline problem
solving procedure. Indeed, not constrained variables have an empty watch list and are
not involved in the propagation procedure.
·
Flaw Management in J-TRE
(ac)
.
First thing we do is to generate the initial partial
plan by executing the DDL code representing our problem. Each time a state variable
token is found in the DDL code, a new goal flaw is added to the set of flaws of the
current search space node. In case of a DDL disjunction, a disjunction flaw is added.
Finally, in case a preference is found, a new preference flaw is added.
The flaw which is more easy to describe is the preference flaw. Such flaws can be
managed simply by adding a branch on the search space and executing the preferred
DDL code on one of the nodes. Disjunction flaws can be managed in a similar way
by adding a branch on the search space and executing each DDL code snippet on each
child node.
For what concerns goal flaws, we have two possible resolution strategies:
compatibil-
ity application
and
merging
. The flaw solver will generate a branch on the search space
with several nodes representing all possible merges and a node for the compatibility
application. Compatibility application is managed simply executing DDL code repre-
senting the compatibility on the proper node and can add further goal flaws, disjunction
flaws as well as preference flaws to the current search space node.
Unification is only applicable to tokens that have the same proposition. For the sake
of compactness, we have introduced a new CSP constraint, that we call “multi-equals”,
defined as follows: given two sets of CSP variables
[
x
0
,...,x
n
]
and
[
y
0
,...,y
n
]
,the
multi-equals constraint is satisfied iff
[
x
0
=
y
0
,...,x
n
=
y
n
]
.
