1CS 2710 Foundations of AICS 2710 Foundations of AILecture 4Milos [email protected] Sennott SquareUninformed search methods (finish) Informed search methodsCS 2710 Foundations of AITopicsUninformed search methods• Review of uninformed search methods• Checking state repeats• Uniform cost searchInformed search methods• Incorporating additional information to guide the search• Best first search– Greedy methods– A* search– IDA*• Heuristics2CS 2710 Foundations of AIUninformed methods• Uninformed search methods use only information available in the problem definition– Breadth-first search (BFS)– Depth-first search (DFS)– Iterative deepening (IDA)– Bi-directional search• For the minimum cost path problem:– Uniform cost searchCS 2710 Foundations of AIBreadth first search (BFS)• The shallowest node is expanded first3CS 2710 Foundations of AIProperties of breadth-first search• Completeness: Yes. The solution is reached if it exists.• Optimality: Yes, for the shortest path.• Time complexity:exponential in the depth of the solution d• Memory (space) complexity:same as time - every node is kept in the memory)(12 ddbObbb =++++ K)(dbOCS 2710 Foundations of AIDepth-first search (DFS)• The deepest node is expanded first• Backtrack when the path cannot be further expanded4CS 2710 Foundations of AIProperties of depth-first search• Completeness: No. Infinite loops can occur. •Optimality: No. Solution found first may not be the shortest possible.•Time complexity:exponential in the maximum depth of the search tree m• Memory (space) complexity:linear in the maximum depth of the search tree m)(mbO)(bmOCS 2710 Foundations of AILimited-depth depth first search•The limit (l) on the depth of the depth-first exploration)(lbO)(blOl- is the given limit•Time complexity:• Memory complexity: Limit l=2Not exploredl5CS 2710 Foundations of AIIterative deepening algorithm (IDA)• Progressively increases the limit of the limited-depth depth-first searchLimit 0Limit 1Limit 2CS 2710 Foundations of AIProperties of IDA• Completeness: Yes. The solution is reached if it exists.(the same as BFS)•Optimality: Yes, for the shortest path.(the same as BFS) •Time complexity:exponential in the depth of the solution dworse than BFS, but asymptotically the same • Memory (space) complexity:linear in the depth of the solution - much better than BFS)()()()()1(21 ddbObObObOO =++++ K)(dbO6CS 2710 Foundations of AIElimination of state repeatsWhile searching the state space for the solution we can encounter the same state many times.Question: Is it necessary to keep and expand all copies of states in the search tree? Two possible cases:(A) Cyclic state repeats(B) Non-cyclic state repeatsAABBSearch treeCS 2710 Foundations of AIElimination of cyclesHow to check for cyclic state repeats:Check ancestors in the tree structure.Do not expand the node with the state that is the same as the state in one of its ancestors.AA7CS 2710 Foundations of AIElimination of non-cyclic state repeatsCase B: nodes with the same state are not on the same path from the initial stateIs one of the nodes nodeB-1, nodeB-2 better or preferable??BBRoot of the search treenodeB-1nodeB-2CS 2710 Foundations of AIElimination of non-cyclic state repeatsCase B: nodes with the same state are not on the same path from the initial stateIs one of the nodes nodeB-1, nodeB-2 better or preferable?Yes. nodeB-1 represents the shorter path between the initial state and BBBRoot of the search treenodeB-1nodeB-28CS 2710 Foundations of AIElimination of non-cyclic state repeatsSince we are happy with the optimal solution nodeB-2 can be eliminated. It does not affect the optimality of the solution.Problem: Nodes can be encountered in different order during different search strategies.BBRoot of the search treenodeB-1nodeB-2CS 2710 Foundations of AIElimination of non-cyclic state repeats with BFSBreadth FS is well behaved with regard to non-cyclic state repeats:nodeB-1 is always expanded before nodeB-2• Order of expansion determines the correct elimination strategy • we can safely eliminate the node that is associated with the state that has been expanded before BBRoot of the search treenodeB-1nodeB-29CS 2710 Foundations of AIElimination of state repeats for the BFSFor the breadth-first search (BFS)• we can safely eliminate all second, third, fourth, etc. occurrences of the same state• this rule covers both the cyclic and non-cyclic repeats !!!Implementation of all state repeat elimination through marking:• All expanded states are marked• All marked states are stored in a special data structure (a hash table)• Checking if the node has ever been expanded corresponds to the mark structure lookupCS 2710 Foundations of AIElimination of non-cyclic state repeats with DFSDepth FS: nodeB-2 is expanded before nodeB-1 • The order of node expansion does not work imply correct elimination strategy • we need to remember the length of the path between nodes to safely eliminate themBBRoot of the search treenodeB-1nodeB-210CS 2710 Foundations of AIElimination of all state redundancies• General strategy: A node is redundant if there is another node with exactly the same state and a shorter path from the initial state– Works for any search method – Uses additional path length informationImplementation: marking with the minimum path value:• The new node is redundant and can be eliminated if – it is in the hash table (it is marked), and – its path is longer or equal to the value stored.• Otherwise the new node cannot be eliminated and it is entered together with its value into the hash table. (if the state was in the hash table the new path value is better and needs to be overwritten.)CS 2710 Foundations of AIBi-directional search• In some search problems we want to find the path from the initial state to the unique goal state (e.g. traveler problem)•Bi-directional search:– Search both from the initial state and the goal state;– Use inverse operators for the goal-directed search.Initial state Goal state11CS 2710 Foundations of AIBi-directional searchWhen does it help? • It cuts the size of the search tree by half.What is necessary?• Merge the solutions.Initial state Goal stateEqual ?CS 2710 Foundations of AIMinimum cost path searchTraveler example with distances [km]Optimal path: the shortest distance path from Arad to Bucharest12CS 2710 Foundations of AISearching for the