Heuristic Search Algorithms

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson
Download our mobile app to listen on the go
Get App

Questions and Answers

In the context of search algorithms, what is a heuristic function designed to estimate?

How close a state is to a goal.

Explain why using the actual cost as the heuristic in A* search might not be practical, despite its accuracy.

Calculating the actual cost is computationally expensive and defeats the purpose of using a heuristic, which is to provide a quick estimate.

Describe the key difference in how Uniform-Cost Search (UCS) and A* Search expand nodes, particularly in terms of direction.

UCS expands equally in all directions, while A* expands mainly towards the goal, adjusting for optimality.

What are relaxed problems are and how are used when creating admissible heuristics?

<p>A 'relaxed problem' simplifies the original problem by removing constraints, making it easier to solve. The optimal solution cost of this relaxed problem can provide an admissible heuristic for the original, more constrained, problem.</p> Signup and view all the answers

Explain the intuition behind why admissibility is a desired property for heuristics in A* search.

<p>Admissibility ensures that A* does not overestimate the cost to reach the goal, guaranteeing that when a goal is reached, it is the optimal path.</p> Signup and view all the answers

In A* search, what are the backward and forward costs, and how does A* make use of them?

<p>Backward costs, represented by <code>g(n)</code>, are the costs to reach the current node from the start node. Forward costs, represented by <code>h(n)</code>, are the estimated costs to reach the goal from the current node. A* uses both to evaluate nodes.</p> Signup and view all the answers

Describe a scenario where Greedy Search might fail to find the optimal path to a goal.

<p>Greedy Search might be 'lured' down a path that appears to immediately reduce the distance to the goal, but which ultimately leads to a longer or more costly route.</p> Signup and view all the answers

In A* search, under what condition is it safe to terminate the search once a goal node is enqueued?

<p>It is not generally safe. A* should terminate only when a goal node is dequeued, ensuring that an optimal path has been found and proven.</p> Signup and view all the answers

What is the key difference between Tree A* and Graph A* in terms of optimality guarantees?

<p>Tree A* is optimal with an admissible heuristic, while Graph A* is optimal with a consistent heuristic.</p> Signup and view all the answers

Explain what it means for a heuristic to be 'consistent.' How does consistency relate to admissibility?

<p>Consistency implies that the estimated cost from node A to the goal is no more than the cost to reach a neighbor C plus the estimated cost from C to the goal. A consistent heuristic is also admissible.</p> Signup and view all the answers

In the context of search algorithms, explain what is meant by the term 'fringe'.

<p>The 'fringe' refers to the collection of nodes that are available for expansion in a search algorithm.</p> Signup and view all the answers

How is the best path determined in Greedy Search, and what is the primary factor influencing path selection at each step?

<p>Greedy Search determines the best path by expanding the node that appears closest to the goal. The primary factor is the estimated distance (or cost) to the goal from the current node.</p> Signup and view all the answers

What is the formula that A* Search uses to determine the priority of nodes in the fringe, and what does each component of the formula represent?

<p>A* Search uses the formula <code>f(n) = g(n) + h(n)</code>. <code>g(n)</code> represents the cost to reach the node <code>n</code> from the start, and <code>h(n)</code> represents the estimated cost to reach the goal from node <code>n</code>.</p> Signup and view all the answers

Why might an admissible heuristic still result in a suboptimal search process, even though it guarantees an optimal solution?

<p>An admissible heuristic might lead to exploring more nodes because its estimates are too optimistic, causing A* to explore many paths that ultimately lead to the goal.</p> Signup and view all the answers

In the context of search problems, what is the significance of search operating over 'models' of the world, and what are the implications of this?

<p>Search algorithms operate on simplified representations, not reality, affecting planning effectiveness. The search is only as good as the models.</p> Signup and view all the answers

How can admissible heuristics be used in situations where an optimal solution is not strictly required?

<p>While formally designed for optimal solutions, admissible heuristics can be useful because as heuristics get closer to the true cost, you will expand fewer nodes but usually do more work per node to compute the heuristic itself</p> Signup and view all the answers

Describe when the number of misplaced tiles in the 8-puzzle can be used for the search heuristic?

<p>The tile must be misplaced and heuristic must be admissible.</p> Signup and view all the answers

Explain how you can identify an algorithm is A* Search?

<p>It combines uniform-cost to orders path cost, or backward cost <code>g(n)</code> and Greedy search to orders by goal proximity, or forward cost <code>h(n)</code>.</p> Signup and view all the answers

Provide a brief comparison of the effectiveness of Uniform Cost Search vs. greedy algorithm in A* Search?

<p>Uniform-cost expands equally in all directions and Greedy search expands node that seems closest by goal proximity.</p> Signup and view all the answers

