CMPUT 366 F20: Heuristic Search II
Vadim Bulitko & James Wright
September 17, 2020
CMPUT 366 F20: Heuristic Search II
1
Lecture Outline
Heuristic (informed) search
PM 3.6, 3.7
CMPUT 366 F20: Heuristic Search II 2
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
Not looking at path cost → can lose number-of-edges optimality with greedy BFS PM Example 3.14
CMPUT 366 F20: Heuristic Search II 3
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 II 4
A*: Pseudo-code
CMPUT 366 F20: Heuristic Search II 5
A* Properties
Consider a solution
p = [start,n2,…,nk−,goal]. If h is admissible then ∀i ≤ k [f(ni) ≤ f(p)]
CMPUT 366 F20: Heuristic Search II 6
A* Properties
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 II 7
A* Properties
A* with an admissible heuristic is about to expand a goal node → it has found a lowest-cost path to it
Not true for non-goal nodes
What is the problem?
f values rise but then fall along a path
thus a path looks worse (higher f) than it really is (lower f)
CMPUT 366 F20: Heuristic Search II 8
A* Properties
Why is reaching a node through a suboptimal path a problem? Cannot use multiple-path prunning since we can inadvertly remove a better path later. Lose A* optimality.
Solution:
make sure A* expands any node via an optimal path
prevent f values from falling along a path make the heuristic consistent:
∀(n, n2) ∈ E [|h(n) − h(n2)| ≤ cost(n, n2)]
With a consistent 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 II 9
A* Properties
Space complexity: O(bm) Time complexity: O(bm)
Why not use Lowest-Coast First Search (LCFS) instead?
CMPUT 366 F20: Heuristic Search II 10
Iterative Deepening A*
Iterative deepening (an earlier 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 II
11
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 II
12
Problems with Search Algorithms So Far
All search algorithms so far were off-line and bird’s eye an agent sits in place computing a solution in its head then blindly executes the solution computed
Problems?
per action limit (e.g., driving)
needs to know the whole search graph a priori dynamic world (e.g., other agents)
CMPUT 366 F20: Heuristic Search II 13
Agent-Centered Search
search is centered on an agent
agent interleaves planning and plan execution (i.e., acting) agent updates its knowledge of the world as it moves about agent can access the world around its current state
agent has bounded memory (less than the world)
CMPUT 366 F20: Heuristic Search II 14
Any of the Search Algorithms so far for Agent-centered Search?
in break-out rooms discuss:
how you would adapt any of the algorithms presented so far to an agent-centered
setting
focus on limited time for planning:
how would we make, say, A* time-bounded?
CMPUT 366 F20: Heuristic Search II 15
Real-time Heuristic Search
The problem with time-bounded A* is that it losses completeness when its planning time is bounded
inaccuracies in the heuristic can lead the search astray An alternative?
Complement planning with (heuristic) learning Satisfies:
search is centered on an agent
agent interleaves planning and plan execution (i.e., acting) agent updates its knowledge of the world as it moves about agent can access the world around its current state
agent has bounded memory (less than the world)
CMPUT 366 F20: Heuristic Search II 16
Learning Real-time A* (LRTA*)
Until in a goal state do 1. lookaround
2. compute the f of each neighbor 3. move to the lowest-f neighbor
Hill-climbing
What is the problem?
incomplete – get stuck in dead-ends (heuristic depressions)
CMPUT 366 F20: Heuristic Search II 17
Learning Real-time A* (LRTA*)
Until in a goal state do 1. lookaround
2. compute the f of each neighbor
3. update the h of the current state with the lowest f among any neighbors 4. move to the lowest-f neighbor
Complete on finite, safely explorable graphs Satisfies:
search is centered on an agent
agent interleaves planning and plan execution (i.e., acting) agent updates its knowledge of the world as it moves about agent can access the world around its current state
agent has bounded memory (less than the world)
CMPUT 366 F20: Heuristic Search II 18