Example:The 8-puzzle 6 3 8 3 8 Start State Goal State states?locations of tiles actions?move blank left,right,up,down goal test?goal state (given) path cost?_1 per move [Note:optimal solution of n-Puzzle family is NP-hard] 14]an2004 CS 3243-Blind Search 16
14 Jan 2004 CS 3243 - Blind Search 16 Example: The 8-puzzle ◼ states? locations of tiles ◼ actions? move blank left, right, up, down ◼ goal test? = goal state (given) ◼ path cost? 1 per move ◼ [Note: optimal solution of n-Puzzle family is NP-hard]
Example:robotic assembly P 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 14]an2004 CS 3243-Blind Search path cost?:time to execute 17
14 Jan 2004 CS 3243 - Blind Search 17 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 ◼ ◼ path cost?: time to execute
Tree search algorithms Basic idea: offline,simulated exploration of state space by generating successors of already-explored states (a.k.a.~expanding states) function TREE-SEARCH(problem,strategy)returns a solution,or failure initialize the search tree using the initial state of problem loop do if there are no candidates for expansion then return failure choose a leaf node for expansion according to strategy if the node contains a goal state then return the corresponding solution else expand the node and add the resulting nodes to the search tree 14]an2004 CS 3243-Blind Search 18
14 Jan 2004 CS 3243 - Blind Search 18 Tree search algorithms ◼ Basic idea: ◼ offline, simulated exploration of state space by generating successors of already-explored states (a.k.a.~expanding states) ◼
Tree search example Aiad 2 14]an2004 CS 3243-Blind Search 19
14 Jan 2004 CS 3243 - Blind Search 19 Tree search example