A* uses both backward costs and (estimates of) forward costs. What is the relationship between them?

<p>The sum must be admissible and consistant based on the heuristics.</p> Signup and view all the answers

Explain why A* Tree search is optimal.

<p>A is an optimal goal node, B is a suboptimal goal node and h is admissible, A will exit the fringe before B,</p> Signup and view all the answers

What must happen to demonstrate why an A* search to be optimal?

<p>All ancestors of A must expand before B, and A must expands before B.</p> Signup and view all the answers

When can the same proof show that UCS is optimal?

<p>When the heuristic <code>h=0</code>.</p> Signup and view all the answers

Are all search algorithms conceptually only priority queues, collection only for nodes with attached priorities and what do they depend on?

<p>Yes, it depends on the fringe strategies.</p> Signup and view all the answers

What does A* search rely on to be good?

<p>The search depends on the models and you must have a key heuristics.</p> Signup and view all the answers

How does the idea of admissible heuristic relate to the 8 puzzle?

<p>Heuristics are created by number of tiles misplaced, being a relaxed-problem heuristic or distance away from goal.</p> Signup and view all the answers

Explain how admissible heuristic in 8 tiles are the solutions to relaxed problems, making the actions available??

<p>It's often a simpler version, it's the new actions are available. To make it admissible, all the new actions need to give an answer that is less than, and optimistic to the answer.</p> Signup and view all the answers

Under what circumstance would an AI program use Graph Search?

<p>Graph Search will be optimal with a consistent heuristic.</p> Signup and view all the answers

Why would you save on number of expanded nodes during A* search?

<p>The numbers can be save by nodes based on admissibility.</p> Signup and view all the answers

True or False and explain. Tile 5 and 6 can switch to solve the 8 Puzzle program, will the heuristic be admissible.

<p>False, because heuristics break optimality by trapping good plans on the fringe.</p> Signup and view all the answers

Should A* stop when you find itself enqueue a goal?

<p>No, only stop when we dequeue a goal.</p> Signup and view all the answers

Name any two examples of search programs or functions, with each example, name their respective heuristic.

<p>Manhattan and Eucildean distance.</p> Signup and view all the answers

What is the difference in what a heuristic is designed for with both Informed search with an Uninformed search

<p>The goal of a heuristic is based on being efficient and design it to solve a search problem.</p> Signup and view all the answers

How does A* determine optimality to guarantee the search is finished.

<p>We need estimates to be less than actual costs!</p> Signup and view all the answers

When should A* stop using an enqueue?

<p>A* does not use enqueues.</p> Signup and view all the answers

The 8-puzzle tiles can be solved when all of the tiles do what to move from state to state?

<p>When all the tiles ignore each other and can slide anyway.</p> Signup and view all the answers

What are the factors of the quality of work node?

<p>Quality depends admissibility, trade offs can depend on the work.</p> Signup and view all the answers

When using consistency, what should happen to "f" values along the path.

<p>They should never decreases with with cost added, A* graph search is optimal.</p> Signup and view all the answers

In the 8-puzzle tile, how can you keep track and avoid using the 8 tile as an ADT list?

<p>All depends on the collection of collection priority queues of nodes and attached priorities.</p> Signup and view all the answers

How does DFS/BFS practically avoid overhead?

<p>They using stacks and queues, while a program can code an implementation and takes a variable queueing object.</p> Signup and view all the answers

When using Models to simulate algorithms, are they used to simulate in the real world or in their own enviroment?

<p>Algorithms are the simulated enviroment.</p> Signup and view all the answers

Flashcards

What is a heuristic?

A function that estimates how close a state is to a goal; designed for a particular search problem.

What is Greedy Search?

Expands the node that seems closest to the goal based on the heuristic.

What is Uniform-cost search?

Orders nodes by path cost, or backward cost g(n).

What does Greedy search order by?

Orders by goal proximity, or forward cost h(n).

Signup and view all the flashcards

What is A* Search?

Orders by the sum of path cost and goal proximity: f(n) = g(n) + h(n).

Signup and view all the flashcards

What is an admissible heuristic?

A heuristic is admissible if it never overestimates the true cost to a nearest goal (optimistic).

Signup and view all the flashcards

What is the main idea of estimated heuristic costs?

Estimated heuristic costs are less than or equal to actual costs.

Signup and view all the flashcards

When is Graph A* optimal?

With a consistent heuristic, Graph A* is optimal

Signup and view all the flashcards

How planning works

The agent doesn't actually try all the plans out in the real world. Planning is all “in simulation".

Signup and view all the flashcards

What does A* use?

A* uses both backward costs and (estimates of) forward costs

