Chapter 2 - General Representation of AI problems.pdf

Department of Computer Sciences College of Computers & Information Technology 501481-3 Artificial Intelligence Chapter 2: General Representation of AI problems 1 ...

Department of Computer Sciences College of Computers & Information Technology 501481-3 Artificial Intelligence Chapter 2: General Representation of AI problems 1  AI Problem Assume: P is an AI problem. P has an initial configuration called the initial state (s ). The solution of P is called the goal state (G). To find a solution to the problem P: – We will start from the start state s. – Apply an action to s to get a new state s1. – Apply an action to s1 to get a new state s2. – Keep applying actions until we reach the goal G. Artificial Intelligence 2 12:05 AM  Problem Solving in AI Problem solving is a technique to reach the goal G from the start state s. A search space is all possible actions applied to a state si to get a new state sj for all states si and sj. Artificial Intelligence 3 12:05 AM  //Problem Solving in AI Problem solving can be converted into a graph where nodes are the problem states and edges are actions. All the nodes in the graph are called the search space. Search space is defined as all the possible states of the problem. Artificial Intelligence 4 12:05 AM  General Example Assume I want to go from city Arad to city Bucharest. This defines problem P: – The initial state is city Arad, The goal state is city Bucharest. – Roads will connect between different cities. Problem P can be converted into a graph. 5  /Representation of search problems Graphs and Trees A search problem is represented using a: Directed graph : – The states are represented as nodes. – The allowed actions are represented as arcs. Undirected graph : – Edges does not imply directions. Weighted graph: – Edges may have weight (cost). Lecture 3: introduction to state space search Artificial Intelligence 6  Representation of search problems Graph and tree A path is a sequence of edges. – Example :p=(A,D),(D,E),(E,F),(F,B) or – Or a sequence of nodes p=A,D,E,F,F Loop (cycle) may exist in a graph. – Edges lead back to the original node. – l=(A,D),(D,E),(E,F),(F,B),(B,A) or l=A,D,E,F,F,A Graph is connected if for any pair of nodes there is a path between them. Lecture 3: introduction to state space search Artificial Intelligence 7  Representation of search problems Graph and tree Lecture 3: introduction to state space search Artificial Intelligence 8  Other Graph representation Techniques: Adjacency Matrix ❑ Adjacency matrix A( N x N matrix)-undirected graph ✓ A[i, j]=1: an edge exist between nodes i and j. ✓ A[i, j]=0: no edge exist between nodes i and j. ✓ Row represents source, Column represents destination. Lecture 3: introduction to state space search Artificial Intelligence 9  Other Graph representation Techniques: Adjacency Matrix ❑ Adjacency matrix for a directed graph ❑ Rows identify source nodes. ❑ Columns identify destination nodes. Lecture 3: introduction to state space search Artificial Intelligence 10  Example-1 For the problem of going from city Arad to city Bucharest, we have the following setting: S = set of all cities in the problem. – S = {Arad, Zerind, Sibiu, …}, 10 cities Initial state s = Arad, Goal state G = Bucharest. Operations O = set of all roads connecting the cities. 11  Representing the Search Space Basic search problem could be stated as: – Given [S, s, O, G] where: S is the set of states. s is the initial state. O is the set of state transition operators (actions). G is the set of goal state(s). – Purpose: to find a sequence of state transitions heading from s to a goal state G. Artificial Intelligence 12 12:05 AM  Example-2 Search in a Maze Assume that there a robot that need to move in the shown maze. Define this AI problem by representing: [S, s, O, G], and drawing the search space.  Representing the Search Space Initial state s =A. Goal G= {G,J} State space S = set of locations = {A,B,C,D,E,F,G,H,I,J} Operator O= {(A, left, B), (A, down, C), (A, right, D), (B, left, E), (B, down, F), (B, right, A), (E, right, B), (E, down, I), (D, left, A), (D, down, G), (D, right, H), (H, left, D), (H, down, J), (J, up, H), (G, up, D), (C, up, A), (F, up, B), (I, up, E)} Artificial Intelligence 14 12:05 AM Representing the Search Space s A B C D E F G H I J End of Solution Artificial Intelligence 15 12:05 AM  Example-3 Search in a Puzzle Space We have a number of disks and 3-pegs. Goal: move disks to peg 3 such that they are in increasing order. Constraints: Larger disk can not sit on a smaller disk & You cannot move a disk that has another disk above it. Define this AI problem by representing: [S, s, O, G], and drawing the search space. 1 2 3 1 2 3 C C B B A A Initial State s Goal State G Artificial Intelligence 16 12:05 AM  Representing the Search Space Constraints: – Larger disk can not sit on a smaller disk. – Cannot move a disk that has another disk above it. Solution: – Move disk C to peg 3. – Move disk B to peg 2. – Move disk C to peg 2 on top of disk B. – Move disk A to peg 3. – Move disk C to peg 1 – Move disk B to peg 3 on top of A. – Move disk C to peg 3 on top of B. Artificial Intelligence 17 12:05 AM  Representing the Search Space State space S: (Peg1, Peg2, Peg3) – Peg1: list of disks (bottom-top). – Peg2: list of disks (bottom-top). – Peg3: list of disks (bottom-top). Initial state s =((A,B,C), (),()). Goal state G=((), (), (A,B,C)). Operator: move(Disk, From, To) – Disk is disk name – From is peg number – To is peg number. Artificial Intelligence 18 12:05 AM  Search in a Puzzle Space State space S s move(c,1,2) move(c,1,3) S1 =((A,B), (C),()) S =((A,B,C), (),()) S2 =((A,B), (),(C)) move(c,2,3) s1 move(b,1,3) move(c,3,2) s2 move(b,1,2) Artificial Intelligence 19 12:05 AM  Search in a Puzzle Space S G S =((A,B), (),()) G =((), (),(A,B)) Think of the solution as an exercise!  Example-3 Search in an Adversarial Game Space: Missionaries and Cannibals Initially, 3 missionaries and 3 cannibals are at one side of a river, along with a boat that can hold one, or two people. Goal: all people need to go to the other side of the river. Constraint: – Group of cannibals cannot outnumber the group of missionaries. – No more than two people can be on the boat Artificial Intelligence 21 12:05 AM  Missionaries and Cannibals Task: Consider the shown, simplifies, Missionaries and Cannibals problem. Define this AI problem by representing: [S, s, O, G], and drawing the search space. Artificial Intelligence 22 12:05 AM  Missionaries and Cannibals State: (#mL, #cL, #mR, #cR, 1/0) – #mL is the number of missionaries at the left side. – #cL is the number of cannibals at the left side. – The last bit indicate the location of the boat. 1 means right side of the river, and 0 means left side of the river. So: (2,2,0,0,0), G: (0,0,2,2,1). Operators: – Boat carry: (1,0), (0, 1), (2,0),(0,2),(1,1)  Missionaries and Cannibals Think of the solution as an exercise!