AI - Search

Problem-Solving: Search

Peter Norvig - AIMA

TEXT

CH. 2 Intelligent Agents

CH.3 Solving Problems by Searching

AI is doing what we don't know how to do.

Search is the key area where we can define steps to figure out what to do.

Problem Definition

Procedures

• initial state
• $Action(s) -> {a1, a2, a3...}$
• $Result(s, a) -> s'$
• $Goal_test(s) -> T/F$
• $Path_cost(s1->s2->s3) -> n or StepCost(s, a, s') -> n$

Structures in the algorithm

• Frontier
• unexplored region
• explored region

Tree Search

Remove choice from frontier

• BFS/Shortest First Search

Graph search

Add s to explored to avoid revisit the same node

Uniform Cost Search(Cheapest First)

• Greedy algorithm.

• non-zero action cost.

• Always expand the lowest cost of the frontier.

• Move the goal out of frontier, guaranteed to find the cheapest path cost.

Search comparison

Algorithm	Optimal	Completeness	Frontier numbers
BFS	Y	Y	2^n
UCS	Y	Y	> 2^n
DFS	N	N	n

They all need to keep the explored set space with 2^n.

Completeness: If the tree is infinite, can the algorithm find the goal?

A* Search algorithm

• The best part of greedy best first search.
• Add more knowledge to UCS with the consistent heuristic for the goal.

$$f = g(path) +h(path)$$

• g(path) = path cost

• h(path) = h(s) = "estimate distance to the goal."

Minimise g is to keep the path short;

Minimise h keeps searching focus on the goal.

A* find the lowest cost path if h(s) < true cost or h is optimistic, admissible.

A* Heuristic

We say h2 dominates h1 if for any node n,

$$h_2(n) >= h_1(n)$$

It means h2 will never expand more nodes than h1 for A*.

Final Review

Uninformed Search Strategy

• Best-First Search
• Breadth-First Search
• Uniform Cost Search
• Depth-First Search
• Depth-Limited/Iterative Deepening.

Informed Search Strategies

• Greedy Best-First Search
• A* Seach

Advanced Strategies

• Bi-directional Approach

Bi-directional Heuristic

1. What's the good heuristic for a search?

2. Admissible and consistent meaning.

$$f(n) = g(n) + h(n)$$ $$h(n) {'<='} h^*(n)$$ $$h(n) {'<='} c(n,a,n') + h(n')$$

1. Can you compare two heuristics and determine which heuristic performs better for a given search?