Example:vacuum world Single-state,start in #5.Solution?? Right,Suck 1 -Q 2 Conformant,start in {1,2,3,4,5,6,7,8} e.g.,Right goes to (2,4,6,8}.Solution?? Q 8 3 Right,Suck,Left,Suck -Q -Q Contingency,start in #5 哪 Murphy's Law:Suck can dirty a clean carpet Local sensing:dirt,location only. Solution?? Right,if dirt then Suck Chapter 3 11
Example: vacuum world Single-state, start in #5. Solution?? [Right, Suck] Conformant, 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, start in #5 Murphy’s Law: Suck can dirty a clean carpet Local sensing: dirt, location only. Solution?? [Right, if dirt then Suck] 1 2 3 4 5 6 7 8 Chapter 3 11
Single-state problem formulation A problem is defined by four items: initial state e.g.,"at Arad" successor function S(z)=set of action-state pairs e.g.,S(Arad)={(Arad-Zerind,Zerind),...} goal test,can be explicit,e.g.,="at Bucharest" implicit,e.g.,NoDirt(x) path cost(additive) e.g.,sum of distances,number of actions executed,etc. c(x,a,y)is the step cost,assumed to be >0 A solution is a sequence of actions leading from the initial state to a goal state Chapter 3 12
Single-state problem formulation A problem is defined by four items: initial state e.g., “at Arad” successor function S(x) = set of action–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 (additive) e.g., sum of distances, number of actions executed, etc. c(x, a, y) is the step cost, assumed to be ≥ 0 A solution is a sequence of actions leading from the initial state to a goal state Chapter 3 12
Selecting a state space Real world is absurdly complex state space must be abstracted for problem solving (Abstract)state-set of real states (Abstract)action complex combination of real actions eg,“"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)solution set of real paths that are solutions in the real world Each abstract action should be "easier"than the original problem! Chapter 3 13
Selecting a state space Real world is absurdly complex ⇒ state space must be abstracted for problem solving (Abstract) state = set of real states (Abstract) action = complex combination of real actions 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) solution = set of real paths that are solutions in the real world Each abstract action should be “easier” than the original problem! Chapter 3 13
Example:vacuum world state space graph states?? actions?? goal test?? path cost?? Chapter 3 14
Example: vacuum world state space graph R L S S S S R L R L R L S S S S L L L L R R R R states?? actions?? goal test?? path cost?? Chapter 3 14
Example:vacuum world state space graph g园0园✉0 states??:integer dirt and robot locations (ignore dirt amounts etc.) actions?? goal test?? path cost?? Chapter 3 15
Example: vacuum world state space graph R L S S S S R L R L R L S S S S L L L L R R R R states??: integer dirt and robot locations (ignore dirt amounts etc.) actions?? goal test?? path cost?? Chapter 3 15