程序代做 COMP 424 - Artificial Intelligence Informed Search

COMP 424 – Artificial Intelligence Informed Search
Instructor: Jackie CK Cheung Readings: R&N Ch 3.5-3.7 (3rd ed); 3.5 – 3.6 (4th ed)

Announcements

• Midterm scheduled for Feb 18, 2022
• Online MyCourses Quiz; you’ll have 48 hours to complete;
designed to take ~80 minutes
• Final projects to be done in pairs
• Syllabus & office hours posted on Ed
• Quiz 1 will be posted by end of week
• Study guide information and first SG (you will have plenty of time to find a group and organize them)
• A1 will be posted early next week
COMP-424: Artificial intelligence 2

Overview of today’s class
• Using heuristics to inform (guide) the search
• Informed search algorithms
• Best-First (Greedy) Search
• Heuristic Search
• A* Search
• Learning heuristic functions
COMP-424: Artificial intelligence 3

Eight-Puzzle
How would you solve an eight-puzzle? Do you really perform an uninformed search as we discussed last class, or do some configurations seem more promising than others?
COMP-424: Artificial intelligence 4

Informed Search
• Uninformed search methods expand nodes based on distance from the start node, 𝑑(𝑛𝑠𝑡𝑎𝑟𝑡, 𝑛)
Easy: we always know that!
• What about expanding based on distance to the goal, 𝑑(𝑛, 𝑛𝑔𝑜𝑎𝑙)?
• If we know 𝑑(𝑛, 𝑛𝑔𝑜𝑎𝑙) exactly?
Easy: just expand the nodes that minimize 𝑑(𝑛, 𝑛𝑔𝑜𝑎𝑙)
• If we do not know 𝑑(𝑛, 𝑛𝑔𝑜𝑎𝑙) exactly, can we use intuition about this distance?
• We will call this intuition a heuristic 𝒉 𝒏 .
COMP-424: Artificial intelligence 5

• We are very close to the goal:
COMP-424: Artificial intelligence 6

Example: Travelling through Romania
What is good heuristic for path planning problems?
COMP-424: Artificial intelligence 7

Example heuristic: path planning
• What is a reasonable heuristic?
• The straight-line distance between two places.
• Is it always right?
• Clearly not – roads are rarely straight!
• But it’s roughly correct.
COMP-424: Artificial intelligence 8

Example heuristic: eight-puzzle
• What would be a good heuristic for this problem?
COMP-424: Artificial intelligence 9

Example heuristic: eight-puzzle
Two options: h1(𝑛) = number of misplaced tiles = 7 h2(𝑛) = total Manhattan distance
Which is better?
= (2+3+3+2+4+2+0+2) = 18
COMP-424: Artificial intelligence

Example heuristic: eight-puzzle
Two options: h1(𝑛) = number of misplaced tiles = 7 h2(𝑛) = total Manhattan distance
= (2+3+3+2+4+2+0+2) = 18
Which is better? Intuitively, h2(𝑛) seems better : varies more across state space and its estimate is closer to the true cost.
COMP-424: Artificial intelligence 11

Where do heuristics come from?
Possible strategies:
• Prior knowledge about the problem
• Exact solution to a relaxed version of the problem
• E.g., If rules of eight-puzzle are changed to allow a tile to move
anywhere. Then h1(𝑛) gives the exact distance to goal.
• E.g., If rules of eight-puzzle are changed to allow a tile to move to
any adjacent square. Then h2(𝑛) gives the exact distance to goal.
• Learning from prior experience
• More on this later
COMP-424: Artificial intelligence 12

Best-First Search
• Algorithm: expand the most promising node according to the heuristic.
• Example:
• What is the sequence of nodes visited in Best-First Search?
• What is the sequence of nodes visited in Uniform-Cost Search?
COMP-424: Artificial intelligence 13

Best-First Search
• Algorithm: expand the most promising node according to the heuristic.
• Example:
• What is the sequence of nodes visited in Best-First Search? START -> A -> C -> GOAL
• What is the sequence of nodes visited in Uniform-Cost Search? START -> A -> B -> C -> GOAL
COMP-424: Artificial intelligence 14

Best-First Search
• Algorithm: expand the most promising node according to the heuristic.
• If the heuristic is always 0, and we break ties by preferring shallowest depth, best-first search is the same as breadth- first-search.
• Best-first search contrasts with uniform-cost search: Uniform cost search considers the cost-so-far.
Best-first search considers the cost-to-go.
• Best-first search is a greedy method.
maximize short-term advantage without worrying about long-term consequences.
COMP-424: Artificial intelligence

