[SOLVED] CS代写 PowerPoint Presentation

PowerPoint Presentation

Planning with Continuous Linear Change: COLIN General Approach

Copyright By PowCoder代写加微信 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;
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δviis 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 = 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 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 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代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]