Search

It's possible to view a lot of different kinds of problems as search problems. Some obvious kinds of search are things like enemy movement in video games: the ghosts move towards pac-man, etc. But even turn-based games like chess or tic-tac-toe involve choosing one of many possible moves repeatedly, with a goal of scoring higher than an opponent. In real life you might try to pick the line at the grocery store checkout that minimizes your shopping time. This may not be the shortest line, because not all lines move at the same speed.

In their book Artificial intelligence a modern approach, Russel and Norvig define a systematic approach to search problems.

Let's model the search problem abstractly, then later implement it concretely to explore different variations and their trade-offs.

First they define concepts like search space, goal states, a successor function to produce a new set of states from the current set, and a cost function to help rank the choices. So for any given search function, your first task is to determine:

1. a set of states \(S\)
2. an initial state \(s_{0}\)
3. a successor function \(\text{succ}(S) \rightarrow 2^{S}\) that encodes transitions from current state \(S\) to its power set \(2^{S}\)
4. a set of goal states \(S_{G}\)
5. a cost function \(\text{cost}(s_{i}) \rightarrow \text{num}\)

Once you have all these, you start to explore the possible sequences of states with the aim of finding a path from the initial state to one of the goal states. Depending on other factors, you might keep searching until you find the best path, or simply return the first one you find. Remember that in general it's also possible that no solution exists so searches have the possibility of failure.

Let's look at an example problem: navigating a 2d maze.

. . . s .
. . . . .
. . . . .
. g . . .

Here s is start position and g is the end position, and at each iteration we can explore at most one position in any of the directions up, down, left, or right. At each iteration the first question we should ask is: did we reach the goal? Here the answer is no, so we continue to the next phase: exploration. The next set of states we could possibly explore are these (L for left, D for down, R for right):

. . L s R
. . . D .
. . . . .
. . g . .

Of these, both L and D are closer to g than the current position, so we should move to one of those. But for clarity, here are all the possible new states \(2^{S}\)

State \(s_{1}\), after moving left:

. . s . .
. . . . .
. . . . .
. . g . .

State \(s_{2}\), after moving down:

. . . . .
. . . s .
. . . . .
. . g . .

State \(s_{3}\), after moving right:

. . . . s
. . . . .
. . . . .
. . g . .

Moving right results in a new state which is "obviously" farther from the goal, so let's not do that. But how can we make a computer program do the "obvious" right thing? This is where the cost function comes in. In a maze like this we can use the distance from the current position to the goal position as our cost function. Compute the cost of each path:

• \(\text{cost}(s_{1}) = 4\)
• \(\text{cost}(s_{2}) = 4\)
• \(\text{cost}(s_{3}) = 6\)

Since the cost of \(s_{3}\) is higher, we rank it lower in our set of choices. The next step is to take one of the better choices and continue searching until we reach the goal. This example so far has been easy because we can keep moving closer to the goal at each iteration, for example we can mark the previous position with an x and illustrate one possible path to the goal:

. . . x .
. . . x .
. . x x .
. . g . .

But what if there was a wall of # blocking one of our paths?

. . . s .
# # # # .
. . . . .
. . g . .

Now the only viable path to the goal requires moving right to pass the wall. The possible paths are now moving left, resulting in failure to reach the goal:

. . x x .
# # # # .
. . . . .
. . g . .

And moving right, which eventually results in success:

. . . x x
# # # # x
. . x x x
. . g . .

Alternatively, we could model the wall as an "infinitely long" path, which might let us avoid iterating in that direction to begin with. Changing the initial state slightly makes this more obvious

. . . s .
. # # # .
. . . . .
. . g . .

Now there are at least two paths to the goal, but it turns out that initially moving right (away from the goal) is part of the shortest path. Finding the shortest path implies exploring all paths to the goal.

To systematically explore the state space, we need to keep track of not only the current shortest distance to the goal, but the cumulative cost of the entire path from where we started.