Planning in Stochastic,Dynamic etc Environments.
Class Notes.
March 29th 2000.
Ullas
TCSP
Dr Rao continued from where he left off the discussion in the last class. On TCSP.
TCSPs can be broken into 3 types
Quantitative
Qualitative
A combination of both
The variables in TCSP are time points.
The constraints are represented as intervals eg Xi - Xj with bounds like
C12=3 <= X2 - X1 <=5
or
Alternately can be specified as
C12[3 5]
Unless said - time is assumed to be dense ie for eg. between 3.1 and 3.2 there is a possible infinite number of intervals or discretizations.
Dr Rao then explained that between any two variables (instantaneous) if a constant can be represented as a "single interval" then that is fine.
CSP becomes harder with disjunction coming. Without the disjunction TCSP becomes a simpler version called STP.
Constraints are - Unary or Binary.
The Unary constraints can be considered as Binary w.r.t the origin Xo.
Regarding constraint propagation, Dr Rao said, considering the constraints as set of possible values ends up reducing the constraints when constraint propagation is carried out. The representation as mentioned above then gives to the fragmented representation rather than reducing the constraints.
Thus a tighther constraint need not be small.Since a single dense interval can be broken into huge number of sub intervals, the summation of which is subsumed by original interval. Almost related to the discretization of time in the state-base planners aka midterm.
How to compute Path Consistency ?
For three points X1,X2,X3. The PC is calculated as under
C13 <- C13 Intersect (C12 compose C23)
C12,C23 and C13 are constraints between 1-2, 2-3 and 1-3 points directly.
When the above equation is iterated over, if we get to a point where the constriants dont change between iterations then we get Path Consistency.
Dr Rao said, Deciding Consistency is NP-complete, even if constraints have just 2-intervals.
Computing minimal network is NP-hard.
Calculating the Intersection
1 <= X2- X1 <= 3
2 <= X2- X1 <= 4
----------------
Max <= interval <= min
2 <= X2-X1 <= 3
Calculating the Compostion
1 <= X2- X1 <= 3
2 <= X2- X1 <= 4
----------------
3 <= X2-X1 <= 7
About STP, IXTET and RAX handle the temporal resource usages by making STP.
Rao : " One of the nicer ways to solve disjunction is to do some constraint propagation and then push into search space".
How to get STP?
Take one value of interval for every constraint and then check this one is consistent or not. The problem so modeled is called Simple Temporal Problem (STP).
In relation to refinement planning, Rao reminded that constraints have infinte candidate sets to begin with.
If there is no constraint then effectively [-infinity, infinity] is the constraint.
On a STP, when 2 intervals are composed we get 1 interval back. As also with the intersection.
And if the interval becomes "degenerate" then the plan is dead.
eg [-5,-7] is a degenerate interval.
STP can be represented as a weighted interval graph.
Each interval becomes 2 constraints
2 <= X2- X1 <= 4
becomes
X1-X2 <= -2
X2-X1 <= 4
and then a directed graph can be drawn from X1 to X2.
Inconsistency in a weighted graph is when it has a -ve cycle.
If the constraints are disjunctive then simple weighted graphs cannot be made. Then hyper graphs are the solution.