PowerPoint Presentation
Planning with Continuous Linear Change: COLIN General Approach
Copyright By PowCoder代写 加微信 powcoder
Generalising This
For each (snap) action, Ai, in the (partial) plan create the following LP variables for each numeric variable in the problem:
vi: the value of that variable immediately before Ai is executed;
v’i: the value v immediately after Ai is executed.
δvi: the rate of change active on v after Ai is executed.
Create a single LP variable ti to represent the time at which Ai will be executed.
Constraints
Initial values:
v0 = initial state value of v;
Temporal Constraints:
ti >= ti-1 + ε
tj – ti <= max_dur A (where tj is the end of the action starting at ti)
tj – ti >= min_dur A (where tj is the end of the action starting at ti)
Continuous Change
vi+1 = v’i + δvi (ti+1 – ti)
Discrete Change:
v’i = vi + w . vi;
e.g : v’i = vi + 2 ui – 3wi
Constraints Continued
Preconditions: constraints over vi:
w . vi {>=,=,<=} c;
e.g. 2wi -3ui <= 4;
Invariants of A, must be checked before and after every step between the start (i) and end (j) of A.
w . v’i {>=,=,<=} c;
w . vi+1 {>=,=,<=} c;
w . v’i+1 {>=,=,<=} c;
w . vj {>=,=,<=} c;
Linearity Assumption
δvi is a constant that we can calculate whilst making the LP by looking at the continuous numeric effects of actions:
All of the form δvi +=/-= c
What if δvi was a function of the variables: e.g. δvi = 2w – u?
vi+1 = v’i + δvi (ti+1 – ti)
Invariant checking:
We only check the condition at the start and end of each interval (i.e. after one action is applied, and before the next is.
Objective Function
LPs have an objective function:
Want to minimise makespan?
Make a variable tnow and order it after all other steps in the plan:
tnow -ti >= ε
Now set the LP Objective to minimize tnow
Want to minimise some cost function other than makespan (e.g. a function of the final values of variables?
Write the objective as a function of tnow for the final action in the plan so far:
E.g minimise 3vnow + 2wnow – unow
LP will find a solution that is optimal for this plan.
Action Applicability
In general in discrete numeric planning we know the values of the variables:
Value in initial state specified;
Effects update value by a known amount: v = v + 2u – 3w
Compute the new value in the current state and check whether preconditions are satisfied.
What if there is continuous numeric change active in a state?
The value of the a variables depends on how much time we allow to elapse.
In our example if we start the route the value of battery is:
50 – 40 * time elapsed.
We don’t know the exact value of battery but we know it’s in the range [50,0] depending on what time we apply the next action.
Using the LP to find general it’s not easy once a lot of change has happened to know the bounds on a given variable in a state;
We can however, use the same LP to calculate this with a small modification:
A variable tnow representing the time of the next action being applied.
Add a variable vnow for each variable, representing its value at tnow
For each variable set the objective function to:
Maximise vnow to give the upper bound on v.
Minimise vnow to give the lower bound on v.
Now take the upper (lower) bound to satisfy all >= (<=) conditions.
Is the action guaranteed to be applicable? 2v + w >= 5?
You’re Solving a lot of LPs isn’t that Expensive?
Short answer no: they’re easy ones.
Heuristic computation is notoriously expensive:
An analysis showed that FF spends ~80% of its time evaluating the heuristic.
So what about COLIN:
Empirically using an STP scheduler scheduling accounts for on average less than 5% of state evaluation time.
For CLP and CPLEX (LP solvers) the figures are 13% and 18% respectively.
So better than calculating the heuristic.
/docProps/thumbnail.jpeg
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com