[SOLVED] CS PowerPoint Presentation

PowerPoint Presentation

Planning with Continuous Linear Change: COLIN General Approach

Copyright By Assignmentchef assignmentchef

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;
vi: 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 = vi + vi (ti+1 ti)
Discrete Change:
vi = vi + w . vi;
e.g : vi = 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 . vi {>=,=,<=} c;w . vi+1 {>=,=,<=} c;w . vi+1 {>=,=,<=} c;w . vj {>=,=,<=} c;Linearity Assumptionviis a constant that we can calculate whilst making the LP by looking at the continuous numeric effects of actions:All of the form vi +=/-= cWhat if vi was a function of the variables: e.g. vi = 2w u?vi+1 = vi + 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 FunctionLPs 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 dont know the exact value of battery but we know its in the range [50,0] depending on what time we apply the next action.

Using the LP to find general its 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?

Youre Solving a lot of LPs isnt that Expensive?
Short answer no: theyre 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: assignmentchef QQ: 1823890830 Email: [email protected]