AI 101 Part 8 – Cost-Driven Search

Part 7 introduced the notion of uninformed search: a strategy of exploring a search space whereby we follow a rather strict and inflexible series of instructions.  This is achieved courtesy of the algorithms we discussed, with breadth-first search exploring each layer or depth in the search space in its entirety, while depth-first search burrows down deep into particular corners, only to subsequently pull itself back up once a dead-end has been discovered.  While both regimented and structured, neither of these approaches is intelligent and as such, is not particularly useful in many larger circumstances.

Consider the example map shown below, taken from The Legend of Zelda: A Link to the Past.  This map has a relatively complex layout: with a number of different paths that could be taken from one area to the next.  Now let us consider if we were to navigate this map, starting from the top and working our way down, but only walking along the stoned paths, there are a number of issues we will stumble across.  Firstly, how do we model this map such that we can cross it?  We provide a simple abstraction of this map with nodes that represent junctions in the map. We would assume then that you can reach any node by walking along the stone paths from one node to the next.

NOTE: Beware that this is not the best manner with which to model this environment. We will be returning to discuss how best to model and explore this village in subsequent entries of AI 101 and AI DIY.

Despite this state structure we have provided, adopting either breadth-first or depth-first approach here is rather naive for a number of reasons:

  1. Breadth-first will find a solution, but it will take time: It will effectively search the entire map in the worst possible scenario.
  2. Depth-first might find a solution depending on where it starts: Given that this state space is effectively a connected graph of locations, it could easily catch itself in a loop and never escape.
  3. Each search could easily visit the same state twice: This is map is a connected graph, so there is plenty of potential for the same successor state to appear multiple times.
  4. The distance between each state is not the same across the map.  As such, some paths may not appear to be optimal due to the number of ‘walk‘ actions taken, but the distance travelled tells us otherwise.

So we need to be smarter in how we go about exploring these problems.  Let’s start trying to make these searches more intelligent.

Some Simple Changes

We can start making our search strategies more effective, but introducing a couple of very simple changes to the formula:

  1. Record the Cost of Actions: Ensure that we now know just how expensive a particular action is.
  2. Record (and ignore) places we have visited: If we visit the same state twice, don’t bother checking if it is the goal, don’t add its children to the agenda.  Just ignore it.  To do this, we need to keep a reference to whether we have visited that state before.
  3. Change the agenda: As mentioned in Part 7, the agenda of the search algorithms stores the successor states we have yet to visit and it typically does so by the order in which we explore the search space.  So breadth first adopts a queue, while depth first uses a stack.  Now we wish to use something different, a priority queue: which is a queue where items are ranked based upon a metric.  This will allow us to pick the next state to visit based upon costs we mentioned above.

With this in mind, we have now created an intelligent algorithm, given it now makes moves based upon information it is finding in the problem.  If we were to write this as an algorithm in code, then it would look something like this:

A Greedy Algorithm

What we have created is a greedy algorithm: a search method that now always takes what it thinks is the best thing at that point in time.  Is this a good thing?  Yes and no.  While it is now more intelligent, it also suffers from a number of real problems as a result of these changes:

  • It is greedy! Being greedy is a bonus as much as it is a hinderance.  The algorithm now makes the best decision it can at that point in time, which isn’t necessarily a good thing in the grander scheme of things.
  • It does not think about the future: One real issue is that this algorithm does not consider how useful that ‘best’ action is after it has been taken.  It could very well be that making the best action at time ‘t’ proves to be not that useful when we look for our next action at time ‘t+1’.

So why would we be so worried about this?  Well, let us take an example from the previously shown Kakariko Village from The Legend of Zelda.  If we were to run a search from a particular start state and upon finding the goal, build our path by backtracking through the states predecessors or parents, we get some varied performance using breadth first, depth first search and our newly minted greedy search.  These paths assume that the list of successors for a given state are recorded in order of north, east, south and finally west.

If we look at each of the resulting paths generated, it’s clear that breadth-first search is the most effective choice for this particular problem.  As mentioned previously, it can find the optimal path because it searches the whole breadth of the search space.  What we don’t see in this image is that in order to find that goal, the search algorithm has explored most of the graph in order to find it. So it is a great solution for this problem, but it is not an efficient algorithm to use should this map get any bigger.

The path for depth-first search is something of a disaster and this is largely due to the fact that it never stopped to backtrack; because this is a fully connected graph of states.  This means that the search can’t necessarily bottom out and be forced to backtrack to a child state it passed by earlier. In fact, if we were to use the original design of depth-first, it will never find a solution. This is because it will get caught in a loop in the east side of the village, getting caught in a small loop in the south-east corner, then running back along the east perimeter before running back down into the corner again.  In order for this to work, we need to add the second change mentioned earlier and ensure we do not re-visit states that we have already been to.  In doing so, this will actually allow for our modified search to complete, but with a horribly inefficient solution.  Given as stated, it never bottoms out, it keeps searching down one particular ‘path’ of the search space until it accidentally finds the goal.

Lastly, our cost-driven greedy search does not fair particularly well either.  In fact, it produces the same efficient solution as breadth-first search.  While this works out well in this particular case, it almost backfires.  There are a couple of paths that are almost generated due to the short-sightedness of its approach to finding solutions.  As shown below, it almost accidentally picks sub-par solutions, but that agenda prioritising cheaper costing actions is what stops it from happening.  What is also more useful is that it won’t explore as much of the state space as the other two algorithms.

Awesome.  We now have an intelligent algorithm that will work!  However in Part 9, we will look at how this particular algorithm fails to work in certain contexts and how to move into the next important aspect of intelligent search: heuristics.

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.