Informed Search PDF

Informed search Artificial intelligence Kristóf Karacs PPKE-ITK Recap n What is intelligence? n Agent model n Problem solving by search ¨ Non-informed search strategies ¨ Informed search strategies 1...

Informed search Artificial intelligence Kristóf Karacs PPKE-ITK Recap n What is intelligence? n Agent model n Problem solving by search ¨ Non-informed search strategies ¨ Informed search strategies 1 Program n Problem solving by search n Search including other agents n Logic and inference n Search in logic representation, planning n Inference in case of constraints n Bayesian networks n Fuzzy logic n Machine learning Outline n Best-first search n What information is available? n Heuristic, heuristic function n Strategies: UCS, greedy, A* n Properties of heuristics n Designing heuristics n Comparing search algorithms n Further informed search strategies ¨ IDA*, RBFS, SMA* 2 Search and AI n Search methods are ubiquitous in AI systems n An autonomous robot uses search ¨ to decide which actions to take and which sensing operations to perform, ¨ to quickly anticipate collision, ¨ to plan trajectories, ¨ to interpret large numerical datasets provided by sensors into compact symbolic representations, ¨ to diagnose why something did not happen as expected, ¨ etc... n Many searches may occur concurrently and sequentially Applications n Search plays a key role in many applications ¨ Route finding: airline travel, networks ¨ Package/mail distribution ¨ Pipe routing, VLSI routing ¨ Comparison and classification of protein folds ¨ Pharmaceutical drug design ¨ Design of protein-like molecules ¨ Video games 3 Assumptions in basic search n World is ¨ static ¨ discretizable ¨ observable n Actions are deterministic n In many real world problems these assumptions do not hold ® Extended search techniques are required Search strategy n The fringe is the set of all search nodes not yet expanded n The fringe is implemented as a priority queue ¨ insert(n, Q) ¨ remove(Q) n The ordering of the nodes in the queue defines the search strategy 4 Revisiting states n Most search strategies have two versions ¨ States can be revisited ¨ States cannot be revisited n Not appropriate for all strategies Best-first search n Which node is good? n f() : evaluation function (typically cost function) n Selection criteria: minimal value of f() n Note: “Best” does not guarantee optimality of the solution path 5 Properties of best-first search n If the state space is infinite, then in general the search is not complete n If the state space is finite and revisited states are not discarded, then in general the search is not complete n If the state space is finite and revisited states are discarded, then the search is complete, but in general it is not optimal Search algorithm n insert(initial-node, Q) n Cycle ¨ If Q is empty then return failure ¨n ß remove(Q) ¨ s ß state(n) ¨ If is-goal(s) then return s and/or path ¨ For every state s’ in succ(s) n Create a node n’ as a successor of n n insert(n’, Q) 6 Using information in search n Intelligence: situation evaluation n Cost of an action ¨ Distancein route planning ¨ Power consumption n Path cost ¨ g() : Sum of all action costs in the path Defeating exponential blow up n Decreasing the number of actions in a given state (policy function) n Decreasing search depth (value function) n Monte Carlo tree search… 7 Heuristic searches n Heuristic = Rule of thumb ¨ Differentfrom heuristic measures ¨ Influences the node to expand n Values that can help ¨ Path cost g() ¨ Heuristic measures h() Heuristic Function n h(node) ¨ Estimates path cost of reaching the solution ¨ Independent of the actual search tree ¨ h(goal state) = 0 n Methods to derive a heuristic function ¨ Mathematically ¨ By introspection ¨ Inspection of particular searches ¨ Computer programs (e.g.: Absolver) n Example: straight line distance 8 Uniform Cost Search (non-informed) n ~BFS n Expands node with smallest g() (ignores heuristic measures) n Finds a solution with least cost ¨ Condition: action costs must be positive n Optimal and complete n Can be very slow Greedy Search n Expand node with smallest h() (ignores path cost) n If in a dead-end then backtrack n Problems ¨ Blind alley effect: estimates can be wrong, leading to superfluous curves ¨ May lead to non-optimal solution (h() is only an estimate of path cost to the goal) 9 A* search n Combines ¨ uniform cost search and ¨ greedy search n f(n) estimates the cost of the best path through n n f(n) = g(n) + h(n) n Hart, Nilsson and Raphael, 1968 Example: route finding Leeds Liverpool 75 n g(n) = distance from London n h(n) = straight line distance to 35 135 70 Liverpool Nottingham Manchester 155 n f(n) = g(n) + h(n) 150 60 n 1st round: Birmingham, Peterborough Birmingham Peterborough ¨ f(Peterborough) = 120 + 155 = 275 ¨ f(Birmingham) = 130 + 150 = 280 n Expands Peterborough 120 130 n Returns to Birmingham in the next step, because 120+60+135 > 130+150 London 10 Properties of heuristics n A heuristic h(n) is admissible if it never overestimates the path cost from node n to the goal node, i.e. 0 £ h(n) £ h*(n) for all n. n A heuristic h(n) is consistent (monotone) if, for every node n and every successor n’ of n generated by any action a h(n) £ c(n, a, n’) + h(n’). n h1 dominates h2 if h1(n) ≥ h2(n). Completeness theorem n A* always finds an optimal solution path (even for non- admissible heuristics) if there are finitely many nodes with f (n) ≤ f*, f* being the cost of the optimal path. This is guaranteed if ¨ all action costs ³ ε, for some fixed ε > 0, and ¨ the branching degree of all nodes are finite n Proof (sketch) ¨ Let f* be the cost of the optimal path ¨ All nodes with f (n) < f * will get expanded ¨ Some further nodes with f (n) = f * may get expanded 11 Optimality theorems n If h(n) is admissible, then A* is optimal with no visited list n If h(n) is consistent, then A* is optimal using a visited list n If h(n) is admissible, then A* is optimally efficient: with any given heuristic no other search strategy expands fewer nodes Dominance theorem n If h and h’ are heuristic functions and h dominates h’, then any node expanded by an A* search using h is also expanded by A* using h’ n Thus, using a dominant heuristic will result in fewer expanded nodes 12 Missionaries and cannibals n Three missionaries and three cannibals must cross a river, using a boat that can carry at most two. n Find a sequence of operations that ensures that cannibals never outnumber missionaries on either side of the river! Designing heuristics n Good heuristics can be hard to find ¨ Often they are implicit in the problem, such as the Euclidean distance heuristic for route-finding ¨ They may be found by relaxing some constraint in the problem n 8-puzzle, 15-puzzle: allow two tiles to occupy the same square n Missionaries: don't worry about missionaries getting eaten n Good heuristics can be hard to compute ¨ Overall goal: minimizing the total time ¨ (Avg. time of computing the heuristic value + node expansion) * (total no. of nodes expanded during search) ¨ Trade off between the branching factor and heuristic complexity 13 Comparing search algorithms n Effective branching factor (ebf): ∗ ¨ Branching rate of a search tree, in which each node has the same number of outgoing edges (BFS) n Calculation ¨ : depth of solution ¨ : number of nodes expanded ∗ ∗ ∗ ∗ ∗ =1+ + + + ⋯+ = ∗ ∗ ¨ Solve for Example: Effective Branching Factor n Suppose ¨ = 15 steps ¨ =4 ∗ n Solve: ∗ = 15 ∗ n Result: = 1.57 14 Numerical comparison n The shortest solution for the missionaries-and-cannibals problem takes 12 steps Search strategy Number of Effective steps branching factor BFS 24,464 2.21 A* search, h1(x) = number of people still 1,202 1.67 on the left bank of the river A* search, h2(x): relaxes the requirement 40 1.18 that cannibals not outnumber missionaries Iterative-Deepening A* search n Bottleneck of A* is memory (not time) ¨ All visited nodes have to be recorded n Iterative deepening like in IDS ¨ Define contours based on evaluation function ¨ Iteratively increase the limit ¨ At each iteration use a cutoff value equal to the smallest f(n) of any node that exceeded the limit in the previous iteration 15 IDA* search - contours Recursive best-first search (RBFS) n Best-first (using f() ) ¨ Stores search tree and the best alternative solution for each expanded node ¨ If there is a better alternative among the nodes visited earlier ® forget the current subtree and continue there ¨ When recursion unwinds, replace the f() value of a node with best f() value of its children n Requires linear space 16  Task: A* from Arad to Bucharest Recursive best-first search (RBFS) 17 Recursive best-first search (RBFS) Recursive best-first search (RBFS) 18 A* vs. RBFS example A* search 19 RBFS RBFS analysis n More efficient than IDA* and still optimal ¨ Best-first Search based on next best f() contour; fewer regeneration of nodes ¨ Exploit results of search at a specific f() contour by saving next f() contour associated with a node whose successors have been explored n Like IDA* still suffers from excessive node regeneration n IDA* and RBFS not good for graphs ¨ Can’t check for repeated states other than those on current path n Both are hard to characterize in terms of expected time complexity 20 Simplified memory-bounded A* (SMA*) n B: bound on memory n If memory is full when performing A* ® drop worst leaf node (with lowest f()) and back-up the value of the forgotten node to its parent n If correctly parameterized, SMA* can solve more complex problems than A* SMA* analysis n Complete, if there is any reachable solution n Optimal, if any optimal solution is reachable n Problem: if B is too low ® thrashing may occur (among a small set of candidate nodes) 21 Extensions of A* n Incremental heuristic search ¨ Optimal efficiency theorem applies only to separate problems ¨ If search trees of subsequent problems are similar, then incremental techniques can be more efficient n Examples ¨ Fringe saving A* ¨ Generalized adaptive A* ¨ D*, D* Lite, Lifelong planning A* Further extensions n Parallel search ¨ Multi- and manycore architectures n Very large state spaces ¨ Graphsdo not fit in memory, random access becomes much slower n Both require a completely rethought theoretical approach 22 Summary n Assumptions and applications n Best-first search n Path cost, heuristic function n Strategies: UCS, greedy, A*, IDA*, RBFS, SMA* n Admissible, consistent, dominant heuristics n Designing good heuristics n Effective branching factor (comparison) 23