PowerPoint Presentation
Numeric Planning
Copyright By PowCoder代写 加微信 powcoder
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代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com