Single-state problem formulation A problem is defined by four items: 1. initial state e.g."at Arad" 2. 2. actions or successor function S)=set of action-state pairs ■e.g,S(Arad,={<Arad→Zerind,Zerind>.,.} 3. goal test,can be ■ explicit,e.g.,="at Bucharest" implicit,e.g.,Checkmate(x) 4. path cost (additive) 日 e.g.,sum of distances,number of actions executed,etc. axay)is the step cost,assumed to be >0 14 JaA29fution is a sequence of aog from the initial state to a 11 goal ctate
14 Jan 2004 CS 3243 - Blind Search 11 Single-state problem formulation A problem is defined by four items: 1. initial state e.g., "at Arad" 2. 2. actions or successor function S(x) = set of action–state pairs ◼ e.g., S(Arad) = {<Arad → Zerind, Zerind>, … } ◼ 3. goal test, can be ◼ explicit, e.g., x = "at Bucharest" ◼ implicit, e.g., Checkmate(x) ◼ 4. 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
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 14Jan2004 CS 3243-Blind Search 12 Fach abctract action should he "easier"than the
14 Jan 2004 CS 3243 - Blind Search 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 ◼ 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
Vacuum world state space graph C园 states? actions? goal test? ■ path cost? 14]an2004 CS 3243-Blind Search 13
14 Jan 2004 CS 3243 - Blind Search 13 Vacuum world state space graph ◼ states? ◼ actions? ◼ goal test? ◼ path cost? ◼
Vacuum world state space graph 图0 00 states?integer dirt and robot location actions?Left,Right,Suck ■goal test起no dirt at all locations path cost?1 per action 14]an2004 CS 3243-Blind Search 14
14 Jan 2004 CS 3243 - Blind Search 14 Vacuum world state space graph ◼ states? integer dirt and robot location ◼ actions? Left, Right, Suck ◼ goal test? no dirt at all locations ◼ path cost? 1 per action
Example:The 8-puzzle 4 2 5 3 Start State Goal State states? ■ actions? goal test? ■path cost2 14]an2004 CS 3243-Blind Search 15
14 Jan 2004 CS 3243 - Blind Search 15 Example: The 8-puzzle ◼ states? ◼ actions? ◼ goal test? ◼ path cost?