Solving problems by searching Chapter 3 14Jan2004 CS 3243-Blind Search 1
14 Jan 2004 CS 3243 - Blind Search 1 Solving problems by searching Chapter 3
Outline Problem-solving agents Problem types Problem formulation Example problems Basic search algorithms 14]an2004 CS 3243-Blind Search 2
14 Jan 2004 CS 3243 - Blind Search 2 Outline ◼ Problem-solving agents ◼ Problem types ◼ Problem formulation ◼ Example problems ◼ Basic search algorithms
Problem-solving agents function SIMPLE-PROBLEM-SOLVING-AGENT(percept)returns an action static:seg,an action sequence,initially empty state,some description of the current world state goal,a goal,initially null problem,a problem formulation stateUPDATE-STATE(state,percept) if seg is empty then do goal+FORMULATE-GOAL(state) problem+FORMULATE-PROBLEM(state,goal) seg+SEARCH(problem) action←-FIRST(seq) seq←REsT(seq return action 14]an2004 CS 3243 Blind Search 3
14 Jan 2004 CS 3243 - Blind Search 3 Problem-solving agents
Example:Romania On holiday in Romania;currently in Arad. Flight leaves tomorrow from Bucharest ■Formulate goal: ■be in Bucharest Formulate problem: states:various cities actions:drive between cities ■ ■Find solution: 14 Jan zosequence of cities,ceng3,AracarSibiu,Fagaras,Bucharest 4
14 Jan 2004 CS 3243 - Blind Search 4 Example: Romania ◼ On holiday in Romania; currently in Arad. ◼ Flight leaves tomorrow from Bucharest ◼ ◼ Formulate goal: ◼ be in Bucharest ◼ ◼ Formulate problem: ◼ states: various cities ◼ actions: drive between cities ◼ ◼ Find solution: ◼ sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest ◼
Example:Romania Oradea 71 Neamt Zerind ▣ 87 75 151 ▣si Arad 140 92 Sibiu 99 Fagaras 18 ▣ 80 白Vaslui Timisoara Rimnicu Vilcea 142 11 211 口Lugj Pitesti 97 70 98 Hirsova Mehadia 146 101 85 Orziceni 的 ■ 138 86 Bucharest Dobreta自 120 Craiova 90 Efo rie Giu rgiu 14]an2004 CS 3243 Blind Search 5
14 Jan 2004 CS 3243 - Blind Search 5 Example: Romania
Problem types Deterministic,fully observable single-state problem Agent knows exactly which state it will be in;solution is a sequence Non-observable sensorless problem(conformant problem) Agent may have no idea where it is;solution is a sequence Nondeterministic and/or partially observable>contingency problem percepts provide new information about current state often interleave}search,execution Unknown state space exploration problem 14]an2004 CS 3243-Blind Search 6
14 Jan 2004 CS 3243 - Blind Search 6 Problem types ◼ Deterministic, fully observable → single-state problem ◼ Agent knows exactly which state it will be in; solution is a sequence ◼ ◼ Non-observable → sensorless problem (conformant problem) ◼ Agent may have no idea where it is; solution is a sequence ◼ ◼ Nondeterministic and/or partially observable → contingency problem ◼ percepts provide new information about current state ◼ often interleave} search, execution ◼ ◼ Unknown state space → exploration problem
Example:vacuum world Single-state,start in #5. 2 Solution? 3 哪 3 3 哪 6 哪 8 14]an2004 CS 3243-Blind Search 7
14 Jan 2004 CS 3243 - Blind Search 7 Example: vacuum world ◼ Single-state, start in #5. Solution? ◼
Example:vacuum world Single-state,start in #5. Solution?Right,Suck Q 2 Q 哪 哪 部 3 4 3 Sensorless,start in {1,2,345,678e.g, 5 6 Right goes to [246,8) 8 哪 Solution? 8 14]an2004 CS 3243-Blind Search
14 Jan 2004 CS 3243 - Blind Search 8 Example: vacuum world ◼ Single-state, start in #5. Solution? [Right, Suck] ◼ ◼ Sensorless, start in {1,2,3,4,5,6,7,8} e.g., Right goes to {2,4,6,8} Solution? ◼
Example:vacuum world Sensorless,start in {1,2,3,45678e.g, 2 哪 8 3 哪 Right goes to {2,4,6,8) Solution? 3 4 哪 TRight,Suck,Left,Suck] 5 6 8 然 8 Contingency Nondeterministic:Suck may dirty a clean carpet Partially observable:location,dirt at current location. Percept:L,Clean/,i.e.,start in #5 or #7 14 Jan 20olution? CS 3243-Blind Search 9
14 Jan 2004 CS 3243 - Blind Search 9 Example: vacuum world ◼ Sensorless, start in {1,2,3,4,5,6,7,8} e.g., Right goes to {2,4,6,8} Solution? [Right,Suck,Left,Suck] ◼ ◼ Contingency ◼ Nondeterministic: Suck may dirty a clean carpet ◼ Partially observable: location, dirt at current location. ◼ Percept: [L, Clean], i.e., start in #5 or #7 Solution?
Example:vacuum world Sensorless,start in {1,2,34,5678e.g, 2 3 哪 哪 部 Right goes to (246,8) Solution? 3 4 TRight,Suck,Left,Suck] 5 6 3 娜 8 Contingency Nondeterministic:Suck may dirty a clean carpet Partially observable:location,dirt at current location. Percept:L,Clean/,i.e.,start in #5 or #7 14 Jan 20Splution?[Right,ifsdint eack 10
14 Jan 2004 CS 3243 - Blind Search 10 Example: vacuum world ◼ Sensorless, start in {1,2,3,4,5,6,7,8} e.g., Right goes to {2,4,6,8} Solution? [Right,Suck,Left,Suck] ◼ ◼ Contingency ◼ Nondeterministic: Suck may dirty a clean carpet ◼ Partially observable: location, dirt at current location. ◼ Percept: [L, Clean], i.e., start in #5 or #7 Solution? [Right, if dirt then Suck]