Informed Search, Heuristics and A*

Informed Search and Heuristics

• The lecture discusses informed search and heuristics, best first (greedy) search, and the A* algorithm.
• The concepts of A* admissibility and map traversal with A* are covered.
• The lecture goes over implementing A* and reconstructing the solution path, followed by a recap.

Quiz Details

• The upcoming quiz consisting of 12 multiple choice questions and 3 free-text questions.
• There is a Mock test which contains examples of the multiple choice questions.

Free Text Questions for 8-Puzzle

• An example free-text question involves designing a search engine for the 8-puzzle game.
• The puzzle's configuration must be stored in a 3x3 int array, using '0' to indicate the gap.
• The task involves describing how to implement the getSuccessor() method, ensuring all possible next moves are added to the list of successor states, even at edge cases.
• When answering the free text question, make sure you have all the details of the algorithm.
• Describe the specifics that should happen in the getSuccessor codes
• Make a clear distinction between a state and a node
• Avoid using imprecise language

Map Traversal and Heuristics

• A Map Traversal search algorithm without heuristics is "blind" to the parts of the map it hasn't explored.
• Algorithms only know the cost/distance of expanded nodes without knowing if they are useful choices.
• Heuristics estimate the distance to the goal from each node

Guiding the Search

• Branch-and-bound searches expand effort equally in all directions.
• Knowledge guiding search comes from estimating the remaining cost to the goal from any node n.
• A SearchState may contain a variable estRemCost which the user has to supply to the application
• In map traversal, this could be the straight-line distance to the goal.
• Only estimates, not true costs, are used for this
• Searching is pointless if the true costs are already known!

Greedy Search / Best First Search

• A Best-First search strategy selects the node with the minimum estRemCost from open, i.e., the node closest to a goal.
• This makes it a greedy algorithm which makes use of the heuristics whilst ignoring the global cost with potentially lucky and great estimates if so.
• It is not admissible

A* Algorithm Overview

• The A* Algorithm is a state space searching that combines Branch-and-Bound and Best-First (Greedy) approaches.
• A* select a node n from open with minimum estimated cost h(n) of path from start to goal through n, where h(n) = g(n) + f(n).
  • g(n) is the cost from start to n, and f(n) estimates the remaining cost from n to the goal.
• It was first discovered by Peter Hard, Nils Nilsson and Bertram Raphael, working at the Stanford Research Institute (1968)

A* Algorithm Characteristics

• A* is admissible if all f(n) (estRemCosts) are guaranteed to be underestimates.
• The known distance along a complete, non-optimal path will not be less than an underestimate of the distance along the incomplete, optimal path, hence the correct path cannot be selected from open.
• There are limiting cases to improve efficiency and accuracy.
  • If all estimates are 0 (or identical), A* reduces to Branch-and-Bound.
  • If all the estimates are accurate A* is optimal and the better the estimates, the more efficient A* is.

Admissibility of A*

• When there are 2 competing routes to the goal; through X and through Y
  • Suppose the known cost of g(X)=110 and Estimated remaining cost f(X) to goal: 25 vs g(Y)=80 and Estimated remaining cost f(Y) to goal: 40
  • As long as estimates are underestimates

Node Selection Approaches from the Open List

• Search problems with variable costs affect how the currentNode is selected off the open list.
• Approaches include Depth-first (stack: last in, first out), breadth-first (queue: first in, first out), and lowest-cost-first (sorted by lowest g(x) first).
• A* uses an open list sorted by lowest h(x)=g(x)+f(x) first.

Search Algorithms

• Search algorithms include both uniformed and informed searches.
• Uninformed search examples: Breadth First Search, Depth First Search, Lower cost / Branch and Bound Search, and Progressive Deepening
• Informed search examples: Best First (Greedy) Search, and A* Search.

Implementing A*

• In the search4 code, changes were made and you can supply estRemCosts for each searchState.
• Additional changes made to selectNode(), and vetSucessors() as well

Nodes on closed

• Initially, place the node, X on open, before expanded it at anytime
• Once fully expanded, this will be placed on closed
• It won't resurface again

Implementing A* - What Happens on the Closed List?

• Node X is placed on open with parent A (cost 10, remaining cost 25)
• open now has X and B. X is expanded (remaining cost 30, not B which would be 55)
• X is moved to the closed list
• Later, a shorter route to X through B (40, remainder 5) emerges
• The node X has its parent and globalCost and totalCost, removed from closed and placed back on open.

Summary of Code Inspection

• Carta provides encapsulated access to the map specific data cities, links, local costs, and estimates.
• MapLink and Carta uses listings of MapLink instances, providing information about a link between two variables.
• MapState inherits from SearchState variables, and also contains city, localCostandestRemCost`.
• getSuccessors() in MapState uses the map information to find successors, and also keeps track of the localCost and estRemCost.

Solution Path Reconstruction

• It is often necessary to reconstruct the solution path
• The parent of each SearchNode must be recalled
• The parent will be "null" for the start node
• The expand() method from Search must be modified so that the parent of open nodes is now the currentNode
• When a search suceeds, you have to reconstruct the solution path, starting with the currentNode and working with closed, following the chain of parents until you get to the parent "null" node.
• The efficiency of the search can also be calculated with this