ple:The 8-puzzle aple:The 8-puzzle 724 123 724 23 468 831 8 831 可8 ic) oal state (giv Example: The 8-puzzle Example:The 8-puzzle 724 回▣ ⑦24 23 56 456 83可 78 831 78 diate positions） Note:optimal solution of n-Puzzle family is NP.hard Example:The 8-puzzle Example:robotic assembly 724 123 56 456 831 actions??:continuous motions of robot joints no robot included! to execute Example: The 8-puzzle 2 Start State Goal State 51 3 4 6 7 8 5 1 2 3 4 6 7 8 5 states?? actions?? goal test?? path cost?? Chapter 3 19 Example: The 8-puzzle 2 Start State Goal State 51 3 4 6 7 8 5 1 2 3 4 6 7 8 5 states??: integer locations of tiles (ignore intermediate positions) actions?? goal test?? path cost?? Chapter 3 20 Example: The 8-puzzle 2 Start State Goal State 51 3 4 6 7 8 5 1 2 3 4 6 7 8 5 states??: integer locations of tiles (ignore intermediate positions) actions??: move blank left, right, up, down (ignore unjamming etc.) goal test?? path cost?? Chapter 3 21 Example: The 8-puzzle 2 Start State Goal State 51 3 4 6 7 8 5 1 2 3 4 6 7 8 5 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?? Chapter 3 22 Example: The 8-puzzle 2 Start State Goal State 51 3 4 6 7 8 5 1 2 3 4 6 7 8 5 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] Chapter 3 23 Example: robotic assembly R R R P R R 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 Chapter 3 24