Properties of Best-First Search
• In worst case: exponential time/space complexity (same as Breadth-First S).
O(bd) (b=branching factor, d=solution depth).
• A good heuristic can help a lot!
O(bd) space complexity (same as DFS).
• Completeness:
• Not always complete. Can get stuck in loops.
• Complete in finite spaces, if we check to avoid repeated states.
• Not optimal! (as seen in the example.) => Can we fix this? COMP-424: Artificial intelligence 16

Fixing Best-First Search
What’s the problem with best-first search?
• It is too greedy: does not take into account the cost so far!
Let’s use both of the following:
• Let 𝑔 be the cost of the path so far
• Let h be a heuristic function (estimated cost to go)
Heuristic search: best-first search, greedy with respect to 𝑓=𝑔+h
• Think of 𝑓 = 𝑔 + h as the estimate of the cost of the current path.
COMP-424: Artificial intelligence 18

Heuristic search
• Algorithm:
• At every step, take node 𝑛 from the front of the queue.
• Add to queue successors 𝑛’ with priorities: 𝑓(𝑛’) = 𝑔(𝑛’) + h(𝑛’)
• Terminate when a goal state is popped from the queue.
• Previous example:
COMP-424: Artificial intelligence 19

Priority queue: {(S,h(S))}
COMP-424: Artificial intelligence

Priority queue: {(S,h(S))} {(S,h(S)), (B,4), (A,7)}
{(S,h(S)), (B,4), (C,5), (A,7)}
{(S,h(S)), (B,4), (C,5), (A,7), (G,9)}
{(S,h(S)), (B,4), (C,5), (A,7), (G,8), (G,9)} Found!
Remark: Continue expanding nodes after goal is found if there are unexpanded nodes that have lower cost than current path to goal.
COMP-424: Artificial intelligence 22

Is heuristic search optimal?
• Example:
COMP-424: Artificial intelligence 23

Is heuristic search optimal?
• Example:
• Short answer: NO!
• In this example, any heuristic h(𝐴) > 2 leads to suboptimal
path (and if h(𝐴) = 2, it depends on tie breaking).
We must put conditions on the choice of heuristic to guarantee
optimality.
COMP-424: Artificial intelligence 24

Admissible heuristics
• Let h∗(𝑛) be the shortest path from n to any goal state.
• A heuristic h is called an admissible heuristic if:
h𝑛 ≤h∗ 𝑛,∀𝑛.
• Admissible heuristics are optimistic.
• Trivial case of an admissible heuristic: h 𝑛 = 0, ∀𝑛.
• In this case, we get uniform-cost search.
• If h is optimistic, we must have h(𝑠) = 0, 𝑠𝐺, the goal set.
COMP-424: Artificial intelligence 25

Examples of admissible heuristics
• Robot navigation? • 8-puzzle?
COMP-424: Artificial intelligence 26

Examples of admissible heuristics
• Robot navigation? straight-line distance to goal.
• 8-puzzle? h1: number of misplaced tiles.
h2: sum of Manhattan distances for each tile to its goal position.
• In general, if we get a heuristic by solving a relaxed version of the problem, we will obtain an admissible heuristic.
COMP-424: Artificial intelligence 27

• Algorithm: Heuristic search with an admissible heuristic.
• Let g be the cost of the path so far.
• Let h be an admissible heuristic function.
• Perform greedy search with respect to:
COMP-424: Artificial intelligence 28

Consistency
• An admissible heuristic h is called consistent (or monotone*) if for every state s and successor s’:
h(s)  c(s,s’) + h(s’).
• Think of h as getting “more precise” as it gets closer to the goal.
• This is a version of triangle inequality*, so heuristics that respect this inequality are metrics*.
• Consistency is a slightly stronger property than admissibility.
*Note: Look-up these terms if they are not familiar.
COMP-424: Artificial intelligence

Is A* complete?
• Suppose that the state space graph is finite, h is consistent, and all costs c(s,s’)>0.
• This implies that f cannot decrease along any path: f(s) = g(s) + h(s)  g(s) + c(s,s’) + h(s’) = f(s’)
• If a solution exists, it must have bounded cost.
• In this case, A* cannot get stuck in cycles, because the f-score of a re-expanded node will keep going up, eventually exceeding the solution’s.
• Hence, A* will have to find the solution! So, it is complete. Note:
• Non-decreasing path costs and c(s,s’)>0 mean that it is never necessary to re-expand a node, as the first time it is encountered by A* already gives you a lowest cost path to it.
COMP-424: Artificial intelligence 30

