CS代考 FIT3080 1 / 31 - PowCoder代写

Heuristic Search
. University
Heuristic Search FIT3080 1 / 31

Uniform-Cost Search is awesome, right? 􏰀 Complete
􏰀 No duplicates (Graph-Search version) 􏰀 Best-first expansion order
􏰀 Usually much faster than depth-first or breadth-first
Heuristic Search
FIT3080 2 / 31

The problem with Uniform-Cost Search
Not yet reached
UCS has no idea where the target is. It’s searching blindly.
Heuristic Search
FIT3080 3 / 31

Informed Search
We say an algorithm is informed if it relies on problem-specific knowledge that helps us decide which node to expand next.
One approach for making a search informed is to add a heuristic function — h(n) — that estimates cost-to-go: from any node n to the current goal.
Heuristic Search FIT3080 4 / 31

Heuristics, concretely
A heuristic is a function that satisfies the following essential properties: 􏰀 h(n) is an estimate of the true path cost, from n to t
Where do heuristics come from?
􏰀 Human knowledge of the domain
􏰀 From solving a relaxed version of the problem at hand. 􏰀 From prior experience
Heuristic Search
FIT3080 5 / 31

Greedy Best-First Search
Idea: the heuristic value h(n) is the priority of each node.
Here we use a heuristic called Manhattan distance: hM (n) = ∆x + ∆y
Heuristic Search FIT3080 6 / 31

Greedy Best-First Search
Idea: the heuristic value h(n) is the priority of each node.
At each step, we expand the most promising node according to hM.
Heuristic Search FIT3080 6 / 31

Greedy Best-First Search
Idea: the heuristic value h(n) is the priority of each node.
For this problem, hM is a perfect guide and the search cost is minimal.
Heuristic Search FIT3080 6 / 31

The Problem with Greedy Best-First Search
In this example we seek an optimal path from a to h. b3a2c
a b c d e f g h i j
5 4.5 2.8 2 2.8 2 0 3 3.6
This time our heuristic is straight line distance hSLD =􏰁∆x2+∆y2
Heuristic Search
FIT3080 7 / 31

The Problem with Greedy Best-First Search
In this example we seek an optimal path from a to h. b3a2c
a b c d e f g h i j
5 4.5 2.8 2 2.8 2 0 3 3.6
Now GBFS becomes misleading and produces suboptimal results. In Tree-Search, expanding greedily may not even terminate!
Heuristic Search FIT3080 7 / 31

The A* Algorithm
Idea: let’s combine cost-so-far with cost-to-go. Nodes are now expanded according to minimum f-value where f (n) = g (n) + h(n)
Each f (n) is an estimate of the total solution cost: from s to t via node n.
snt NB: UCS and GBFS are both special cases of A*.
A* originally appears in (Hart, P.E., Nilsson, N.J. and Raphael, B., 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2), pp.100-107.)
Heuristic Search FIT3080 8 / 31

