Classical Planning in Artificial Intelligence

classical planning problem and classical conversations tutor planning sheets and classical approach of strategic planning and classical planning machine learning
JaydenGibbs Profile Pic
JaydenGibbs,United States,Teacher
Published Date:19-07-2017
Your Website URL(Optional)
Classical Planning Problems: Representation Languages – 20173 3 History: 1959  The language of Artificial Intelligence was/is logic  First-order, second-order, modal, …  1959: General Problem Solver (Newell, Shaw, Simon) jonkvi jonkvida da4 4 History: 1969  1969: Planner explicitly built on Theorem Proving (Green) jonkvi jonkvida da5 5 Basis in Logic  Full theorem proving generally proved impractical for planning  Different techniques were found  Foundations in logical languages remained ▪ Languages use predicates, atoms, literals, formulas ▪ We define states, actions, … relative to these ▪ Allows us to specify an STS at a higher level Formal representation using a first-order language: "Classical Representation" (from the book) "The simplest representation that is (more or less) reasonable to use for modeling" jonkvi jonkvida da6 6 Running Example  Running example (from the book): Dock Worker Robots Containers shipped Cranes move containers in and out of a harbor between ”piles” and robotic trucks jonkvi jonkvida da8 8 Objects 1: Intro  We are interested in objects in the world  Buildings, cards, aircraft, people, trucks, pieces of sheet metal, …  Must be a finite set Modeling: Which objects exist and are relevant for the problem? jonkvi jonkvida da9 9 Objects 2: Dock Worker Robots  Dock Worker Robots A crane moves containers between piles and robots A robot is an automated A container can be truck moving containers stacked, picked up, between locations loaded onto robots loc2 c2 p2 c3 c1 r1 p1 loc1 We can skip: A pile is a stack of containers – Hooks A location is an area that can at the bottom, there is a pallet be reached by a single crane Wheels Rotation angles Can contain several piles, at most one robot. Drivers – not relevant for this problem jonkvi jonkvida da10 10 Objects 3: Classical Representation  Classical representation:  We are constructing a first-order language𝐿  Every object is modeled as a constant  Add a constant symbol ("object name") for each object: 𝐿 contains loc2 c2 p2 c3 c1 r1 p1 loc1 jonkvi jonkvida da11 11 Objects 4: For all non-boolean values  All non-boolean constant values are modeled in the same way  Colors: red, green, blue  … jonkvi jonkvida da13 13 Internal Structure?  An STS only assumes there are states  What is a state? The STS doesn’t care  Its definitions don’t depend on what 𝑠 “represents” or “means” ′ ▪ Can execute𝑎 in 𝑠 if 𝛾𝑠,𝑎=𝑠  We (and planners) need more structure  "state 𝑠 "  23862497124985 " " jonkvi jonkvida da14 14 Predicates  First-order language: Start with a set of predicates  Properties of the world ▪  Properties of single objects ▪  Relations between objects ▪  Relations between 2 objects ▪  Non-boolean properties are "relations between constants" ▪ Essential: Determine what is relevant for the problem and objective jonkvi jonkvida da15 15 Predicates for DWR  All predicates for DWR, and their intended meaning: "Fixed/Rigid" ▪ (can't change) "Dynamic" (modified by actions) jonkvi jonkvida da16 16 Predicates, Terms, Atoms, Ground Atoms  Terminology:  Term: Constant symbol or variable ▪ ▪  Atom: Predicate symbol applied to the intended number of terms ▪ ▪ ▪ ▪  Ground atom: Atom without variables (only constants)  Plain first-order logic has no object types  Allows “strange” atoms: ▪ ▪ ▪ jonkvi jonkvida da17 17 States 1: Factored, Internally Structured  A state defines which ground atoms are true/false in the world We can compute differences between states Structure is essential We will see later how planners make use of structured states… jonkvi jonkvida da18 18 States 2: First-order Representation  Efficient specification / storage of a single state:  Specify which facts are true ▪ All other facts have to be false – what else would they be?  A classical state is a set of all ground atoms that are true ▪ 1 2 3 ∈ Why not store all ground atoms ∉ that are false instead? jonkvi jonkvida da19 19 States 3: State Set  "A state is a set of all ground atoms that are true"…  Set of states in the STS: 𝑑𝑛𝑔𝑟𝑜𝑢𝑠𝑎𝑡𝑜𝑚 ▪𝑆=2 (powerset: all sets of ground atoms)  Number of states: 𝑑𝑛𝑟𝑜𝑢𝑔𝑠𝑎𝑡𝑜𝑚 ▪𝑆=2= jonkvi jonkvida da20 20 States 4: Initial State  The STS assumes a single initial state𝑠 0 Complete relative to the model:  Complete information about We must know everything the current state of the world about those predicates and objects we have specified...  State = set of true facts… 𝑠=attachedp1,loc1,inc1,p1,onc1,pallet,onc3,c1,… 0 loc2 c2 c3 p2 c1 r1 loc1 p1 jonkvi jonkvida da