Planning II: Partial Order Planning

Planning II: Partial Order Planning

Planning II: Partial Order Planning Sections 11.5 - 11.6 Total v. Partial Order plans Total-order planner maintains a partial solution as a totally ordered list of steps found so far STRIPS

Partial-order planner only maintains partial order constraints on operators in the plan e.g., temporal constraints: S1 < S2 [S1 must come before S2, but not necessarily immediately before it] Principle of least commitment Dont make an ordering choice, unless required to do so Keep the ordering choice as general as possible

S1 < S2 v. S1 S2 Reduces the amount of backtracking needed dont waste time undoing steps Partial-order planners have this property of least commitment

situational planners dont Types of links Temporal: ordering constraint G1 < G2: G1 must occur before G2 graph Causal

Si c Sj Si achieves c for Sj in the effects list of Si is a literal c that is needed to satisfy part of the precondition for the operator Sj

records the purpose of a step in the plan Creating partial order plans Search through a space of (partial-order) plans Each node is a partial-order plan Each arc from a state (operator) consists in either adding a new step to the plan adding a temporal & causal constraint between existing steps

Situation-space planners, conversely, commit to an ordering when an operator is applied Initializing the algorithm Start node preconditions: none effects: positive literals defining the start state Finish node

preconditions: goal effects: none Initial plan Start ---------------> Finish Finishing the algorithm A solution is a complete and consistent plan

(see page 349, for the definitions of complete and consistent plan) Example Problem Interleaving v. non-interleaving planner Non-interleaving planner

all of the steps for a sub-goal occur atomically G1 ^ G2: either all of the steps for achieving G1 occur before G2, or all of the steps for achieving G1 occur after G2 STRIPS is non-interleaving because it uses a stack mechanism cannot solve the Sussman anomaly Flawed Plan Establishment

Solve an open/unsatisfied precondition p a precondition is not satisfied if it does not have a causal link to it Simple establishment Find an existing step T prior to S in which p is true (its in the Effects list of T) Step addition

Add a new plan step T that contains in its Effects list p Add both a causal & temporal link from T to S Declobbering = threat removal Threat

G2 requires an effect of G1 (there is a causal link between G1 & G2), but the effect of G3 is to undo the needed effect picture Thus, G3 cant occur between G2 & G3 it must occur either before G1 (promotion) add temporal link G3 < G1

or after G2 (demotion) add temporal link G2 < G3 Solving the Sussman anomaly Solving the Sussman anomaly I also used the slides from chapter 11 from Russells (and some from chapter 7 on situation calculus)

Recently Viewed Presentations

  • The Fall of Adam & Eve The Three

    The Fall of Adam & Eve The Three

    Now this is the way I interpret [Moses 3:16-17]: The Lord said to Adam, "Here is the Tree of the Knowledge of Good and Evil. If you want to stay here, then you cannot eat of that fruit. If you...
  • Community Helpers An Alphabet Electronic Book By Mr.

    Community Helpers An Alphabet Electronic Book By Mr.

    They also tell people ware to go. I Investigator An Investigator's job is to find information for the news so people know what is happening in the world they do what they can to help the world to become a...
  • Planning for slab-on-ground placement

    Planning for slab-on-ground placement

    Sand, gravel, crushed stone, slag, and similar materials that are mixed with cement and water to make concrete are called aggregates. Make up 60% to 75% of the absolute (solid) volume of concrete and represent 70% to 80% of its...
  • Japan: An Ancient and Modern Adventure Summer 2015

    Japan: An Ancient and Modern Adventure Summer 2015

    Fundraising: Car wash and odd jobs letter Passports: Valid through Dec 2015 Upcoming dates/ meetings Questions/concerns Parent traveler meeting (Last 10 min) All information and slides are available at globalxpeditions.weebly.com Agenda Albrecht Stacy Albrecht Jason Benson Laura Garnett Jill Haley...
  • Genetic variation - Groby Bio Page

    Genetic variation - Groby Bio Page

    Some phenotypic variation is caused only by the environment and not passed on in genes: Speaking with a regional dialect. Loss of limbs or scars. Some phenotypic variation is caused by the environment interacting with genes: Diet in humans. Chlorosis...
  • Management of Post-transplant hyperlipidemia B. Gisella Carranza Leon,

    Management of Post-transplant hyperlipidemia B. Gisella Carranza Leon,

    Epanova: 1 g capsule contains ~ 850 mg of polyunsaturated fatty acids, including multiple omega-3 fatty acids (EPA and DHA being the most abundant). Lovaza: 1 g capsule contains EPA (~ 465 mg) and DHA (~375 mg) Vascepa: 1 g...
  • AS and A Level Chemistry A, Powerpoint, The Arrhenius equation

    AS and A Level Chemistry A, Powerpoint, The Arrhenius equation

    The Arrhenius equation Exponential form Exponential factor, e-Ea/RT: proportion of molecules that have sufficient energy for a reaction to take place Pre-exponential term (frequency factor), A, accounts for the frequency of collisions with the correct orientation R = gas constant...
  • Anne Sullivan Macy - Ms. Culliton&#x27;s Pages

    Anne Sullivan Macy - Ms. Culliton's Pages

    Anne Sullivan Macy. Sullivan left Tewksbury to attend the Perkins School for the Blind in 1880, and underwent surgery to help improve her limited vision. Still, Sullivan faced great challenges while at Perkins. She had never been to school before...