State Space Graphs(状态空间图) State space graph:A mathematical representation of a search problem Nodes are(abstracted)world configurations Arcs represent successors (action results) The goal test is a set of goal nodes(maybe only one) In a state space graph,each state occurs only once! We can rarely build this full graph in memory (it's too big). but it's a useful idea G Tiny state space graph for a tiny search problem 日4左+1声，量9QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . State Space Graphs (状态空间图) ▶ State space graph: A mathematical representation of a search problem ▶ Nodes are (abstracted) world configurations ▶ Arcs represent successors (action results) ▶ The goal test is a set of goal nodes (maybe only one) ▶ In a state space graph, each state occurs only once! ▶ We can rarely build this full graph in memory (it’s too big), but it’s a useful idea
Example:Vacuum World State Space Graph 图0 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) 口卡B·三4色进分双0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example: Vacuum World State Space Graph ▶ 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)
Example:The 8-puzzle 7 2 3 5 6 5 6 8 3 8 Start State Goal State States:integer locations of tiles(ignore intermediate positions) Actions:move blank left,right,up,down (ignore unjamming etc.) Goal test:goal state(given) Path cost:1 per move Note:optimal solution of n-Puzzle family is NP-hard ,·15,￥20C
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example: The 8-puzzle ▶ States: integer locations of tiles (ignore intermediate positions) ▶ Actions: move blank left, right, up, down (ignore unjamming etc.) ▶ Goal test: = goal state (given) ▶ Path cost: 1 per move Note: optimal solution of n-Puzzle family is NP-hard
Example:Robotic Assembly States:real-valued coordinates (of robot joint angles parts of the object to be assembled Actions:continuous motions of robot joints Goal test:complete assembly with no robot included! Path cost:time to execute 口卡回t·三4色，是分Q0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example: Robotic Assembly ▶ States: real-valued coordinates (坐标) of robot joint angles parts of the object to be assembled ▶ Actions: continuous motions of robot joints ▶ Goal test: complete assembly with no robot included! ▶ Path cost: time to execute
例子：华容道 张 赵 赵 卒 马 黄 曹操 曹操 曹操 黄 卒 曹操 云 云 卒 超 忠 忠 卒 马 关羽 黄 关羽 卒 卒 卒 关羽 卒 关羽 张飞 超 卒卒 忠 马 张飞 黄 卒 张飞 卒 赵云 马超 卒 卒 超 忠 赵云 卒 卒 横刀立马(81) 层拦叠障(62) 层层设防(12) 水泄不通(79) 卒 卒 卒 卒 卒 赵 张 卒 卒 关羽 卒 曹操 曹搡 卒 卒 马 云 卒 黄 曹操 曹操 关羽 张飞 超 黄 赵 马 黄 卒 超 忠 赵云 马超 关羽 忠 云 超 忠 卒 卒 张飞 卒 黄忠 卒 张飞 关羽 赵云 过五关(34) 峰回路转(138) 一路进军(58) 井中之蛙(68) 4口◆4⊙t1三1=，￥9QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 例子：华容道