Search Problems in AI

Let’s talk about Search, the most basic of techniques in AI. Search provides a very broad framework for modeling problems, almost any problem can be modeled as a search problem (e.g., finding the shortest path between two cities, finding the best next move in a game of chess, or finding the best sequence of stock trades).A search problem consists of:

  1. A state space
  2. A successor function
  3. A start state
  4. A goal test

Let’s dig deeper into each of these components:

State Space

A state encodes the picture of the world (relevant to the problem) at a certain point along the progression of our plan. State space is the universe of all the possible states. We should be careful to encode only the necessary information in the state and not every tiny little detail about the world because it would blow up our search space and make search that much more difficult. Here in lies the distinction between the model state and the world state. The world state includes every last detail of the environment while the search/model state keeps only the details needed for planning. We are always working with a model of the world and choosing an appropriate model is critical to whether or not our solution works.

Let’s understand the difference between model state and world state with the example of routing. We want to find a route from one city to another. To solve this problem, we may choose a model in which cities are represented as nodes and there is a directed edge from one city to another to represent a path. This is only an abstraction of the real world. The real world has any number of other details (like individual roads on a path, traffic on each road and so on) which are not relevant for finding a solution to our problem. We want to choose the minimal model that captures enough details, but no more, for us to be able to solve the problem.

Let’s see another example to understand how choosing an appropriate model affects our ability to find a solution: Eight Queens puzzle. The goal is to place 8 queens on a chessboard such that no two queens threaten each other. We can model our problem like this:

  • The position vector of the 8 queens can be used as the state. Each queen can be placed on any of the 64 squares so the size of our search space is 648 = 248 ~ 2.8*1014, quite a large number. We are unlikely to find a solution with this model in any reasonable time.
  • No two queens can share a column so each queen must be placed in its own column. With this key insight, we can model our state as the vector of row numbers of the 8 queens, ordered by column number. This reduces our search space to 88 = 224 ~ 1.7*107, which can be enumerated by any decent machine in less than a second.

Successor Function

The successor function models how we think the world works i.e., how states evolve in response to the actions we take. It takes a state from the state space and returns the list of states directly reachable from that state, along with the actions that achieve them and their costs.

Start State

The state from where we start the search. For the routing problem, it can be the source city. For the Eight Queens puzzle, it can be any random 8-vector of row numbers if we use backtracking.

Goal Test

The goal test is a function that takes a state and tells whether or not it is a goal state. For the routing problem, it can compare the current state with the destination. For the Eight Queens puzzle, it can check if there exist two queens that threaten each other. The goal test comes directly from the problem description but how efficiently we can implement it, depends on our model.

A solution to a search problem is a sequence of actions (a plan) which transforms the start state to a goal state. For the routing problem, it can be the sequence of cities we visit along a path from the source to the destination. Once we have modeled our problem as a search problem, we can use standard search techniques, which don’t require knowledge of our problem but use the abstraction of the start state, the successor function and the goal test. So we can implement search algorithms once and use them again and again for different problems by simply defining the state state, the successor function and the goal test.

The state space is basically a graph, where the nodes are abstracted world configurations and edges represent successors (action results). The goal test is a set of goal nodes. This search space graph is a mathematical representation of a search problem. We don’t really build this graph in memory because it is exponentially large for any non-trivial problem. What we can work with, however, is a search tree, rooted at the start state and then having its successors at the first level and their successors at the next level and so on. We can’t build this entire tree in memory either, rather we try to find a solution while exploring as little of the search tree as possible.

We have the following general tree search algorithm:

This general tree search algorithm is instantiated into several specific search algorithms, depending on the strategy i.e., which node is picked for expansion next. Each of these algorithms have different properties:

  • Completeness: Is it guaranteed to find a solution if one exists?
  • Optimality: Is it guaranteed to find the optimal/best solution?
  • Time complexity
  • Space complexity

We will discuss several of these algorithms in future posts.


4 thoughts on “Search Problems in AI

  1. Hi Kartik, there needs to be a small correction. Since all queens are identical in the Eight queens puzzle, there should be 64C8 total arrangements rather than 64^8.

    • It depends on how you model your state space. If you define your state to be 8-vector of queen positions when no two queens can have the same position, then the size of the state space would be 64C8.

      On the other hand, if you model your state to be 8-vector of queen positions, when multiple queens can have the same position, the size of state space will be 64^8.

      In the first case, we’ve a smaller state space but implementation of successor function is more expensive because it now has to ensure that no two queens can have the same position. In the second case, the successor function is straightforward but the state space is larger.

      So there’s always this tradeoff we have to think of.

  2. Pingback: Uninformed Search Algorithms | Everything Under The Sun

  3. Pingback: Adversarial Search | Everything Under The Sun

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s