Many problems simply involve searching through a large bounded set of possibilities. Just knowing the basic moves can help you organize an orderly search.
People are good at solving problems. We can "figure out" how to take three kids to five soccer games in one day. We can also figure out how to visit four stores in one day while minimizing gas usage and avoiding traffic delays. These everyday problems are stressful at times, but are relatively easy to solve. However, when the problem involves moving 100,000 people and their supplies, or routing one million messages through 100,000 nodes in a network, we need help.
Searching is an AI (Artificial Intelligence) technique that finds solutions to such problems [1]. Search systems search through a tree of possible states of a problem to find a goal or solution. This works with problems that require deducing or inferring solutions.
This article discusses the topic of problem solving via searching. The article shows how to use the depth-first, breadth-first, and uniform cost algorithms to solve basic problems. It also describes source code that implements the algorithms.
Searching With AI
The concepts of searching are easiest to understand given an example. Figure 1 shows three blocks. The figure shows all the possible ways of stacking three blocks; each different way is considered a state of the system. The top node of the tree represents the initial problem state, in which the blocks are all sitting on a table. The other nodes in the tree show the other possible combinations of the blocks sitting on one another and on the table.
The tree is actually a database, which is the first part of a search system. The database represents the problem situation, which consists of a start node and all other possible nodes.
The second and third levels of the tree were created by applying operators. Operators are the second part of a search system. In this case, the operators in the system work by moving a block. In this example three rules govern the operators:
Rule 1: Do not move a block unless it is uncovered (no blocks sitting on top of it).
Rule 2: Do not put a block on top of another if the second block has something on it (the second block must be uncovered).
Rule 3: Do not not repeat a state.
These rules are not universal for search systems. They are specific to this example. Different situations will require different rules.
The third part of a search system is the control strategy. The control strategy determines what to do next. Figure 1 shows the entire search space, but does not show the order in which each node was created. If the search program created the second level of the tree before going to the third level, that would be called a breadth-first control strategy. In contrast, the depth-first control strategy would create the left-most node of level two, then the left-most node of level three, before moving back up to level two. The choice of control strategy can affect the answer the search system produces.
The control strategies presented in this article are called "blind" strategies. They assume nothing about the problem and search blindly for an answer. Heuristic control strategies use knowledge of the problem to find answers more efficiently. Efficiency means added complexity, however. Hueristic control strategies are beyond the scope of this article.
The example of Figure 1 is known as a state-space representation. This is an AI term, which means that the search system will (1) start at the top of a tree of nodes, (2) use the operators to create new nodes, and (3) move or "reason" forward to reach a goal state.
The solution is the path from the start node to the goal node. In order to present the complete solution to the user, it must be possible to trace back from the goal node to the start node. So at every node in the tree (except the top), it must be possible to move upward to its parent node.
How can we go from all three blocks sitting on the table to having block 0 on top of block 1 on top of block 2? In Figure 1 the top node is the start node. The goal node is in the third level, third from the right. The sequence of moves that represents the solution is found in the path from the start node to the goal node:
0 1 2 together on the table -> 0 2 on the table, and 1 on 2 -> 0 on 1 on 2That problem was easy. The next sections will use harder problems to illustrate the three control strategies. These problems are easy enough to solve by hand, but could be extended to where they are impossible to solve by hand.
Depth-First Searching
Depth-first searching is one of the three simple blind-search control strategies. Depth-first expands the search space downwards first. The block situation shown earlier will illustrate this control strategy. (The blocks problem is not just a child's game. It represents the problem of juggling logistics. How can we move 500 truckloads of supplies in 200 trucks to 100 different locations? That is not a child's game, but is a similar problem.)
Figure 2 shows the start node (0 on 1, 2 on table) and goal node (0 on 1 on 2) for the example. Figure 3 shows the depth-first control strategy algorithm. The algorithm uses two lists of nodes. The OPEN list contains nodes that have not been expanded (they have no children in the tree) while the CLOSED list contains nodes that have been expanded. The search system expands nodes using the operators and rules until a goal node is created. The solution is the trail from the goal node back to the start node.
Figure 4 shows the tree created by depth-first searching. The node numbers (N0 through N11) show the order in which the nodes are created. The blocks under the node numbers represent the state at a given node. Node N11 is the goal node. The solution is the trail through nodes N0, N1, N6, and N11.
Figure 5 shows part of the source code that implements the depth-first algorithm for the blocks situation. (The full source code is available on the CUJ ftp site. See p. 3 for downloading instructions.) The node struct is the key data structure in the program. It defines an array, named blocks, which represents the configuration of the blocks in the current state. Each element in the blocks array represents a particular block (blocks[0] represents block 0, and so on). The value stored in each element represents the block that is currently underneath. (If the table is underneath, the value is -1.)
The initial and goal states are created a few lines down in the source code. The code shows that initially the table is under blocks 1 and 2 while block 1 is under block 0.
Note the pointers in the node struct. The next pointer is necessary because the nodes will reside in the linked lists pointed to by OPEN and CLOSED. The parent pointer for each node points to that node's parent node in the tree. Providing a parent pointer allows the search system to trace back through the tree to show the solution.
This program and the two described later do not actually build tree data structures. This may be confusing. I use tree diagrams because they make good illustrations of what is happening. The algorithms, however, do not explicitly refer to trees. The nodes in these algorithms do not need to know which nodes are their children or other types of information common in tree data structures. A node only needs to know its parent.
The while(searching) area of Figure 5 is the major part of the algorithm represented in Figure 3, so it comprises the major part of the source code. The subroutines invoked do what their names imply.
The section that expands node n is the part of this program that is unique. All depth-first search systems will use code similar to that shown, except for the code in this section. This section is specific to the block problem being solved. The next two programs have the same characteristic. The bulk of the code in these programs is not specific to any problem; the code that expands a node is custom tailored to the problem at hand.
The loop over i does the node expansion. In this loop the program looks at each block and determines if it can be moved. The code uses the three rules listed above and repeated in the listing. The first test (if(is_uncovered(n, i))) checks whether block i at node n is covered. If the block is covered, it cannot be moved so the algorithm proceeds to the next node.
If the block is not covered, the program attempts to move it. First, the program tries to move it to the table. Next, it tries to move the block on top of each of the other blocks in turn. (The code here will work for COUNT+1 blocks, not just three.) The subroutine calls are written so as to ensure that the operator rules are obeyed.
This program produces the correct answer for the given problem. Other problems with other start and goal states can be simulated by changing the initialization part of the code.
Breadth-First Searching
Breadth-first searching is another of the three simple blind-search control strategies. Breadth-first search expands the search space outward first by filling in a level of the tree before going down to the next, deeper level.
Figure 6 shows the breadth-first control strategy. This is almost identical to the depth-first strategy in Figure 3. The major difference is in the third line from the bottom. The breadth-first algorithm places all nodes expanded from node n at the end of the OPEN list instead of the beginning. In the breadth-first scheme, the nodes are expanded in the order they are created. This ensures that each level in the search space tree is filled before going down to the next level.
A robot navigation problem will illustrate breadth-first searching. Figure 7 shows a simple course that a robot must navigate. The circles are obstacles. The robot enters at any of the four squares at the top of the matrix and tries to reach any square at the bottom.
The operators for this example follow these rules: a robot may (1) move down one square, and if that is not possible; (2) move left one square, and if that is not possible; (3) move right one square. The robot would have a map of the course before moving. The robot would find a path through the map, then move through that path in the obstacle course.
Figure 8 shows the state search tree for this problem. Each node contains the coordinates of a square, and represents a square that the robot can visit. The goal node has the coordinates (3, 3). This node occurs in the tree twice. The breadth-first search will find the (3, 3) node in the far-right branch of the tree first. (Breadth-first searching always finds the goal node with the least depth first.) The solution to the navigation problem is to follow the rightmost branch of the tree.
This navigation example is easy. But suppose the course were 1,000 by 1,000 and had several thousand obstacles. That would be too much for a person, but a search system would solve it as easily as it solves the example.
Figure 9 shows part of the source code that implements the breadth-first algorithm for the robot navigation. The integer matrix holds the navigation course, with ones representing obstacles. The node struct is similar to that in Figure 5. Here, the data for the problem is kept in the x and y coordinates. The next and parent pointers perform the same role as in the previous example.
The program initializes this problem by allowing the robot to enter the course at the three open squares in the top row of the matrix. The while(searching) section performs the searching part of the algorithm. The code follows the rules given above by first trying to move the robot down one square. If that is not possible, it tries to move the robot left one square, then right one square.
A major difference in this program is not shown in the figure. The add_to_list subroutine adds the node to the end of the list instead of the start of the list as was done in the depth-first program.
Uniform Cost Searching
Uniform cost searching is the third of the three simple blind-search control strategies. It is similar to breadth-first searching, but it adds the concept of cost.
Cost is important in the real world. The previous examples assumed that going from one state to any number of other states was the same. In real life, however, different moves rarely cost the same. Locations have different distances or difficulty separating them, and the cost to go to these locations is different.
Figure 10 shows the uniform cost algorithm. This is similar to the breadth-first algorithm shown in Figure 6. The main differences are references to cost. Also note that when a node is removed from the OPEN list, the node with the lowest cost is removed.
Finding the shortest path through a network will illustrate the uniform cost control strategy. Figure 11 shows a network of points. This could be a map of cities, a network of computers, a network of telephone switches, etc. The numbers between the points represent the distances (costs of moving) from one point to another.
Figure 12 shows the state search tree for moving from point P0 to point P9. There are five different paths between these two points. The shortest or cheapest path has a total distance of nine as shown in the path second from the right. The solution to moving from point P0 to P9 is to traverse the path P0, P3, P8, and P9.
Again, this is a simple example that a person could solve in her head. Real life problems, however, can have hundreds of points (stores needing to distribute products) or thousands (computer and telephone networks). That is too tedious and difficult to solve by hand, but simple for the computer.
Figure 13 shows part of the source code that implements the uniform cost algorithm for moving through the network of points. The cost_matrix shows the cost of moving between two points. It works like one of those distance tables found in a road atlas. The node struct is similar to those shown in the previous two listings. The data for this problem is kept in the cost variable. As each point is added to the state search tree, its cost is set to the cost of its parent plus the cost of moving from its parent to itself. The next and parent pointers perform the same role as in the previous examples.
The first section of code initializes the problem. The create_new_node routine receives the node number and cost as inputs. This program sets P0 as the start point, and allows the user to enter the goal point as an argument (not shown). It is simple to set any points as the start and goal points.
The while(searching) section of code implements the majority of the control strategy. The remove_from_list routine searches through the OPEN list to find the node with the lowest cost. This is the major difference between this program and the others and is the key to finding the cheapest path.
The rest of the code expands the node n pulled from the OPEN list. The code will not expand a node to itself (cost is NOTHING, -1 in the cost_matrix). It will also not expand a node's parent, since that is the same as moving backward in the network.
Conclusion
Searching is a powerful technique for finding solutions to problems that require deduction or inference. This AI technique applies to many practical problems found in logistics, management, shipping, and computer and communications networks. The three simple algorithms presented here will work with problems that are too large and complex for people to solve reliably.
This article did not mention several important topics in searching. It is easy for the state search trees to become large (hundreds of thousands of nodes). Today's desktop computers can handle this with ease. Researchers in past years did not have this hardware, so they developed techniques to limit the search space. Their algorithms are far more complex and efficient than those presented here. Nevertheless, these three algorithms will solve most problems easily.
Searching is a deep topic. Explore these algorithms and apply them to problems you encounter daily.
Reference
[1] Avron Barr and Edward A. Feigenbaum, editors. The Handbook of Artificial Intelligence, Volume 1 (William Kauffmann, 1981).
Dwayne Phillips has worked as a software and systems engineer with the US government since 1980. He has written Image Processing in C, R&D Publications, 1994; and The Software Project Manager's Handbook, Principles that Work at Work, IEEE Computer Society, 1998. He has a Ph.D. in electrical and computer engineering from Louisiana State University. He can be reached at d.phillips@computer.org.