Artificial Intelligence - CMPSC 162 - Lesson 3: State Space Search (Part 1) PDF

CMPSC 162: Artificial Intelligence Lesson 3 State Space Search (Part 1) WILBEN CHRISTIE R. PAGTACONAN Faculty Mariano Marcos State University College of Computing and Information Scien...

CMPSC 162: Artificial Intelligence Lesson 3 State Space Search (Part 1) WILBEN CHRISTIE R. PAGTACONAN Faculty Mariano Marcos State University College of Computing and Information Sciences Topic Objectives understand the state space representation; and gain familiarity with some common problems formulated as state space search problems. Try this out… Basic Notion of State Space Search Search is an important approach to general-purpose problem-solving. Search techniques are the most important and general AI programming technique. Basic Notion of State Space Search The basic idea: before actually doing something in order to solve some problem/puzzle, an intelligent agent will explore possibilities "in its head". Search = "(mental) exploration of possibilities" Examples 15-puzzle: The goal of an agent working on a 15-puzzle problem may be to reach a configuration which satisfies the condition that the top row has the tiles 1, 2 and 3. Examples The goal of an agent may be to navigate a maze and reach the HOME position. State Space Search Notations An initial state is the description of the starting configuration of the agent. An action or an operator takes the agent from one state to another state which is called a successor state. State Space Search Notations A plan is a sequence of actions. The cost of a plan is referred to as the path cost. The path cost may be the sum of the costs of the steps in the path. Search Problem Problem formulation means choosing a relevant set of states to consider, and a feasible set of operators for moving from one state to another. Search Problem Search is the process of considering various possible sequences of operators applied to the initial state and finding out a sequence which culminates in a goal state. Search Problem A search problem consists of the following: S: the full set of states s0 : the initial state A:S→S is a set of operators G is the set of final states. Note that G ⊆ S Search Problem Representation of search problems A search problem is represented using a directed graph. ✓ The states are represented as nodes. ✓ The allowed actions are represented as arcs. Searching process Do until a solution is found or the state space is exhausted. 1. Check the current state 2. Execute allowable actions to find the successor states. 3. Pick one of the new states. 4. Check if the new state is a solution state. If it is not, the new state becomes the current state and the process is repeated. Illustration of a search process Illustration of a search process The two successor states of the initial state are generated. Illustration of a search process The successors of these states are picked and their successors are generated. Illustration of a search process Successors of all these states are generated. Illustration of a search process The successors are generated. Illustration of a search process A goal state has been found! Pegs and Disks problem Problem: 3 pegs and 3 disks. Operators: one may move the topmost disk on any needle to the topmost position to any other needle Goal state: all the pegs are in the needle B. Pegs and Disks problem Goal State! Pegs and Disks problem Initial State (s0) Pegs and Disks problem Step 1: Move A → C Pegs and Disks problem Step 2: Move A → B Pegs and Disks problem Step 3: Move A → C Pegs and Disks problem Step 4: Move B→ A Pegs and Disks problem Step 5: Move C → B Pegs and Disks problem Step 6: Move A → B Pegs and Disks problem Step 7: Move C→ B Exercise 1. Problem: 4 disks problem (Tower of Hanoi). Initial state: all the pegs are in the needle A. Operators: one may move the topmost disk on any needle to the topmost position to any other needle Goal state: all the pegs are in the needle C. 2. Problem: 4 disks problem (Tower of Hanoi). Initial state: all the pegs are in the needle A. Operators: one may move the topmost disk on any needle to the topmost position to any other needle Goal state: all the pegs are in the needle B. Solution Exercise 1 Goal state: all the pegs are in the needle C. A B C Solution Exercise 2 Goal state: all the pegs are in the needle B. Step 1 A→C Step 9 C→B Step 2 A→B Step 10 C→A Step 3 C→B Step 11 B→A Step 4 A→C Step 12 C→B Step 5 B→A Step 13 A→C Step 6 B→C Step 14 A→B Step 7 A→C Step 15 C→B Step 8 A→B 8 queens problem States: Any arrangement of 8 queens on the board Initial state: All queens are at column 1 Successor function: Change the position of any one queen Goal test: 8 queens on the board, none are attacked 8 queens problem Initial State (s0) tic-tac-toe 8 puzzle 8 puzzle States: A state is a description of each of the eight tiles in each location that it can occupy. Operators/Action: The blank moves left, right, up or down Goal Test: The current state matches a certain state (e.g. one of the ones shown on previous slide) Path Cost: Each move of the blank costs 1 8 puzzle 8-puzzle partial state space N queens problem How do we formulate this in terms of a state space search problem? The problem formulation involves deciding the representation of the states, selecting the initial state representation, the description of the operators, and the successor states. N queens problem Wrong Solution! N queens problem Solution N queens problem formulation 1 States: Any arrangement of 0 to 8 queens on the board Initial state: 0 queens on the board Successor function: Add a queen in any square Goal test: 8 queens on the board, none are attacked N queens problem formulation 1 The initial state has 64 successors. Each of the states at the next level have 63 successors, and so on. Consider only those successors where no queen is attacking each other. The solutions are found at a depth of 8. N queens problem formulation 1 N queens problem formulation 2 States: Any arrangement of 8 queens on the board Initial state: All queens are at column 1 Successor function: Change the position of any one queen Goal test: 8 queens on the board, none are attacked N queens problem Initial State (s0) Water jug problem You are given two jugs, a 4-gallon one and a 3- gallon one, a pump which has unlimited water which you can use to fill the jug, and the ground on which water may be poured. Neither jug has any measuring markings on it. How can you get exactly 2 gallons of water in the 4-gallon jug? Water jug problem State Representation: represent a state of the problem as a tuple (x, y) where x represents the amount of water in the 4-gallon jug and y represents the amount of water in the 3-gallon jug. Note 0 ≤ x ≤ 4, and 0 ≤ y ≤ 3. Water jug problem Initial state: (0,0) Goal state = (2,y) where 0 ≤ y ≤ 3. Water jug problem Gals in 4-gal jug Gals in 3-gal jug Rule Applied 0 0 Fill 4 4 0 Pour 4 into 3 to fill 1 3 Empty 3 1 0 Pour all of 4 into 3 0 1 Fill 4 4 1 Pour into 3 2 3 Water jug problem Gals in 4-gal jug Gals in 3-gal jug Rule Applied 0 0 Fill 3 0 3 Pour 3 into 4 3 0 Fill 3 3 3 Pour 3 into 4 to fill 4 2 Empty 4 0 2 Pour all of 3 into 4 2 0 END OF LESSON 3 (Part 1)