CMPUT 366 F20: Heuristic Search
James Wright & Vadim Bulitko
September 15, 2020
CMPUT 366 F20: Heuristic Search
1
Lecture Outline
Assignment 1 is out
Feedback on Lab 1 yesterday?
Heuristic (informed) search
PM 3.6 and 3.7
CMPUT 366 F20: Heuristic Search 2
Recap of the last lecture
Different search strategies have different properties and behaviour costs DFS: space efficient, incomplete, suboptimal
BFS: space inefficient, complete, number-of-edges optimal IDS: space efficient, complete, optimal, less time efficient
LCFS is essentially BFS search with a cost-optimality guarantee
Can we do better than any of these?
CMPUT 366 F20: Heuristic Search 3
Generic Graph Search Algorithm
How can we shape the frontier better?
CMPUT 366 F20: Heuristic Search 4
Heuristics
Domain-specific knowledge to shape the frontier
Encoded as a heuristic function — an estimate of the remaining travel cost
Opens up the whole area of heuristic search
CMPUT 366 F20: Heuristic Search 5
Heuristic Functions
For nodes/vertices/states: h : V → R+ ∪ {à} For paths: h([n, . . . , nk]) = h(nk)
Admissibility: ∀n [h(n) ≤ cost∗(n, goal)] Thus h(goal) = à
Useless/trivial but admissible heuristic: ∀n [h(n) = à]
CMPUT 366 F20: Heuristic Search 6
Examples of Heuristics
Pathfinding: Euclidean distance Vacuum Bot: number of dirty rooms 15 puzzle: Manhattan distance
https://www.growingwiththeweb.com/2012/06/ a- pathfinding- algorithm.html
https://en.wikipedia.org/wiki/15_puzzle
CMPUT 366 F20: Heuristic Search
7
Constructing Admissible Heuristics
Combine multiple admissible heuristics:
h3(n) = max{h(n), h2(n)} preserves admissibility
Cost of an optimal solution to a related problem of a no-greater cost must be easier to solve than the original problem
a relation
a provable non-increase of solution cost
How do get those easier related problems?
drop some constraints on the original problem (relaxation)
can be via state abstraction
Possibly pre-compute and store solutions to relaxed/abstracted problems
pattern databases
Program synthesis for heuristic formulae/code
if curious: research paper posted on eClass
CMPUT 366 F20: Heuristic Search 8
Use of Heuristics: heuristic DFS and BFS
Heuristic DFS: order children paths added to the frontier by their heuristic
Heuristic (greedy) BFS: order the frontier by the paths’ heuristic
PM Example 3.14
CMPUT 366 F20: Heuristic Search 9
A* (1968)
Use both the cost so far and the cost remaining Select the path on the frontier with the lowest f
CMPUT 366 F20: Heuristic Search 10
A* Pseudo-code
CMPUT 366 F20: Heuristic Search 11
A* Example
CMPUT 366 F20: Heuristic Search 12
A* Properties
Consider a solution p = [start, n2, . . . , nk−, goal]. If h is admissible then ∀i ≤ k [f(ni) ≤ f(p)]
A* optimality: with an admissible heuristic, all edge costs lower bounded by ε > à and a finite branching factor, A* is complete and always returns an optimal (i.e., lowest-cost) solution
CMPUT 366 F20: Heuristic Search 13
A* Properties
A* with an admissible heuristic is about to expand a goal node → it has found a lowest-cost path to it
homework: try to prove this
Not true for non-goal nodes
homework: try to prove this
With a consistent (∀(n, n2) ∈ E [|h(n) − h(n2)| ≤ cost(n, n2)]) and admissible heuristic, whenever A* expands any node on its frontier, it has found a lowest-cost path to that node
Thus we can use multiple-path pruning and keep solution optimality (PM 3.7.2)
CMPUT 366 F20: Heuristic Search 14
A* Properties
Space complexity: O(bm) Time complexity: O(bm)
Why not use LCFS instead?
CMPUT 366 F20: Heuristic Search 15
Iterative Deepening A*
Iterative deepening (previous lecture)
Iterative deepening A* (IDA*) (PM 3.6.1) a series of DFS iterations
start with F = f(start)
runDFSwithf ≤F
on the next iteration set F to the minimum of encountered f values that exceeded F
https://artint.info/2e/html/ArtInt2e.html
CMPUT 366 F20: Heuristic Search
16
Summary of Search Algorithms So Far
Search
BFS DFS
ID LCFS greedy BFS A* IDA*
Frontier selection
Solution optimality
Space
exponential linear linear exponential exponential exponential linear
first node added (i.e., lowest edge cost)
fewest edges
last node added
none
last node added
fewest edges
lowest cost(p)
lowest cost
lowest h(p)
none
lowest cost(p) + h(p)
lowest cost
last node added
lowest cost
IDA* does not employ multiple-path pruning: to keep linear memory footprint
can get to the same node in many different ways ineffective on such graphs
CMPUT 366 F20: Heuristic Search
17