Signup and view all the flashcards

Study Notes

  • A heuristic estimates how close a state is to a goal.
  • Heuristics are designed for particular search problems and examples include Manhattan distance and Euclidean distance for pathing.
  • Informed search strategies include heuristics, greedy search, A* search and graph search.

Heuristic functions

  • The straight-line distance to Bucharest from various cities are:
    • Arad (366), Bucharest (0), Craiova (160), Dobreta (242), Eforie (161), Fagaras (178), Giurgiu (77), Hirsova (151), Iasi (226), Lugoj (244), Mehadia (241), Neamt (234), Oradea (380), Pitesti (98), Rimnicu Vilcea (193), Sibiu (253), Timisoara (329), Urziceni (80), Vaslui (199), Zerind (374).
  • In greedy search, the node expanded is the one that seems closest to the goal.
  • A greedy search strategy expands a node believed to be closest to the goal state, using a heuristic to estimate the distance to the nearest goal.
  • Greedy search is not optimal because the resulting path to Bucharest may not be the shortest.
  • It can get stuck or take a badly-guided path.
  • Uniform-cost search orders by path cost (backward cost).
  • Greedy search orders by goal proximity (forward cost).
  • A* Search orders by the sum of path cost and goal proximity: f(n) = g(n) + h(n).
  • With A* search, termination should occur when you dequeue a goal, not when you enqueue it.

A* Optimality

  • Actual bad goal cost can be less than estimated good goal cost and estimated costs need to be less than actual costs for optimality.

Admissible heuristics

  • Admissible heuristics are optimistic and therefore slow down bad plans but never outweigh true costs.
  • A heuristic h is admissible if 0 ≤ h(n) ≤ h*(n), where h*(n) is the true cost to the nearest goal.
  • Coming up with admissible heuristics is a significant part of using A* in practice.
  • If A is an optimal goal node, B is a suboptimal goal node and h is admissible, then A will exit the fringe before B.
  • In A* tree search, imagine B is on the fringe.
  • Some ancestor n of A is on the fringe too (maybe A!).
  • n will be expanded before B because f(n) is less or equal to f(A) and f(A) is less than f(B).
  • All ancestors of A expand before B, A expands before B and A* search is optimal.

UCS vs A*

  • Uniform-cost search expands equally in all directions.
  • A* search expands mainly toward the goal and hedges it bets to ensure optimality.

Creating Admissible Heuristics

  • Most of the work in solving hard search problems optimally is in coming up with admissible heuristics.
  • Admissible heuristics are often solutions to relaxed problems, where new actions are available.
  • Inadmissible heuristics can also be useful.

8 Puzzle

  • An example of a problem is the 8-puzzle where:
    • The states are the arrangement of tiles, and how many there are.
    • The actions possible are based on the space on the board.

8 Puzzle I

  • A possible heuristic for the 8 puzzle is the number of tiles misplaced.
  • The minimum number of steps is h(start) =8
  • 112 nodes need to be expanded to find a solution where the optimal path has four steps, 6,300 nodes when it has 8 steps and 3.6x nodes when it has 12 steps
  • This type of problem is relaxed problems

8 Puzzle II

  • In an easier 8-puzzle, any tile could slide any direction at any time, ignoring other tiles.
  • An admissible heuristic could be the Total Manhattan distance, with an average of 13 nodes expanded for 4 steps, 39 for 8 steps, and 227 for 12 steps. The minimum number of steps is h(start) = 3 +1+2+ = 18 ...

8 Puzzle III

  • Using the actual cost as a heuristic:
    • It is admissible.
    • It saves on nodes expanded.
    • The problem is the increase in work needed.
  • There is a trade-off between quality of estimate and work per node; as heuristics get closer to the true cost, you expand fewer nodes, but more work per node is done to compute the heuristic itself.

Consistency of Heuristics

  • The main idea is that estimated heuristic costs are less than or equal to actual costs.
  • Admissibility means heuristic cost ≤ actual cost to goal.
  • Consistency means heuristic "arc" cost ≤ actual cost for each arc (h(A) – h(C) ≤ cost(A to C)).
  • Consequences of consistency: The f value along a path never decreases (h(A) ≤ cost(A to C) + h(C)) and A* graph search is optimal.
  • Tree A* is optimal with an admissible heuristic.
  • Graph A* is optimal with a consistent heuristic.
  • With h=0, the same proof shows that UCS is optimal.

Search and Models

  • Search operates over models of the world.
  • The agent doesn't actually try all the plans out in the real world.
  • Planning is all in simulation.
  • Your search is only as good as your models.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Related Documents

More Like This

Use Quizgecko on...
Browser
Open
Browser
Browser