GraphPlan and SATPlan in AI Planning

GraphPlan and SATPlan are AI planning techniques that utilize graph structures to encode constraints and search for valid plans efficiently. GraphPlan involves constructing a planning graph with layers of nodes representing propositions and actions, while SATPlan focuses on propositional representations and STRIPS operators. These methods are sound, complete, and suitable for finding shortest plans in planning problems with discrete variables and exponential complexity.

• GraphPlan
• SATPlan
• AI planning
• Planning graph
• Propositional representation

gzul Follow

Uploaded on Nov 17, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Graphplan/ SATPlan Chapter 11.4-11.7 Some material adapted from slides by Jean-Claude Latombe / Lise Getoor

2. GraphPlan: Basic idea Construct a graph that encodes constraints on possible plans Use this planning graph to constrain search for a valid plan Planning graph can be built for each problem in a relatively short time

3. Planning graph Directed, leveled graph with alternating layers of nodes Odd layers ( state levels ) represent candidate propositions that could possibly hold at step i Even layers ( action levels ) represent candidate actions that could possibly be executed at step i, including maintenance actions [do nothing] Arcs represent preconditions, adds and deletes We can only execute one real action at any step, but the data structure keeps track of all actions and states that are possible

4. GraphPlan properties STRIPS operators: conjunctive preconditions, no conditional or universal effects, no negations Planning problem must be convertible to propositional representation NO continuous variables, temporal constraints, Problem size grows exponentially Finds shortest plans (by some definition) Sound, complete, and will terminate with failure if there is no plan

5. What actions and what literals? Add an action in level Ai if all of its preconditions are present in level Si Add a literal in level Si if it is the effect of some action in level Ai-1(including no-ops) Level S0 has all of the literals from the initial state

6. Simple domain: Rocket to Mars Literals: at X Y fuel R in X R Actions: load X L unload X L move X Y Graph representation: Solid black lines: preconditions/effects Dotted red lines: negated preconditions/effects X is at location Y rocket R has fuel X is in rocket R load X (onto R) at location L (X and R must be at L) unload X (from R) at location L (R must be at L) move rocket R from X to Y (R must be at L and have fuel)

7. (define (domain rockets) (:requirements :strips) (:predicates (cargo ?x) (rocket ?x) (location ?x) (at ?t ?l) (in ?c ?r) (fuel ?r)) (:action load :parameters (?c ?r ?l) :precondition (and (cargo ?c) (rocket ?r) (location ?l) (at ?c ?l) (at ?r ?l)) :effect (and (not (at ?c ?l)) (in ?c ?r))) (:action unload :parameters (?c ?r ?l) :precondition (and (cargo ?c) (rocket ?r) (location ?l) (in ?c ?r) (at ?r ?l)) :effect (and (not (in ?c ?r)) (at ?c ?l))) (:action fly :parameters (?r ?dep ?dst) :precondition (and (rocket ?r) (location ?dep) (location ?dst) (at ?r ?dep) (fuel ?r)) :effect (and (not (at ?r ?dep)) (at ?r ?dst) (not (fuel ?r)))))

8. (define (problem rrt5) (:domain rockets) (:requirements :strips) (:objects venus earth mars moon saturn x1 x2 x3 x4 x5 anna beth carol diane emma fiona) (:init (location venus) (location earth) (location mars) (location moon) (location saturn) (rocket x1) (rocket x2) (rocket x3) (rocket x4) (rocket x5) (cargo anna) (cargo beth) (cargo carol) (cargo diane) (cargo emma) (cargo fiona) (at x1 venus) (at x2 earth) (at x3 mars) (at x4 moon) (at x5 saturn) (at anna venus) (at beth venus) (at carol earth) (at diane mars) (at emma moon) (at fiona saturn) (fuel x1) (fuel x2) (fuel x3) (fuel x4) (fuel x5)) (:goal (and (at anna earth) (at beth saturn) (at carol mars) (at diane moon) (at emma saturn) (at fiona earth))))

9. Example planning graph load A L load A L at A L at A L at A L at B L load B L load B L at B L at B L at R L at R L at R L move L P move L P fuel R fuel R at A P fuel R unload A P in A R in A R at B P unload B P move P L in B R in B R at R P at R P States S0 Actions A0 Actions A1 States S2 Actions A2 States S3 (Goals!) States S1

10. BlackBox Planner STRIPS-based plan representation Planning graph CNF representation CSP/SAT solver CSP solution Plan