Chapter 3: Problem solving and search | Đại Học Nội Vụ Hà Nội

lOMoAR cPSD|5906219 0 Chapter 3: Problem solving and search Reminders : Assignment 0 due 5pm today Assignment 1 posted, due 2/9
Sec on 105 will move to 9-10am star next week Chapter 3 1 lOMoAR cPSD|590621 90 ♦ Problem-solving agents ♦ Problem types ♦ Problem formula on ♦ Example problems ♦ Basic search algorithms Problem-solving agents
Restricted form of general agent:
func on Simple-Problem-Solving-Agent(percept) returns an ac on sta c: seq, an
ac on sequence, ini ally empty state, some descrip on of the current world Chapter 3 2 lOMoAR cPSD|590621 90
state goal, a goal, ini ally null problem, a problem formula on
state←Update-State(state,percept) if seq is empty then goal←Formulate- Goal(state)
problem←Formulate-Problem(state,goal) seq←Search(problem) action←Recommenda on(seq,state)
seq←Remainder(seq,state) return action
Note: this is offline problem solving; solu on executed “eyes closed.”
Online problem solving involves ac ng without complete knowledge. Chapter 3 3 lOMoAR cPSD|590621 90 Example: Romania
On holiday in Romania; currently in Arad.
Flight leaves tomorrow from Bucharest
Formulate goal: be in Bucharest Formulate problem: states: various ci es ac ons: drive between ci es Find solu on:
sequence of ci es, e.g., Arad, Sibiu, Fagaras, Bucharest Chapter 3 4 lOMoAR cPSD|590621 90 Example: Romania 5 lOMoAR cPSD|590621 90 Chapter 3 Problem types
Determinis c, fully observable =⇒ single-state problem
Agent knows exactly which state it will be in; solu on is a sequence
Non-observable =⇒ conformant problem
Agent may have no idea where it is; solu on (if any) is a sequence
Nondeterminis c and/or par ally observable =⇒ con ngency problem
percepts provide new informa on about current state solu on is
a con ngent plan or a policy o en interleave search, execu on
Unknown state space =⇒ explora on problem (“online”) Example: vacuum world
Single-state, start in #5. Solu on?? Chapter 3 6 lOMoAR cPSD|590621 90 1 2
Single-state, start in #5. Solu on?? [Right,Suck] 1 2
Conformant, start in {1,2,3,4,5,6,7,8} 3 4
e.g., Right goes to {2,4,6,8}. Solu on?? Chapter 3 7 lOMoAR cPSD|590621 90 5 6 Chapter 3 8 lOMoAR cPSD|590621 90 7 8 Chapter 3 9 lOMoAR cPSD|590621 90 Example: vacuum world
Single-state, start in #5. Solu on?? 2 [Right,Suck] 1
Conformant, start in {1,2,3,4,5,6,7,8} 3 4
e.g., Right goes to {2,4,6,8}. Solu on?? [Right,Suck,Left,Suck] 5 6
Con ngency, start in #5 Murphy’s Law: Suck can dirty a clean carpet 8 7 Local sensing: dirt, loca on only. Solu on?? Example: vacuum world
Single-state, start in #5. Solu on?? Chapter 3 10 lOMoAR cPSD|590621 90 [Right,Suck] 1 2
Conformant, start in {1,2,3,4,5,6,7,8} 3 4
e.g., Right goes to {2,4,6,8}. Solu on?? [Right,Suck,Left,Suck] 5 6
Con ngency, start in #5 Murphy’s Law: Suck can dirty a clean carpet 8 7 Local sensing: dirt, loca on only. Solu on?? [Right,if dirt then Suck]
Single-state problem formulation
A problem is defined by four items: Chapter 3 11 lOMoAR cPSD|590621 90
ini al state e.g., “at Arad” successor func on
S(x) = set of ac on–state pairs
e.g., S(Arad) = {hArad → Zerind,Zerindi,...}
goal test, can be explicit, e.g., x = “at Bucharest” implicit, e.g., NoDirt(x) path cost (addi ve)
e.g., sum of distances, number of ac ons executed, etc.
c(x,a,y) is the step cost, assumed to be ≥ 0
A solu on is a sequence of ac ons leading
from the ini al state to a goal state Selecting a state space
Real world is absurdly complex Chapter 3 12 lOMoAR cPSD|590621 90
⇒ state space must be abstracted for problem solving
(Abstract) state = set of real states Chapter 3 13 lOMoAR cPSD|590621 90
(Abstract) ac on = complex combina on of real ac ons
e.g., “Arad → Zerind” represents a complex set
of possible routes, detours, rest stops, etc.
For guaranteed realizability, any real state “in Arad” must
get to some real state “in Zerind”
(Abstract) solu on = set of real paths that are solu ons in the real world
Each abstract ac on should be “easier” than the original problem! Chapter 3 14 lOMoAR cPSD|590621 90
Example: vacuum world state space graph states?? ac ons?? goal test?? path cost?? Chapter 3 15 lOMoAR cPSD|590621 90
Example: vacuum world state space graph
states??: integer dirt and robot loca ons (ignore dirt amounts etc.)
ac ons?? goal test?? path cost?? Chapter 3 16 lOMoAR cPSD|590621 90
Example: vacuum world state space graph
states??: integer dirt and robot loca ons (ignore dirt amounts etc.)
ac ons??: Left, Right, Suck, NoOp goal test?? path cost?? Chapter 3 17 lOMoAR cPSD|590621 90
Example: vacuum world state space graph
states??: integer dirt and robot loca ons (ignore dirt amounts etc.)
ac ons??: Left, Right, Suck, NoOp goal test??: no dirt path cost?? Chapter 3 18 lOMoAR cPSD|590621 90
Example: vacuum world state space graph
states??: integer dirt and robot loca ons (ignore dirt amounts etc.)
ac ons??: Left, Right, Suck, NoOp goal test??: no dirt : 1 per ac on (0 for NoOp) Chapter 3 19 lOMoAR cPSD|590621 90 states?? ac ons?? goal test?? path cost?? Chapter 3 20