Searching with A*
In this example we seek an optimal path from a to h.
Node hSLD estimate a4 b5
45d c4.5
d 2.8 e2 f 2.8 g2
Expanding: Open: [ (a, 4)
Heuristic Search
FIT3080 9 / 31

Searching with A*
In this example we seek an optimal path from a to h.
Node hSLD estimate a4 b5
45d c4.5
d 2.8 e2 f 2.8 g2
Expanding:
Open: [ (c, 6.5), (b, 8) ]
Heuristic Search
FIT3080 9 / 31

Searching with A*
In this example we seek an optimal path from a to h.
Node hSLD estimate a4 b5
45d c4.5
d 2.8 e2 f 2.8 g2
Expanding:
Open: [ (d, 6.8), (b, 8) ]
Heuristic Search
FIT3080 9 / 31

Searching with A*
In this example we seek an optimal path from a to h.
Node hSLD estimate a4 b5
45d c4.5
d 2.8 e2 f 2.8 g2
(e, 8), (b, 8) ]
Expanding: Open: [
Heuristic Search
FIT3080 9 / 31

Searching with A*
In this example we seek an optimal path from a to h.
Node hSLD estimate a4 b5
45d c4.5
d 2.8 e2 f 2.8 g2
(b, 8), (f, 10.8) ]
Expanding: Open: [
Heuristic Search
FIT3080 9 / 31

Searching with A*
In this example we seek an optimal path from a to h.
Node hSLD estimate a4 b5
45d c4.5
d 2.8 e2 f 2.8 g2
(h, 8), (i, 10), (f, 10.8) ]
Expanding: Open: [
Heuristic Search
FIT3080 9 / 31

Searching with A*
In this example we seek an optimal path from a to h.
Node hSLD estimate a4 b5
45d c4.5
d 2.8 e2 f 2.8 g2
(i, 10), (f, 10.8) ]
Expanding: Open: [
Heuristic Search
FIT3080 9 / 31

Let’s compare Uniform Cost Search (aka. Dijkstra’s algorithm) with A*. https://www.movingai.com/SAS/ASM/
􏰀 Here we solve pathfinding problems on 8-connected gridmaps.
􏰀 Diagonal moves are allowed.
􏰀 The heuristic is octile distance √
hoct = arg min(∆x, ∆y) × 2 + arg max(∆x, ∆y) − arg min(∆x, ∆y)
Heuristic Search FIT3080 10 / 31

The Tree-Search version of A* can be effectively combined with iterative deepening. Similar to DFID but now we search with f -costs.
IDA* sketch:
1. Depth-first tree-search with a cost limit (initially flim = h(start))
2. Compute for each generated node an f -value estimate: f (n) = g + h 3. Expand all nodes with f (n) ≤ flim
4. Update flim to min. f -value of any node generated but not expanded. 5. Repeat 1-4 until the goal is found or until the tree is exhausted.
Heuristic Search FIT3080 11 / 31

Let’s see how IDA* works https://www.movingai.com/SAS/IDA/
􏰀 Here we solve a 3×2 sliding tile puzzle
􏰀 The heuristic is sum of Manhattan distances.
􏰀 NB: The demo will show the entire tree, then the traversal.
Heuristic Search FIT3080 12 / 31

Two important heuristic properties
Admissibility: the heuristic never over-estimates the cost-to-go:
h(n) ≤ h∗(n) where h∗(n) is the true cost from n to t.
Heuristic Search FIT3080 13 / 31

Two important heuristic properties
Consistency:
heuristic estimates decrease monotonically from n to t. t
h(n) ≤ c(n, n′) + h(n′) | n′ ∈ Successors(n)
Any consistent heuristic is also admissible. This includes hSLD and hM .
Heuristic Search FIT3080 13 / 31

Optimality of A* (Graph-Search) Theorem
Graph-Search A* is complete and optimal if its heuristic is consistent.
􏰀 The Open list covers every path to the target
􏰀 Every graph node, including the goal, is eventually expanded
􏰀 Along any path f -values are non-decreasing (due to consistency)
􏰀 When A* selects a node n for expansion g(n) is the optimal path cost, from s to n.
Heuristic Search FIT3080 14 / 31

Inconsistent Heuristics
For any node n and successor n′: we say the heuristic h is inconsistent if |h(n) − h(n′)| > c(n, n′)
h(a) = 1 a
Inconsistent heuristics lead to re- expansions for optimal A* in graphs.
The news is not all bad and inconsistent heuristics are often useful in practice. See (Felner, A., Zahavi, U., Holte, R., Schaeffer, J., Sturtevant, N., & Zhang, Z. (2011). Inconsistent heuristics in theory and practice. Artificial Intelligence, 175(9-10))
Heuristic Search FIT3080 15 / 31

Inconsistent Heuristics
For any node n and successor n′: we say the heuristic h is inconsistent if |h(n) − h(n′)| > c(n, n′)
In trees, A* search generates all paths to each node. Here admissibility is sufficient to guarantee optimality.
The news is not all bad and inconsistent heuristics are often useful in practice. See (Felner, A., Zahavi, U., Holte, R., Schaeffer, J., Sturtevant, N., & Zhang, Z. (2011). Inconsistent heuristics in theory and practice. Artificial Intelligence, 175(9-10))
Heuristic Search FIT3080 15 / 31

Informedness
Heuristic h1 is less informed than heuristic h2 iff for all non-goal nodes n we have h1(n) < h2(n). Heuristic h2 dominates heuristic h1 iff for all non-goal nodes n we have h2(n) ≥ h1(n). 􏰀 More informed heuristics are better (less expansions, faster search). 􏰀 The value |h(n) − h∗(n)| ≥ 0 is called the heuristic error. Heuristic Search FIT3080 16 / 31 Informedness (2) 9 7 7 7 8 9 9 9.0 9 7 7 7 6 6 9 8.1 9777779 7.4 9 77779 8.77.1 9 9 9 9 9 9 8.4 On 4-connected gridmaps hM dominates hSLD. 8 9.0 9.0 6 6 9.0 9.0 8.2 7.5 8.1 9.0 Heuristic Search FIT3080 17 / 31 So, how good is A* really? A* is optimally efficient. This means there exists no algorithm A which is less informed than A* and that can possibly expand fewer nodes. SupposethereexistsanalgorithmAh1 thatisismorecleverthanA∗h2 despite h1 being less informed than h2. That means there exists some node n where: 􏰀 fh1 (n) ≥ fh2 (n) (Ah1 doesn’t expand n) 􏰀 Implies h1(n) ≥ h2(n) 􏰀 But h1 is less informed than h2 (contradiction) The optimal efficiency of A* holds up to tie-breaking Heuristic Search FIT3080 18 / 31 Tie Breaking Sometimes many nodes have the same f -value. How to decide which node to expand next? Expanded Generated Not yet reached 2+7 6+3 1+8 5+4 1+8 2+7 3+6 4+5 5+4 Heuristic Search FIT3080 19 / 31 Tie Breaking Sometimes many nodes have the same f -value. How to decide which node to expand next? Expanded Generated Not yet reached 3+6 66 2+7 1+8 2+7 3+6 4+5 5+4 One good strategy: choose the node with smallest h-value (= largest-g) Heuristic Search FIT3080 19 / 31 Tie Breaking with zero-cost actions The smallest-h strategy fails when we allow zero cost actions. In this problem we assign paths to agents and need to cover every target. The objective is makespan: minimise the task completion time. Heuristic Search FIT3080 20 / 31 Tie Breaking with zero-cost actions The smallest-h strategy fails when we allow zero cost actions. These two solutions have the same cost (and h-value) under makespan. Other ideas: [h, lifo], [h, fifo], [h, rand], [. . .]. None are dominant. Heuristic Search FIT3080 20 / 31 Tie Breaking (3) How important is tie-breaking, really? Some results on IPC benchmarks. From the paper (Asai, Masataro, and . ”Tie-breaking strategies for cost-optimal best first search.” Journal of Artificial Intelligence Research 58 (2017)) Heuristic Search FIT3080 21 / 31 Tie Breaking (3) How important is tie-breaking, really? Some results on IPC benchmarks. From the paper (Asai, Masataro, and . ”Tie-breaking strategies for cost-optimal best first search.” Journal of Artificial Intelligence Research 58 (2017)) Heuristic Search FIT3080 21 / 31 A* performance characteristics In general: 􏰀 For any dominant heuristic h there exists a class of A* algorithms A∗h. 􏰀 Each A∗h ∈ A∗h is differentiated from the rest by tie-breaking. 􏰀 How to choose the one that always gives optimal efficiency in general is an open problem. Bottom line: 􏰀 A* has the same worst-case performance as UCS. 􏰀 With a good heuristic, A* can be much more efficient in practice. 􏰀 Many of the currently leading planners employ some type of A* search. Heuristic Search FIT3080 22 / 31 Improvements for A* A variety of approaches exist for improving the performance of optimal A*. 􏰀 Better data structures for maintaining Open and Closed 􏰀 More accurate heuristics. 􏰀 Reducing the size of the search space via abstraction 􏰀 Constraint-based pruning (feasibility cuts, symmetry cuts etc) Heuristic Search FIT3080 23 / 31 Improvements for A* A variety of approaches exist for improving the performance of optimal A*. 􏰀 Better data structures for maintaining Open and Closed 􏰀 More accurate heuristics. 􏰀 Reducing the size of the search space via abstraction 􏰀 Constraint-based pruning (feasibility cuts, symmetry cuts etc) We can just give up on optimality. Heuristic Search FIT3080 23 / 31 Relaxing the optimality criterion We don’t always need optimal solutions. Sometimes a near optimal or even a feasible solution is enough. Types of suboptimality guarantees: 􏰀 Incomplete, unbounded (very fast, might fail) 􏰀 Complete, unbounded (very fast, variable solution quality) 􏰀 Bounded suboptimal (fast, solutions have quality guarantees) 􏰀 Relative suboptimality (guarantee: C ≤ w × C∗) 􏰀 Additive suboptimality (guarantee: C ≤ δ + C∗) In this lecture we only discuss relative suboptimality. But additive suboptimality algorithms are interesting and useful! See: (Valenzano, R.A., Arfaee, S.J., Thayer, J., Stern, R. and Sturtevant, N.R., ”Using alternative suboptimality bounds in heuristic search.” Twenty-Third International Conference on Automated Planning and Scheduling. 2013.) Heuristic Search FIT3080 24 / 31 Weighted A* Multiply A* heuristic estimates by some factor w ≥ 1. ABCDEFGHI Ground (cost = 1) Bridge (cost = 1) Water (cost = 6) 1 2 3 4 5 6 7 Multi-terrain gridmap (4c). Our estimator is w × hM with w = 2. Heuristic Search FIT3080 25 / 31 Weighted A* Multiply A* heuristic estimates by some factor w ≥ 1. ABCDEFGHI Ground (cost = 1) Bridge (cost = 1) Water (cost = 6) 1 2 3 4 5 6 7 Minimum f-value = 9 Heuristic Search FIT3080 25 / 31 Weighted A* Multiply A* heuristic estimates by some factor w ≥ 1. ABCDEFGHI Ground (cost = 1) Bridge (cost = 1) Water (cost = 6) 1 2 3 4 5 6 7 Minimum f-value = 12 Heuristic Search FIT3080 25 / 31 Weighted A* Multiply A* heuristic estimates by some factor w ≥ 1. ABCDEFGHI Ground (cost = 1) Bridge (cost = 1) Water (cost = 6) 1 2 3 4 5 6 7 Minimum f-value = 13 Heuristic Search FIT3080 25 / 31 Weighted A* Multiply A* heuristic estimates by some factor w ≥ 1. ABCDEFGHI Ground (cost = 1) Bridge (cost = 1) Water (cost = 6) 1 2 3 4 5 6 7 Minimum f-value = 14 Heuristic Search FIT3080 25 / 31 Weighted A* Multiply A* heuristic estimates by some factor w ≥ 1. ABCDEFGHI Ground (cost = 1) Bridge (cost = 1) Water (cost = 6) 1 2 3 4 5 6 7 Minimum f-value = 15 Heuristic Search FIT3080 25 / 31 Weighted A* Multiply A* heuristic estimates by some factor w ≥ 1. ABCDEFGHI Ground (cost = 1) Bridge (cost = 1) Water (cost = 6) 1 2 3 4 5 6 7 Minimum f-value = 16 Heuristic Search FIT3080 25 / 31 Weighted A* Multiply A* heuristic estimates by some factor w ≥ 1. ABCDEFGHI Ground (cost = 1) Bridge (cost = 1) Water (cost = 6) 1 2 3 4 5 6 7 Minimum f-value = 17 Heuristic Search FIT3080 25 / 31 Weighted A* Multiply A* heuristic estimates by some factor w ≥ 1. ABCDEFGHI Ground (cost = 1) Bridge (cost = 1) Water (cost = 6) 1 2 3 4 5 6 7 Minimum f-value = 16 Heuristic Search FIT3080 25 / 31 Weighted A* Multiply A* heuristic estimates by some factor w ≥ 1. ABCDEFGHI Ground (cost = 1) Bridge (cost = 1) Water (cost = 6) 1 2 3 4 5 6 7 Minimum f-value = 15 Heuristic Search FIT3080 25 / 31 Weighted A* Multiply A* heuristic estimates by some factor w ≥ 1. ABCDEFGHI Ground (cost = 1) Bridge (cost = 1) Water (cost = 6) 1 2 3 4 5 6 7 WA* solution (cost = 15) Heuristic Search FIT3080 25 / 31 Weighted A* Multiply A* heuristic estimates by some factor w ≥ 1. ABCDEFGHI Ground (cost = 1) Bridge (cost = 1) Water (cost = 6) 1 2 3 4 5 6 7 A* solution (cost = 13) Heuristic Search FIT3080 25 / 31 Pros and Cons of WA* The bad news: 􏰀 Heuristic estimates might overestimate the cost-to-go (inadmissible). 􏰀 Heuristic estimates might also be inconsistent. The good news: 􏰀 Search now progresses more quickly toward the goal. 􏰀 We obtain feasible solutions sooner. 􏰀 Solution cost guaranteed: at most w-times larger than optimal. 􏰀 Re-expansions are not required to achieve the guarantee. Heuristic Search FIT3080 26 / 31 Bounded guarantee of Weighted A* Theorem Let f (n) = g (n) + w × h(n) be the estimate for any generated node, with h admissible and w ≥ 1. Then, any returned solution has a cost C ≤ w × C∗ Base case (n = s): trivially true. Inductive case: On termination the goal node G may still have an optimal ancestor n on the Open list. We have: 1. f (G ) ≤ f (n) (since G was expanded first) 2. f (n) = g(n) + w × h(n) (by definition) 3. g(n) + w × h(n) ≤ w × (g(n) + h(n)) (because algebra) 4. w × (g(n) + h(n)) ≤ w × C∗ (since f (n) is an underestimate) 程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts