3. Uninformed and Informed Search

-> Problems must be reformulated for Agents, as they are most often made to be understood by humans

Idea: Treat the state-space graph as a tree

• Can use simulated iterative exploration of the state space

• Needs a strategy to determine which node is expanded next

Node is different from State!

A data structure to present a part of a search tree. It includes a state, a parent node, the taken action, the path costs and the current depth of the tree.

A search strategy is defined by picking the order of node expansion.

• Completeness: Does it always find a solution if one exists?

• Time Complexity: Number of Node expansions

• Space Complexity: Maximum number of nodes in memory

• Optimality: Does it always find the optimal (least costs) solution?

Uniform-Cost Search

• Each node is associated with a fixed cost (nodes can have different costs)

• costs accumulate over the path within the search

• uses the lowest cumulative cost to find a path

Breadth-First Search (BFS) -> memory consumptions very costly

• A special case of the uniform-cost search, when all costs are equal

• starts at the tree root and explores the tree level by level

• BFS stops as soon as it generates a goal, whereas UCS examines all the nodes at the goal’s depth to see if one has a lower cost.

Completeness : Yes, if each step has a positive cost, otherwise infinite loops are possible. Hence, BFS is also complete

Complexity: O(bd) for BFS, O(b1+floor(OptCost/eps)) for UCS OptCost=Cost of optimal solution, every actions costs at least eps

Optimality: Yes, since nodes expand in increasing order of path costs. In turn BFS is optimal.

Depth-First Search (DFS)

It starts at the tree root and explores the tree as far as possible along one branch before going step-wise back and exploring alternative branches.

Completeness: No, fails in infinite-depth search spaces and spaces with loops • Can be modified to be complete by avoiding repeated states and limit depth

Time Complexity: Explores each branch until max depth m, i.e., O(bm) • Terrible if m>d (depth of goal node), but may be good in dense settings

Space Complexity: Only a branch and their unexpanded siblings have to be stored • Therefore linear complexity, i.e., O(b*m)

Optimality: No, longer solutions may be found before shorter solutions • Solution could be more expensive then the optimal one

Iterative Deepening Search

Increase l after each failed search, i.e. l = 1, 2, 3, ...

It combines DFS and BFS and is therefore a good solution!

Depth-limited Search

The depth within the search is limited to l. Nodes with depth d>l are not considered.

Bidirectional Search

Perform two search simultaneously, starting with the root and goal state. Stop if node occurs in both searches.

Uninformed search algorithms are inefficient.

Idea: try to be more clever with what nodes to expand, bring knowledge into the process

• i.e. straight-line distances may be a good approximation for the remaining distance to travel

Heuristik h:

Informally denotes a „rule of thumb“, i.e. a rule that may be helpful in solving the problem. In tree-search, a heuristic denotes a function h that estimates the remaining costs to reach the goal

-> can also go wrong!

• Using the evaluation function f (n) = h(n) to estimate the cost from node n to goal

• e.g. h(n)=hSLD(n) = straight-line distance from n to Bucharest

• Expand the tree with smallest cost according to f (n), i.e., here the heuristic

Completeness: No, we can get stuck in loops • Is complete in a finite state space when we make sure to avoid repeating states

Time Complexity: Worst case O(bm), same as DFS but can be improved using good heuristics

Space Complexity: has to keep all nodes in memory​, worst case O(bm)

Optimality: No, solution depends on heuristic

An informed tree search algorithm, build on best-first search. Tries to minimize not only the estimated cost h(n) but also the true costs so far g(n)

Admissible Heuristic:

A heuristic is admissible if it never overestimates the cost to reach a goal!

To guarentee admissibility:

• Combine Heuristics and take maximum

• Problem Relaxation

Consistent Heuristics

A heuristic is consistent if for every node n and every successor n' generated by any action a it holds that h(n) ≤ c(,n,a, n‘) + h(n‘)

This makes sense:

if there were a route from n to the goal that was cheaper than h(n), that would violate the property that h(n) is a lower bound on the cost to reach the goal (kind of triangle inequality.

Combining Heuristics

Lemma 1: Every consistent heuristic is admissible.

Lemma 2: If h(n) is consistent, then the values of f(n) along any path are non-decreasing.

A problem with fewer restrictions on the actions is called a relaxed problem.

Implication for Heuristics:

The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem

Examples:

• If the rules of the 8-puzzle are relaxed so that a tile can move anywhere,then hMIS gives the shortest solution

-> looking for relaxed problems is a good strategy for inventing admissible heuristics.

If h1 and h2 are both admissible heuristics and h2(n) ≥ h1(n) for all n, then h2 dominates h1

Three Memory-Bounded Heuristic Search are Alternatives:

1. Iterative-deepening A* (IDA*)

   • like iterative deepening

   • cutoff information is the f-cost (g + h) instead of depth

2. Recursive best-first search (RBFS)

   • recursive algorithm that attempts to mimic standard best-first search with linear space.

   • keeps track of the f-value of the best alternative

   • path available from any ancestor of current node and heuristic evaluations are updated with results of successors

3. (Simple) Memory-bounded A* ((S)MA*)

   • drop the worst leaf node when memory is full

   • its value will be updated to its parent

   • may need to be re-searched later

• How to define problems

• How to find solutions for single- state problems

• The idea behind tree and graph search

• Some basic (un-)informed search strategies/algorithm

  • DFS, BFS,...

  • Greedy Best-first Search, A*

• Good heuristics can reduce the search time drastically

You should be able to:

• Formulate a real-world problem as a search problem

• Differentiate between search strategies

• Explain the difference between uninformed and informed search

• Iterate though DFS, BFS, A*,...

• Define properties of good heuristics