Fixing inconsistent heuristics
• Make a small change to A*:
Instead of 𝑓(𝑠’) = 𝑔(𝑠’) + h(𝑠’), use
𝑓(𝑠’) = max{ 𝑔(𝑠’) + h(𝑠’), 𝑓(𝑠) }
• With this change, 𝑓 is non-decreasing along any path, and
the previous argument applies.
COMP-424: Artificial intelligence 31

Is A* optimal?
• Proof by contradiction. Suppose a suboptimal goal G2 is in queue.
• Let n be an unexpanded node on a shortest path to optimal
• We have:
f(G2) = g(G2) since h(G2)=0
> g(G1) since G2 is suboptimal ≥ f(n) since h is admissible
• Since f(G2) > f(n), A* will select n for expansion before G2.
• Similarly, all nodes on the optimal path will be chosen before
G2, so G1 will be reached before G2.
COMP-424: Artificial intelligence 32

• If h2(𝑛) ≥ h1(𝑛), for all 𝑛 (both admissible), then h2 dominates h1
Intuition: h2(𝑛) is more informative than h1(𝑛)
• Eight-puzzle example:
Iterative depth search = 3,473,941 nodes A*(h1) = 539 nodes
A*(h2) = 113 nodes
Iterative depth search = too many nodes A*(h1) = 39,135 nodes
A*(h2) = 1,641 nodes
COMP-424: Artificial intelligence 33

• Complete!
• Optimal!
Properties of A*
• Exponential worst-case time/space complexity.
• But with a perfect heuristic, complexity is O(bd), because we only
expand nodes on optimal path.
• With a good heuristic, complexity is often sub-exponential.
• Optimally efficient: with a given h, no other optimal search algorithm is guaranteed to expand fewer nodes than A*.
• Technicality: up to tie-breaking
COMP-424: Artificial intelligence 34

Iterative Deepening A* (IDA*)
• Same trick as we used before to avoid memory problems.
• Algorithm is basically depth-first search, but using the f- value to decide in which order to consider the descendants of a node.
• Use an f-value limit, rather than a depth limit.
• IDA* has the same properties as A* but uses less memory.
• In order to avoid always expanding new nodes, old ones can be remembered if memory permits (this version is known as Simplified Memory-bounded A*, SMA*)
COMP-424: Artificial intelligence 36

Iterative Deepening A* example
• Set f1 = 4  only S, B are searched (no other nodes are put in the queue, because they exceed the cutoff threshold.)
• Set f2 = 8  now S, A, B, C, G, are all searched.
COMP-424: Artificial intelligence 37

Learning Heuristic Functions
• Can we automatically construct a better heuristic function for eight-puzzles?
• Idea: use previous experience of playing other eight- puzzles to help us learn h.
• Features that describe a particular state configuration
𝑥1(𝑛), 𝑥2(𝑛), …
• Form of heuristic function to be learned
h(𝑛) = 𝑐1𝑥1(𝑛) + 𝑐2𝑥2(𝑛)
• Target for the heuristic function
COMP-424: Artificial intelligence 38

• Actual cost to goal is 2.
• Let 𝑥1(𝑛) be number of misplaced tiles (= 2)
• 𝑥2 𝑛 be number of pairs of incorrectly adjacent tiles
• Pick𝑐 and𝑐 s.t.h𝑛 =𝑐𝑥 𝑛 +𝑐𝑥 𝑛 =2 121122
• Actually, we would try to fit an entire dataset of plays, not just this particular case.
COMP-424: Artificial intelligence 39

Summary of informed search
• Insight: use knowledge about the problem, in the form of a heuristic.
• The heuristic is a guess for the remaining cost to the goal.
• A good heuristic can reduce search time from exponential to
almost linear.
• Best-first search is greedy with respect to the heuristic, not complete and not optimal.
• Heuristic search is greedy with respect to f=g+h, where g is the cost so far and h is the estimated cost to go.
• A* is heuristic search where h is an admissible heuristic.
• A* is complete and optimal.
• A* is a key AI algorithm
COMP-424: Artificial intelligence 40

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts