Unit II AIR - Problem Decomposition and Planning

Views:
 
Category: Education
     
 

Presentation Description

Problem Decomposition: Goal Trees, Rule Based Systems, Rule Based Expert Systems. Planning: STRIPS, Forward and Backward State Space Planning, Goal Stack Planning, Plan Space Planning, A Unified Framework For Planning. Constraint Satisfaction : N-Queens, Constraint Propagation, Scene Labeling, Higher order and Directional Consistencies, Backtracking and Look ahead Strategies.

Comments

Presentation Transcript

slide 1:

BE Computer Engineering Unit II Problem Decomposition and Planning 1

slide 2:

Outline  Problem Decomposition:  Goal Trees Rule Based Systems Rule Based Expert Systems.  Planning:  STRIPS Forward and Backward State Space Planning Goal Stack Planning Plan Space Planning  Constraint Satisfaction 2

slide 3:

Goal Trees An AND-OR Tree. And Arcs represent subproblems to be solved individually. 3

slide 4:

Rule Based Systems  Rule based systems have been used in general to decompose a problem and address it in parts.  Pattern  Action  Dinner  Pizza Hut | KFC 4

slide 5:

Reasoning  Backward Reasoning: If the goal is to have dinner then it could be archived by going to one of the two restaurants. This form of reasoning is also called as backward reasoning because the reasoning is done backwards from the goal.  Forward reasoning: In this rules are triggered by patterns in the data. 5

slide 6:

Planning  The goal of action planning is to choose actions and ordering relations among these actions to achieve specified goals  Search-based problem solving applied to 8-puzzle was one example of planning but our description of this problem used specific data structures and functions  Here we will develop a non-specific logic-based language to represent knowledge about actions states and goals and we will study how search algorithms can exploit this representation 6

slide 7:

STRIPS Language through Examples 7

slide 8:

Planning-Planner  In classical planning reasoning about actions involves simulation of changes in mental model that the agent has.  The agent peers into the future to examine the different possibilities and select the desirable course of action projection in future. The planner searches through the possible combination of action to find the plan that will work.  Alternative approach is to use agents experience. If agent has memory it can reuse a plan the worked earlier or reuse the problem solving experience to solve problems. 8

slide 9:

STRIPS  In artificial intelligence STRIPS Stanford Research Institute Problem Solver is an automated planner developed by Richard Fikes and Nils Nilsson in 1971.  The same name was later used to refer to the formal language of the inputs to this planner.  This language is the base for most of the languages for expressing automated planning problem instances in use today such languages are commonly known as action languages. 9

slide 10:

• A robot hand can move blocks on a table • The hand cannot hold more than one block at a time • No two blocks can fit directly on the same block • The table is arbitrarily large A B C TABLE Blocks-World Example • Precondition: The assertions needed to be true for the operator to be applicable. • Add List: The assertions that become true as a consequence of the operator being applied. • Delete List: The assertions that are no longer true as a consequence of the operator being applied. 22

slide 11:

State BlockA  BlockB  BlockC  OnATABLE  OnBTABLE  OnCA  ClearB  ClearC  Handempty A B C TABLE 23

slide 12:

Goal A B C OnATABLE  OnBA  OnCB  ClearC 24

slide 13:

A B C OnATABLE  OnCB A B C Goal 25

slide 14:

Unstackxy P Handempty  Blockx  Blocky  Clearx  Onxy D Handempty Clearx Onxy A Holdingx Cleary Goal 26

slide 15:

Unstackxy P Handempty  Blockx  Blocky  Clearx  Onxy D Handempty Clearx Onxy A Holdingx Cleary A B C BlockA  BlockB  BlockC  OnATABLE  OnBTABLE  OnCA  ClearB  ClearC  Handempty UnstackCA P Handempty  BlockC  BlockA  ClearC  OnCA D Handempty ClearC OnCA A HoldingC ClearA Action 27

slide 16:

C Unstackxy P Handempty  Blockx  Blocky  Clearx  Onxy D Handempty Clearx Onxy A Holdingx Cleary BlockA  BlockB  BlockC  OnATABLE  OnBTABLE  OnCA  ClearB  ClearC  Handempty  HoldingC  ClearA UnstackCA P Handempty  BlockC  BlockA  ClearC  OnCA D Handempty ClearC OnCA A HoldingC ClearA C A B Action 28

slide 17:

BlockA  BlockB  BlockC  OnATABLE  OnBTABLE  OnCA  ClearB  ClearC  Handempty  HoldingC  ClearA UnstackCA P Handempty  BlockC  BlockA  ClearC  OnCA D Handempty ClearC OnCA A HoldingC ClearA C A B Unstackxy P Handempty  Blockx  Blocky  Clearx  Onxy D Handempty Clearx Onxy A Holdingx Cleary Action 29

slide 18:

Unstackxy P Handempty  Blockx  Blocky  Clearx  Onxy D Handempty Clearx Onxy A Holdingx Cleary Stackxy P Holdingx  Blockx  Blocky  Cleary D Cleary Holdingx A Onxy Clearx Handempty Pickupx P Handempty  Blockx  Clearx  OnxTable D Handempty Clearx OnxTable A Holdingx Putdownx P Holdingx  Blockx D Holdingx A OnxTable Clearx Handempty All Action 30

slide 19:

Unstackxy P Handempty  Blockx  Blocky  Clearx  Onxy D Handempty Clearx Onxy A Holdingx Cleary Stackxy P Holdingx  Blockx  Blocky  Cleary D Cleary Holdingx A Onxy Clearx Handempty Pickupx P Handempty  Blockx  Clearx  OnxTable D Handempty Clearx OnxTABLE A Holdingx Putdownx P Holdingx  Blockx D Holdingx A OnxTABLE Clearx Handempty A block can always fit on the table 31

slide 20:

InitAtC1 SFO  AtC2JFK  AtP1SFO  AtP2JFK  CargoC1  CargoC2  PlaneP1  PlaneP2  AirportJFK  AirportSFO GoalAtC1JFK  AtC2SFO ActionLoadcpa PRECOND: Atca Atpa Cargoc Planep Airporta EFFECT: ¬Atca Incp ActionUnloadcpa PRECOND: Incp Atpa Cargoc Planep Airporta EFFECT: Atca  ¬Incp ActionFlypfromto PRECOND: Atpfrom Planep Airportfrom Airportto EFFECT: ¬ Atpfrom  Atpto LoadC1P1SFO FlyP1SFOJFK LoadC2P2JFK FlyP2JFKSFO Example: Air cargo transport 32

slide 21:

Planning Methods 33

slide 22:

PLANNING WITH STATE-SPACE SEARCH • The most straightforward approach is to use state-space search. Because the descriptions of actions in a planning problem specify both preconditions and effects • It is possible to search in either direction: either forward from the initial state or backward from the goal as shown in Figure next slide. • We can also use the explicit action and goal representations to derive effective heuristics automatically. 34

slide 23:

PLANNING WITH STATE-SPACE SEARCH • Both forward and backward search possible • Progression planners • forward state-space search • Consider the effect of all possible actions in a given state • Regression planners • backward state-space search • To achieve a goal what must have been true in the previous state. 35

slide 24:

Two approaches to searching for a plan. a Forward progression state-space search starting in the initial state and using the problems actions to search forward for the goal state. b Backward regression state-space search: a belief-state search starting at the goal states and using the inverse of the actions to search backward for the initial state. Progression and Regression 36

slide 25:

Progression algorithm • Formulation as state-space search problem: • Initial state initial state of the planning problem • Literals not appearing are false • Actions those whose preconditions are satisfied • Add positive effects delete negative • Goal test does the state satisfy the goal • Step cost each action costs 1 • No functions … any graph search that is complete is a complete planning algorithm. • E.g. A • Inefficient: • irrelevant action problem • good heuristic required for efficient search 37

slide 26:

Forward State Space Planning • Consider an air cargo problem with 10 airports where each airport has 5 planes and 20 pieces of cargo. • The goal is to move all the cargo at airport A to airport B. There is a simple solution to the problem: load the 20 pieces of cargo into one of the planes at A fly the plane to B and unload the cargo. • But finding the solution can be difficult because the average branching factor is huge: each of the 50 planes can fly to 9 other airports and each of the 200 packages can be either unloaded if it is loaded or loaded into any plane at its airport if it is unloaded. • It is clear that a very accurate heuristic will be needed to make this kind of search efficient. We will discuss some possible heuristics after looking at backward search. 38

slide 27:

Regression algorithm • How to determine predecessors • What are the states from which applying a given action leads to the goal • Goal state AtC1 B  AtC2 B  …  AtC20 B • Relevant action for first conjunct: UnloadC1pB • Works only if pre-conditions are satisfied. • Previous state InC1 p  Atp B  AtC2 B  …  AtC20 B • Subgoal AtC1B should not be present in this state. • Main advantage: only relevant actions are considered. 39

slide 28:

Forward State Space Planning From ref book 44

slide 29:

OnBA  OnCB A B C Initial state Backward Planning 45

slide 30:

OnBA  OnCB StackCB OnBA  HoldingC  ClearB ClearC  OnCTable  ClearA  Handempty  ClearB  OnBTable ClearC  OnCTABLE  HoldingB  ClearA StackBA PickupB PutdownC ClearA  ClearB  OnBTable  HoldingC UnstackCA ClearB  OnBTable  ClearC  Handempty  OnCA PickupC OnBA  ClearB  Handempty  ClearC  OnCTable A B C Initial state Backward Planning 46

slide 31:

OnBA  OnCB StackCB OnBA  HoldingC  ClearB ClearC  OnCTable  ClearA  Handempty  ClearB  OnBTable ClearC  OnCTABLE  HoldingB  ClearA StackBA PickupB PutdownC ClearA  ClearB  OnBTable  HoldingC UnstackCA ClearB  OnBTable  ClearC  Handempty  OnCA PickupC OnBA  ClearB  Handempty  ClearC  OnCTable A B C Initial state Backward Planning 47

slide 32:

Backward State Space Planning • One way to take the goal state into account is to start searching backwards from the goal. From ref book 48

slide 33:

• Backward planning searches a space of goals from the original goal of the problem to a goal that is satisfied in the initial state • There are often much fewer actions relevant to a goal than there are actions applicable to a state  smaller branching factor than in forward planning • The lengths of the solution paths are the same Search Tree 50

slide 34:

• Push the original goal to the stack. Repeat until the stack is empty: • GSP works by pushing the goal description onto the stack. • It pushes both the conjunct as well as each of the individual goal predicates separately. The algorithm pops the element on the top of stack. • If it is goal predicate that is true in the current state then nothing is done and next element is popped from the stack. • If it is goal predicate that is not true in the current state a relevant action is pushed onto the stack followed by the preconditions • The precondition on the top of the stack becomes the next subgoal to be addressed recursively. Goal Stack Planning 51

slide 35:

Goal Stack Planning 52

slide 36:

Goal Stack Planning 1. UNSTACKC A 2. PUTDOWNC 3. PICKUPA 4. STACKA B 5. UNSTACKA B 6. PUTDOWNA 7. PICKUPB 8. STACKB C 9. PICKUPA 10. STACKA B Goal Stack Planning 53

slide 37:

Goal Stack Planning 54

slide 38:

• Any planning algorithm that can place two actions into a plan without which comes first is a PO plan. Plan Space Planning 55

slide 39:

Constraint Satisfaction Problems 56

slide 40:

• Constraint satisfaction problems CSPs are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. • CSPs are the subject of intense research in both artificial intelligence and operations research. • CSPs often exhibit high complexity requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint satisfaction problems CSPs 57

slide 41:

Constraint satisfaction problems CSPs • CSP: A constraint satisfaction problem is defined as a three V D C Goal test is a set of constraints • Standard search problem: State of problem is defined by an assignment of values to some or all variables. Assignment that does not violate any constraint is called consistent assignment. 58

slide 42:

Constraint satisfaction problems CSPs 59

slide 43:

Constraint satisfaction problems CSPs 60

slide 44:

Constraint satisfaction problems CSPs 61

slide 45:

Constraint satisfaction problems CSPs 62

slide 46:

Constraint satisfaction problems CSPs 63

slide 47:

Constraint satisfaction problems CSPs 64

slide 48:

Constraint satisfaction problems CSPs 65

slide 49:

Constraint satisfaction problems CSPs 66

slide 50:

Constraint satisfaction problems CSPs 67

slide 51:

Constraint satisfaction problems CSPs 68

slide 52:

Constraint satisfaction problems CSPs 69

slide 53:

Constraint satisfaction problems CSPs 70

slide 54:

Example: Map-Coloring Variables WA NT Q NSW V SA T Domains D i redgreenblue Constraints: adjacent regions must have different colors e.g. WA ≠ NT or WANT in redgreenredbluegreenred greenblueblueredbluegreen 71

slide 55:

Example: Map-Coloring Solutions are complete and consistent assignments e.g. WA red NT greenQ redNSW greenV redSA blueT green 72

slide 56:

Backtracking example 74

slide 57:

Backtracking example 75

slide 58:

Backtracking example 76

slide 59:

Backtracking example 77

slide 60:

Constraint propagation Forward checking propagates information from assigned to unassigned variables but doesnt provide early detection for all failures: NT and SA cannot both be blue Constraint propagation repeatedly enforces constraints locally 78

slide 61:

Arc consistency Simplest form of propagation makes each arc consistent X Y is consistent iff for every value x of X there is some allowed y of Y 79

slide 62:

Arc consistency Simplest form of propagation makes each arc consistent X Y is consistent iff for every value x of X there is some allowed y of Y 80

slide 63:

Arc consistency Simplest form of propagation makes each arc consistent X Y is consistent iff for every value x of X there is some allowed y If X loses a value neighbors of X need to be rechecked 81

authorStream Live Help