How to solve a problem - Problemdefinition and problem-based agents

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

key terminology to describe problems

Describe the Single-State-Problem and its four items

Explain the Tree-Search-Algorithm

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.

What is a Search Strategy? What dimensions does it include?

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?

What types of Search Strategies exist? Name examples for each Strategy

Explain the Uniform Cost Search (UCS). Evaluate them in terms of the dimensions for a search strategy!

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

Explain the Breadth-First Search (BFS). Evaluate them in terms of the dimensions for a search strategy!

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.

Explain the Depth-First Search (DFS). Evaluate them in terms of the dimensions for a search strategy!

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

Explain the Iterative-Deepening Search (DLS). Evaluate them in terms of the dimensions for a search strategy!

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!

Explain the Depth-limited Search (DLS). Evaluate them in terms of the dimensions for a search strategy!

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.

Compare BFS and DFS, Depth-limited search and Iterative deepeing search!

Compare BFS and DFS, Depth-limited search and Iterative deepeing search regarding the four dimensions of Search Algorithms!

Whats the problem with Uninformed search algorithms? What are solutions?

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!

Explain the Greedy Best-first Search! Evaluate them in terms of the dimensions for a search strategy!

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

Explain the A* Search! Evaluate them in terms of the dimensions for a search strategy!

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)

Explain Heuristics in more Detail!

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

What are two Lemmas from the Heuristic?

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.

Explain the concept of Relaxed Problems! Why are they important?

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.

Explain the concept of Dominance! Why is it important?

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

A* (as well as BFS) has Space problems. What are Alternatives?

Three Memory-Bounded Heuristic Search are Alternatives:

Iterative-deepening A* (IDA*)

like iterative deepening

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

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

(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

Summary and learning goals:

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

Last changed7 months ago