[SOLVED] 程序代写 PowerPoint Presentation

PowerPoint Presentation

Numeric Planning

Copyright By PowCoder代写加微信 assignmentchef

Planning with Numbers
In the Scanalyzer application we saw:
(increase (total-cost) 3)
total-cost is a state variable
We can create others:
Can have effects on them (already seen)
Can condition on them in the preconditions of actions.

Numeric Variables in PDDL
(:predicates
(at ?obj – locatable ?loc – location)
(in ?obj1 – obj ?obj – truck)
(driving ?d – driver ?v – truck)
(link ?x ?y – location) (path ?x ?y – location)
(empty ?v – truck)
(:functions (time-to-walk ?l1 ?l2 – location)
(time-to-drive ?l1 ?l2 – location)

Numeric Preconditions
In principle, PDDL numeric preconditions comprise:
A comparison operator: >, >=, =, <=, <; with…A left- and right-hand side written using constants, the values of functions, and the operators +, -, *, /.(>= (fuel) (* 5 (distance ?from ?to)))
(<= (height truck) (height barrier1))(>= (number-of-widgets) 3)

Numeric Effects
In principle, PDDL numeric effects comprise:
A variable to update
How to update it: assign (=), increase (+=), decrease (-=)
A right-hand-side formula, as in preconditions
(decrease (fuel) (* 5 (distance ?from ?to)))
(increase (number-of-widgets) (capacity))
(assign (battery-charge b) (max-charge b))

Metric (Objective) Functions
Now we have numeric state variables we can define a metric function for the planner to optimise.
(minimize (total-cost))
(minimize (+ (fuel-used) (*2 (wages))))
These metrics refer to the values of the variables after the plan has finished executing, i.e in the goal state.
Defining a metric function is optional for a numeric planning problem.

Planning with Numbers
Search is straightforward these are discrete effects so:
We check numeric preconditions are satisfied before applying actions;
Update the values of the variables according to effects when we apply actions.

But so far we’ve not seen anything about Heuristic Guidance.

Metric relaxed planning graph, from Metric-FF (Hoffmann 2003).

“The Metric-FF Planning System: Translating “Ignoring Delete Lists” to Numeric State Variables” J. Hoffmann, JAIR Volume 20, 2003.

Ignoring Numeric ‘Delete’ Effects
(:action move
:parameters (?x – object ?from ?to – location)‏
:precondition (and
(at ?x ?from)‏
(>= (fuel ?x) 1)‏
:effect (and
(at ?x ?to)‏
(not (at ?x ?from))‏
(decrease (fuel ?x) 1)‏

Relaxing Numeric Effects
Is (decrease (fuel ?x) 1) a delete effect?
Conceptually yes, deletes a unit of fuel, needed to perform a move action;
Could ignore this in a relaxed problem.
What about (decrease (undelievered-packages) 1) where the goal is(= (undelivered-packages) 0)?
Not a delete effect: we want fewer undelivered packages;
Ignoring this would make the problem unsolvable.
How do we generalise relaxing numeric effects?
Maintain bounds: upper and lower bound on each numeric variable;
Use lower bound for preconditions v <= c and upper bound for v >= c.

Store = [1,1]

Site = [0,0]

Lorry = [0,0]

at Lorry Store

Load at store

Drive to site

Drive to store

Unload at store

Unload at site

Load at site

Load at store

Drive to site

Drive to store

Unload at store

Unload at site
Store = [-2,6]

Lorry = [-4,4]

Site = [-1,2]

at Lorry Site

at Lorry Store

Store = [0,2]

Lorry = [0,1]

Site = [0,0]

at Lorry Site

at Lorry Store

Store = [-1,4]

Lorry = [-2,2]

Site = [0,1]

at Lorry Site

at Lorry Store

Bounds propagation

Searching for Better Solutions
Once a solution has been found we can continue searching;
We can easily compute the cost of the plan so far, simply by evaluating the metric function in the current state.
Assuming the cost monotonically increases as we add actions to the plan we can prune states for which cost(S) > cost* where cost* is the best cost we have found so far;
Alternatively, we can just restart search, adding a goal (cost < cost*).Problem: heuristic is not necessarily providing guidance to find better solutions, it might keep sending us back to the same one./docProps/thumbnail.jpeg程序代写 CS代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]