Selecting a state space Example:vacuum world state space graph 0图O (Abstract)state set of real states 0号0·0T0 eg.. 00 setofreapat thatareos in thereord Each abstract actionshoud bethan the orignl problem! co? Example:vacuum world state space graph Example:vacuum world state space graph 0。 1 00 00 00 00 Example:vacuum world state space graph Example:vacuum world state space graph 00 0图®0 000g号0 00g华0 号50 50 二hSelecting 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 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 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 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??: Left, Right, Suck, NoOp goal test?? path cost?? Chapter 3 16 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??: Left, Right, Suck, NoOp goal test??: no dirt path cost?? Chapter 3 17 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??: Left, Right, Suck, NoOp goal test??: no dirt path cost??: 1 per action (0 for NoOp) Chapter 3 18