Module 2: Idealized Searches

Topic 3: Creating Effective Heuristics for Search

Why do we need a good heuristic?

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 efficient
- 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 Manhattan 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 non-promising paths)
- To do this, it needs to be a non-zero value but not an overestimate (see admissible above)

How to create a heuristic

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

Creating a heuristic in a non-Euclidean space can feel challenging. We offer some tips to help you to design effective heuristics.

Relax the problem
- What can you do the make the problem easier? This is called relaxing the problem. Remember, admissible heuristics are always optimistic so one way to design an admissible and O(1) heuristic is to remove the difficult aspects of the problem.
- For example, assume there are no obstacles in a task where you must navigate around obstacles. With no obstacles, straight light distance is an admissible heuristic and will satisfy the triangle inequality too.
- If you are trying to use search on a puzzle or a game, remove rules that make the game or puzzle hard. For example, remove any constraints such as “red must be next to blue.”
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 pre-compute 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
Feature-based 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)
Learn the heuristics
- We won’t discuss machine learning approaches for a few more modules but you could use machine learning to learn a feature-based heurstic function.

Navigation

Jump back to informed searches

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