Problems and Solutions A (search)problem consists of: An initial state so so In(Arad) Actions A(s)in each state A(In(Arad))={Go(Sibiu),Go(Timisoara),Go(Zerind)} A transition model Result(s,a) Result(In(Arad),Go(Zerind))=In(Zerind) A state space S S can be implicitly defined by so.A(s).and Result(s,a) A goal test G(s) ·Explicit,eg,G(s)=I(s∈{In(Bucharest)}) Implicit,e.g.,G(s)=Checkmate(s) A path cost function that assigns a numeric cost to each path E.g.,sum of distances,number of actions executed,etc. A step cost c(s,a,s),assumed to be >0 A solution is a sequence of actions leading from the initial state to a goal state An optimal solution has least cost among all solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Problems and Solutions ▶ A (search) problem consists of: ▶ An initial state s0 ▶ s0 = In(Arad) ▶ Actions A(s) in each state ▶ A(In(Arad)) = {Go(Sibiu), Go(Timisoara), Go(Zerind)} ▶ A transition model Result(s, a) ▶ Result(In(Arad), Go(Zerind)) = In(Zerind) ▶ A state space S ▶ S can be implicitly defined by s0, A(s), and Result(s, a) ▶ A goal test G(s) ▶ Explicit, e.g., G(s) = I(s ∈ {In(Bucharest)}) ▶ Implicit, e.g., G(s) = Checkmate(s) ▶ A path cost function that assigns a numeric cost to each path ▶ E.g., sum of distances, number of actions executed, etc. ▶ A step cost c(s, a,s ′ ), assumed to be ≥ 0 ▶ A solution is a sequence of actions leading from the initial state to a goal state ▶ An optimal solution has least cost among all solutions