#### Transcript PowerPoint

CS 416 Artificial Intelligence Lecture 5 Informed Searches Administrivia Visual Studio • If you’ve never been granted permission before, you should receive email shortly Assign 1 • Set up your submit account password • Visit: www.cs.virginia.edu/~cs416/submit.html Toolkit • You should see that you’re enrolled through Toolkit access to class gradebook Example A h(n) 100 c(n, n’) 10 5 B C 0 Goal f(n) 90 10 95 A* w/o Admissibility B = goal f(B) = 10 Are we done? No Must explore C A 100 10 5 B C 0 Goal 90 10 95 A* w/ Admissibility B = goal f(B) = 10 Are we done? Yes h(C) indicates best path cost of 95 A 10 10 5 B C 0 Goal 90 10 95 A* w/o Consistency B 5 101 5 A D 0 100 4 C 200 5 A* w/ Consistency B 5 101 5 A D 0 100 4 C 105 5 Pros and Cons of A* A* is optimal and optimally efficient A* is still slow and bulky (space kills first) • Number of nodes grows exponentially with the length to goal – This is actually a function of heuristic, but they all make mistakes • A* must search all nodes within this goal contour • Finding suboptimal goals is sometimes only feasible solution • Sometimes, better heuristics are non-admissible Memory-bounded Heuristic Search Try to reduce memory needs Take advantage of heuristic to improve performance • Iterative-deepening A* (IDA*) • Recursive best-first search (RBFS) • SMA* Iterative Deepening A* Iterative Deepening • Remember, as in uniformed search, this was a depth-first search where the max depth was iteratively increased • As an informed search, we again perform depth-first search, but only nodes with f-cost less than or equal to smallest fcost of nodes expanded at last iteration – What happens when f-cost is real-valued? Recursive best-first search Depth-first combined with best alternative • Keep track of options along fringe • As soon as current depth-first exploration becomes more expensive of best fringe option – back up to fringe, but update node costs along the way Recursive best-first search • box contains f-value of best alternative path available from any ancestor • First, explore path to Pitesti • Backtrack to Fagaras and update Fagaras • Backtrack to Pitesti and update Pitesti Quality of Iterative Deepening A* and Recursive best-first search RBFS • O(bd) space complexity [if h(n) is admissible] • Time complexity is hard to describe – efficiency is heavily dependent on quality of h(n) – same states may be explored many times • IDA* and RBFS use too little memory – even if you wanted to use more than O(bd) memory, these two could not provide any advantage Simple Memory-bounded A* Use all available memory • Follow A* algorithm and fill memory with new expanded nodes • If new node does not fit – free() stored node with worst f-value – propagate f-value of freed node to parent • SMA* will regenerate a subtree only when it is needed – the path through deleted subtree is unknown, but cost is known Thrashing Typically discussed in OS w.r.t. memory • The cost of repeatedly freeing and regenerating parts of the search tree dominate the cost of actual search • time complexity will scale significantly if thrashing – So we saved space with SMA*, but if the problem is large, it will be intractable from the point of view of computation time Meta-foo What does meta mean in AI? • Frequently it means step back a level from foo • Metareasoning = reasoning about reasoning • These informed search algorithms have pros and cons regarding how they choose to explore new levels – a metalevel learning algorithm may combine learn how to combine techniques and parameterize search Heuristic Functions 8-puzzle problem Avg Depth=22 Branching = approx 3 322 states 170,000 repeated Heuristics The number of misplaced tiles • Admissible because at least n moves required to solve n misplaced tiles The distance from each tile to its goal position • No diagonals, so use Manhattan Distance – As if walking around rectilinear city blocks • also admissible Compare these two heuristics Effective Branching Factor, b* • If A* explores N nodes to find the goal at depth d – b* = branching factor such that a uniform tree of depth d contains N+1 nodes N+1 = 1 + b* + (b*)2 + … + (b*)d • b* close to 1 is ideal – because this means the heuristic guided the A* search linearly – If b* were 100, on average, the heuristic had to consider 100 children for each node – Compare heuristics based on their b* Compare these two heuristics Compare these two heuristics h2 is always better than h1 • for any node, n, h2(n) >= h1(n) • h2 dominates h1 • Recall all nodes with f(n) < C* will be expanded? – This means all nodes, h(n) + g(n) < C*, will be expanded All nodes where h(n) < C* - g(n) will be expanded – All nodes h2 expands will also be expanded by h1 and because h1 is smaller, others will be expanded as well Inventing admissible heuristic funcs How can you create h(n)? • Simplify problem by reducing restrictions on actions – Allow 8-puzzle pieces to sit atop on another – Call this a relaxed problem – The cost of optimal solution to relaxed problem is admissible heuristic for original problem It is at least as expensive for the original problem Examples of relaxed problems A tile can move from square A to square B if A is horizontally or vertically adjacent to B and B is blank • A tile can move from A to B if A is adjacent to B (overlap) • A tile can move from A to B if B is blank (teleport) • A tile can move from A to B (teleport and overlap) Solutions to these relaxed problems can be computed without search and therefore heuristic is easy to compute Multiple Heuristics If multiple heuristics available: • h(n) = max {h1(n), h2(n), …, hm(n)} Use solution to subproblem as heuristic What is optimal cost of solving some portion of original problem? • subproblem solution is heuristic of original problem Pattern Databases Store optimal solutions to subproblems in database • We use an exhaustive search to solve every permutation of the 1,2,3,4-piece subproblem of the 8-puzzle • During solution of 8-puzzle, look up optimal cost to solve the 1,2,3,4-piece subproblem and use as heuristic Learning Could also build pattern database while solving cases of the 8-puzzle • Must keep track of intermediate states and true final cost of solution • Inductive learning builds mapping of state -> cost • Because too many permutations of actual states – Construct important features to reduce size of space