Introduction to AI
Module 2: creating effective heuristics for search
creating effective heuristics
When you design your informed search implementation for a specific problem, it is important that you create effective heuristics or the informed search will not be any more efficient than uninformed search, nor will it find an optimal answer.
What makes a good heuristic?
When you design your heuristic, you want to make sure it is going to actually help make the search more efficient. Follow these guidelines to ensure h(n) is effective.

 Monotonic decreasing estimate to goal
 The heuristic should be 0 at the goal state
 Nearby states should have smaller values than states that are farther away
 Admissible heuristics are always optimistic: they think the real answer will be better than it is
 If you are using A*, it is important that your heuristic be admissible or A* may not give you the optimal answer
 Even if you are not using A*, try to ensure your heuristic is admissible as it will make your search more efficientAdmissible
 Note, while h(n) = 0 is an admissible heuristic, it is useless as it gives no information to the agent!
 Consistent
 If you are using A*, the heuristic must also be consistent, meaning it must satisfy the triangle inequality within your graphs.
 This is relatively easy to do if you are searching in a 2D space since you can use Euclidean distance or Manhatten distance (depending on your environment).
 While this is harder for more challenging environments, it is critical to ensuring A* always finds the shortest path to a node when that node is expanded.
 Provides useful information to the agent
 Note, while h(n) = 0 is an admissible heuristic, it is useless as it gives no information to the agent!
 Your heuristic should provide information to guide your agent towards the goal, as much as possible.
 Your heuristic needs to only require O(1) time to compute. If you require a search to return an answer within a search algorithm, it is not efficient!
 Reduces effective branching factor
 A good heuristic should provide sufficient information to reduce the effective branching factor (e.g. keep the agent from going down any nonpromising paths)
 To do this, it needs to be a nonzero value but not an overestimate (see admissible above)
 Monotonic decreasing estimate to goal
How to create a heuristic
Creating a heuristic in a nonEuclidean space can feel challenging. We offer some tips to help you to design effective heuristics.
 Save solutions to subproblems
 If a subproblem is easy to solve, store the solutions (and the cost) in a database and then use the cost of these solutions to estimate the final cost of the full problem.
 For example, break the problem into pieces. Perhaps your goal is to solve A and B. The subproblems are A and B separately. If the cost of A and B are known, you can add them together to estimate the full solution, assuming the subproblems are serializable, where the solution to A does not affect the solution to B. We will discuss this further in the planning module.
 Even if the subproblems are hard to solve, if you will be accessing their solutions over and over again (such as in map search), you could precompute the solutions and store those answers so the heuristics for the larger problems are effective.
 Landmarks
 Pick some landmark verticies on the search graph
 Fully compute and save the solution from those nodes
 Use the estimate of how to get to those nodes plus the solution from those nodes to estimate h() from other nodes
 Pick your landmarks to be spread far apart in the graph
 Featurebased heuristics
 If you know something about the problem you are trying to solve, you could create a set of features to summarize the state space
You could then create a function that weights each feature f(n) = w_0 * f_0 + w_1 * f_1 and so on (this format doesn’t allow me to insert math easily)
 If you know something about the problem you are trying to solve, you could create a set of features to summarize the state space
 Learn the heuristics
 We won’t discuss machine learning approaches for a few more modules but you could use machine learning to learn a featurebased heurstic function.
Example heuristics
The two most commonly used heuristics for Euclidean space are
 Euclidean distance or straight line distance: there is not a shorter path than a straight line between two points so this is the most optimistic estimate one can give in a Euclidean space.
 Manhattan distance or city block distance: if you are in a gridded environment (or in a city!), straight lines are not possible and thus the city block distance is used
 Easter egg: if you got this far, please post a picture of your pet (or a friend’s pet, or a favorite cute animal!) to #random on slack and all such posts will get extra credit