Problem types Example:va world DaemAtoaaaim is a seq 图 图 Non-ob omcrmn,atih dirty a clea Unknown state space exploration problem ("online") Example:vacuum world Example:vacuum world Single-state. 图 图▣图 ‘☑ Conformant,start in (..4.56.7.8) 图☐·☑ 图 AE 图 ☑ clean carpet Righ,dirt then Suck Example:vacuum world Single-state problem formulation 图 initial statetArad 图□ ☑ successor fune 冠 goal test,can be 4■ ☑ path cost (additive) Problem types Deterministic, fully observable =⇒ single-state problem Agent knows exactly which state it will be in; solution is a sequence Non-observable =⇒ conformant problem Agent may have no idea where it is; solution (if any) is a sequence Nondeterministic and/or partially observable =⇒ contingency problem percepts provide new information about current state solution is a contingent plan or a policy often interleave search, execution Unknown state space =⇒ exploration problem (“online”) Chapter 3 7 Example: vacuum world Single-state, start in #5. Solution?? 1 2 3 4 5 6 7 8 Chapter 3 8 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?? 1 2 3 4 5 6 7 8 Chapter 3 9 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?? 1 2 3 4 5 6 7 8 Chapter 3 10 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(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