AI 101 – Part 9 – Considering Heuristics

In part 8 of the series, we started to inject some intelligence into our search process.  This was achieved by no longer exploring the state space in a rigid and inflexible fashion, but to start considering the cost of an action.  These costs allow for us to use a priority-queue agenda, that ensures we now place greater emphasis on making our solutions as cheap as possible.  So why didn’t the series end already?  If anything, because this greedy-search approach has its failings and ultimately, we need to be thinking even more intelligently than we currently are.  However, to date, we have not yet seen any example of why this is necessary.  So let us provide one.

The Romanian Map Problem

The Romanian map problem is taken from the classic artificial intelligence textbook: “Artificial Intellingence: A Modern Approach” by Stuart Russell and Peter Norvig.  In this case, we are provided a map layout similar to that shown in the Kakariko Village example back in part 8, but in this example (spoiler alert), the greedy cost-driven approach won’t work.

romania-graph

This is evident really early-on if we are to pick a rather specific example: attempting to navigate from Arad to Bucharest.  In this map, the differences between locations is all rather varied; meaning if we are to search by prioritising the cheapest paths, then this could prove a little bit disastrous.  The agenda will allow us to explore the world by always expanding the next state which has the lowest cost to its neighbour.  Even assuming that we were to do this by ignoring places we have already visited, we would end up with a path like this:

Arad >> Timisoara >> Lugoj >> Mehadia >> Dobreta >> Craiova >> Pitesti >> Bucharest

Now this is a very sub-optimal solution:the total distance taken here is 733 kilometres when you can easily achieve this task in less than 500km.  The issue is because the costs are entirely local in nature; i.e. we are paying attention to how cheap it is to visit a child, but it is not considering whether or not this is bringing us closer to the goal.  In order to resolve this, we need to look at how to create metrics that help give us some guidance.  A metric that allows us to establish whether the next state will be closer to the goal.  Let us consider the adoption of heuristics.

Heuristics

Heuristics are a common type of metric in AI that attempt to establish roughly how far away from the goal state a particular state is.  Heuristics, by their nature, are designed to give a reasonable estimate of the distance to the goal, but they’re not guaranteed to be perfect.  The reasons for heuristics are fairly obvious, given that we really can’t expect to know the distance from any given state to the goal unless we sit down and calculate it.  That would require looking at all potential successor states, iterating through them and their successors to find the goal, only to ultimately achieve that which we had originally set out to do and find a path to the goal.  So providing a rough estimate that is easy to calculate is always useful: given it will give us an indication of whether or not we’re getting closer to the final destination but without the computational overhead of figuring out exactly how far away we are.

As noted, a heuristic needs only calculate roughly how far away the goal state is.  As such, we can relax or remove certain constraints that exist in a given problem in order for them to work.  In doing so, we are actually creating a different version of the problem we are trying to solve, except it is now easier.  As we will see when we return to our example, relaxed problem is actually easier to solve given that it will typically require either less steps to complete.  The cost of the solution to this relaxed problem is our heuristic: providing an estimate of the total cost to reach the goal that will typically be less than the actual cost of the final solution.  This is rather important, as it allows for heuristics to clearly identify the potential a given state has in reaching the final state of the problem.

Should a heuristic be calculating the (estimated) cost of the goal to be less than the actual one, or in the worst case calculating it to be the exact cost of reaching the goal, then we consider this heuristic to be admissible.  Admissible heuristics help ensure we focus our efforts on paths that will converge on the goal, even if it means it will cost more than we estimated.  What is crucial is that the heuristic never overestimates the cost to the goal.  In doing so, we can accidentally force a search algorithm to ignore potential states, given that they may now no longer look as valuable as others in the search space.

Relaxing a Problem

If we consider the Romanian map problem as we already described, the adoption of a heuristic should aim to relax the constraints of that problem.  If we re-evaluate the problem given, the only real constraint given to us is that we need to traverse across the map by way of the main roads between each of the cities.  As such, the one real relaxation of this problem that we can achieve is to move directly from any city to another by way of a straight line.  As such, the cost of reaching the goal, and by extension the heuristic value of that state, would be the straight-line distance to the goal destination.  The original map is updated below except this time we now add the straight line distances of all locations headed towards Bucharest.

The abstract roadmap of Romania found in (Russell and Norvig, 2010).
The abstract roadmap of Romania found in (Russell and Norvig, 2010).

As we can now see in this updated diagram, the straight-line distance to Bucharest from Arad is 366km, which is less than half the distance our cost-driven search found earlier.  This is a perfectly acceptable heuristic, given that there is no path through these connected cities that is less than or equal to that value.  In the case of each city, use of straight-line distance will always provide an admissible heuristic, given that even in the worst possible case, the value provided will be the exact distance it would take to reach Bucharest.  This is the case for all cities that are directly connected to Bucharest itself: Fagaras, Giurgiu, Pitesti and Urziceni.

Using Heuristics In Search

So how well does this apply to the problem at hand?  Is it more beneficial to simply remove the cost-based approach and rely solely on a heuristic?  If we were to adopt the same algorithm structure as before back in part 8, we would have an algorithm that works as follows:

  1. Record the heuristic value of a state: This time ignore the cost of an action, but instead rely on the heuristic value of the state to guide you to the correct destination.
  2. Record (and ignore) places we have visited.
  3. Use a priority queue agenda based on heuristic value.

If we were to try the same problem again, we get a very different solution:

Arad >> Sibiu >> Fagaras >> Bucharest

If we compare the two methods, we can see that the heuristic-driven algorithm performs a lot better, with a much shorter distance travelled: 450km compared to our original of 733km.

Comparing our cost-driven approach (red) to our heuristic driven method (green).
Comparing our cost-driven approach (red) to our heuristic driven method (green).

However, there is still a problem here: even the heuristic-driven search did not yield the optimal solution to this problem.  There is still a faster route to be found.  In order to find it, we will conclude this opening series of AI 101 in part 10 as we bring the cost and heuristic elements together and build A* search.

Enjoying AI and Games? Please support us on Patreon!
Tommy Thompson Written by:

Tommy is the writer and producer of AI and Games. He's a senior lecturer in computer science and researcher in artificial intelligence with applications in video games. He's also an indie video game developer with Table Flip Games. Because y'know... fella's gotta keep himself busy.

Comments are closed.