Last Modified 342010 
IUSB 

Home AI Topic Links Problem Solving Agents Uninformed Search Strategies BreadthFirst Search UniformCost Search DepthFirst Search Depth First C++ Solution Depth Limited Search Iterative Depth Search Bidirectional Search Comparing Strategies Informed Strategies Greedy BestFirst Conditions For Optimality A* Search C++ A* Search Code 
Solving Problems by SearchingProblem Solving AgentsThe simplest agents previously discussed were the reflex agents, which base their actions on a direct mapping from states to actions. Such agents cannot operate well in environments for which this mapping would be too large to store and would take too long to learn. Goalbased agents, on the other hand, can succeed by considering future actions and the desirability of the their outcomes. One kind of goalbased agent is called a problemsolving agent. Problem solving agents use atomic representations. In an atomic representation each state of the world is indivisible and has no internal structure. In other words, states of the world as considered as wholes, with no internal structure visible to the problem solving algorithms. Our discussion of problem solving agents begins with precise definitions of problems and their solutions and give several examples to illustrate these definitions. We then describe several generalpurpose algorithms that can be used to solve these problems. We will see several uninformed search algorithms  algorithms that are given no information about the problem other than its definition. Although some of these algorithms can solve any solvable problem, none of them can do so efficiently. Informed search algorithms, on the other hand, can often do quite well given some idea of where to look for solutions. Initially, we will limit ourselves to the simplest kind of task environment, for which the solution to a problem is always a fixed sequence of actions. We will use concepts from the analysis of algorithms. Specifically, asymptotic complexity, or Big 'O' notation, and NPcompleteness.
Intelligent agents are supposed to maximize their performance measure. Achieving this is sometimes simplified if the agent can adopt a goal and aim at satisfying it. Let us first look at why and how an agent might do this. Imagine an agent in the city of Arad, Romania, enjoying a touring holiday. The agent's performance measure contains many factors: it wants to improve its suntan, improve its Romanian language, take in the sights, enjoy the Romanian nightlife, avoid hangovers, and so on. The decision problem is a complex one involving many tradeoffs and careful reading of guidebooks. Now, suppose the agent has a nonrefundable ticket to fly out of Bucharest the following day. In that case, it makes sense for the agent to adopt the goal of getting to Bucharest. Courses of action that don't reach Bucharest on time can be rejected without further consideration and the agent's decision problem is greatly simplified. Goals help organize behavior by limiting the objectives that the agent is trying to achieve and hence the actions it needs to consider. Goal formulation, based on the current situation and the agent's performance measure, is the first step in problem solving. We will consider a goal to be a set of world states  exactly those states in which the goal is satisified. The agent's task is to find out how to act, now and in the future, so that it reaches a goal state. Before it can do this, it needs to decide (or we need to decide on its behalf) what sorts of actions and states it should consider. If it were to consider actions at the level of "move left foot forward an inch" or "turn the steering wheel one degree left," the agent would probably never find its way out of the parking lot, let alone to Bucharest, because at that level the detail there is too much uncertainty in the world and there would be too many steps in a solution. Problem formulation is the process of deciding what actions and states to consider, given a goal. Let us assume that the agent will consider actions at the level of driving from one major town to another. Each state therefore corresponds to being in a particular town. Our agent has now adopted the goal of driving to Bucharest, and is considering where to go from Arad. There are three roads out of Arad, one toward Sibu, one to Timisoara, and one to Zerind. None of these achieves the goal, so unless the agent is very familiar with the geography of Romania, it will not know which road to follow. In other words, the agent will not know which of its possible actions is best, because it does not yet know enough about the state that results from taking each action. If the agent has no additional information  i.e., if the environment is unknown in the sense defined in Section 2.3  then it has no choice but to try one of the actions at random. But suppose the agent has a map of Romania. The point of a map is to provide the agent with information about the states it might get itself into, and the actions it can take. The agent can use this information to consider subsequent stages of a hypothetical journey via each of the three towns, trying to find a journey that eventually gets to Bucharest. Once it has found a path on the map from Arad to Bucharest, it can achieve its goal by carrying out the driving actions that correspond to the legs of the journey. In general, an agent with several immediate options of unknown value can decide what to do first by examining future actions that eventually lead to states of known value. To be even more specific about what we mean by "examining future actions," we have to be more specific about properties of the environment. For now, we will assume that the environment is observable, so that the agent always knows the current state. For the agent driving in Romania, it's reasonable to suppose that each city on the map has a sign indicating its presence to arriving drivers. We will also assume the environment is discrete, so that at any given state there are only finitely many actions to choose from. This is true for navigating in Romania because each city is connected to a small number of other cities. We will assume the environment is known, so that the agent knows which states are reached by each action. Next, we assume our map is accurate. And finally, we assume that the environment is deterministic, so that each action has exactly one outcome. Under ideal conditions, this is true for the agent in Romania  it means that if it chooses to drive from Arad to Sibiu, it does end up in Sibiu. Under these assumptions, the solution to any problem is a fixed sequence of actions. The process of looking for a sequence of actions that reaches the goal is called a search. A search algorithm takes a problem as input and returns a solution in the form of an action sequence. Once a solution is found, the actions it recommends can be carried out. This is called the execution phase. Figure Agent1 gives us a simple formulate, search, execute design for the agent:
After formulating a goal and a problem to solve, the agent calls a search procedure to solve it. It then uses the solution to guide its actions, doing whatever the solution recommends as the next thing to do  typically the first action of the sequence  and then removing that step from the sequence. Once the solution has been executed, the agent will formulate a new goal. Notice that while the agent is executing the solution sequence it ignores its percepts when choosing an action because it knows in advance what they will be. An agent that carries out its plans with its eyes closed, so to speak, must be quite certain of what is going on. Control theorists call this an openloop system, because ignoring the percepts breaks the loop between agent and environment. We first describe the process of problem formulation, and then present various algorithms for the Search function. Welldefined problems and solutionsA problem can be defined formally by five components:
The preceding elements define a problem and can be gathered together into a single data structure that is given as input to a problemsolving algorithm. A solution to a problem is an action sequence that leads from the initial state to a goal state. Solution quality is measured by the patch cost function, and an optimal solution has the lowest path cost among all solutions. Formulating ProblemsIn the preceding section we proposed a formulation of the problem of getting to Bucharest in terms of the initial state, actions, transition model, goal test, and path cost. This formulation seems reasonable, but is still a model  an abstract mathematical description  and not the real thing. Compare the simple state description we have chosen, In(Arad), to an actual crosscountry trip, where the state of the world includes so many things: the traveling companions, what is on the radio, the scenery out the window, whether there are any law enforcement officers nearby, how far it is to the next rest stop, the condition of the road, the weather, and so on. All these considerations are left out of our state descriptions because they are irrelevant to the problem of finding a route to Bucharest. The process of removing detail from a representation is called abstraction. In addition to abstracting the state description, we must abstract the actions themselves. A driving action has many effects. Besides changing the location of the vehicle and its occupants, it takes up time, consumes fuel, generates pollution, and changes the agent. Our formulation takes into account only the change in location. Also, there are many actions that we will omit altogether: turning on the radio, stopping at McDonald's, getting speeding tickets, and thrown in jail for drunk driving, and so on. And of course, we don't specify turning the steering wheel 97 degrees, or screaming at the kids. Can we be more precise about defining te appropriate level of abstraction? Probably not, but let's give it a shot anyways. Think of the abstract states and actions we have chosen as corresponding to large sets of detailed world states and detailed action sequences. Now consider a solution to the abstract problem: the path from Arad to Sibiu to Rimnicu Vilcea to Pitesti to Bucharest. This abstract solution corresponds to a large number of more detailed paths. For example, we could drink beer between Sibiu and Rimnicu Vilcea, then smoke pot for the rest of the trip, although this may add to the mileage, since we forgot where we were going, but didn't care anyways. The abstraction is valid if we can expand any abstract solution into a solution in the more detailed world; a sufficient condition is that for every detailed state that is In(Arad), there is a detailed path to some state that is In(Sibiu), and so on. The abstraction is useful if carrying out each of the actions in the solution is easier than the original problem; in this case they are easy enough that they can be carried out without further search or planning by an average driving agent. But, if we are planning on drinking beer on this trip, and we don't want to get arrested, we had better plan on having a Better than average driving agent. The choice of a good abstraction thus involves removing as much detail as possible while retaining validity and ensuring that the abstract actions are easy to carry out. Were it not for the ability to construct useful abstractions, intelligent agents would not be considered very intelligent, especially when being swamped by activities in the real world. Example ProblemsThe problemsolving approach has been applied to a vast array of task environments. We list some of the best known here, distinguishing between toy and realworld problems. A toy problem is intended to illustrate or exercise various problemsolving methods. It can be given a concise, exact description and hence is usable by different researchers to compare the performance of algorithms. A realworld problem is one whose solutions people actually care about. They tend not to have a single agreedupon description, so we will do our best describing the formulations used. Toy ProblemsVacuum WorldThe first example we will examine is the vacuum world. as diagrammed in Figure Agent3:
The problem is formulated as follows:
Compared with the real world, this toy problem has discrete locations, discrete dirt, reliable cleaning, and it never gets messed up once cleaned. 8puzzleThe 8puzzle, an instance of which is shown in Figure Agent4, consists of a 3 Χ 3 board with eight numbered tiles and a blank space. A tile adjacent to the blank space can slide into the space. The object is to reach a specified goal state, such as the one shown on the right of the figure:
The object is to reach a specified goal state, such as the one shown on the right of the figure. The standard formulation is as follows:
What abstractions have we included here? The actions are abstracted to their beginning and final states, ignoring the intermediate locations where the block is sliding. We have abstracted away actions such as shaking the board when pieces get stuck, or extracting the pieces with a knife and putting them back again. We are left with a description of the rules of the puzzle, avoiding all the details of physical manipulations. The 8puzzle belongs to the family of slidingblock puzzles, which are often used as test problems for new search algorithms in AI. This family is known to be NPcomplete, so one does not expect to find methods significantly better in the worst case than the search algorithms which are described in this analysis. the 8puzzle has 9!/2 = 181,440 reachable states and is easily solved. The 15puzzle (on a 4x4 board) has around 1.3 trillion states, and random instances can be solved optimally in a few milliseconds by the best search algorithms. The 24puzzle (on a 5x5 board) has around 10^{25} states, and random instances take several hours to solve optimally. 8Queens ProblemThe goal of the 8queens problem is to place eight queens on a chessboard such that no queen attacks any other. (A queen attacks any piece in the same row, column or diagonal.) Figure Agent5 shows an attempted solution that fails: the queen in the rightmost column is attacked by the queen at the top left.
Although efficient specialpurpose algorithms exist for this problem and for the whole NQueens family, it remains a useful test problem for search algorithms. There are two main kinds of formulation. An incremental formulation involves operators that augment the state description, starting with an empty state; for the 8Queens problem, this means that each action adds a queen to the state. A completestate formulation starts with all 8 queens on the board and moves them around. In either case, the path cost is of no interest because only the final state counts. The first incremental formulation one might try is the following:
In this formulation we have 64 * 63 * 62 ... *57 ==> 1.8 x 10^{14} possible sequences to investigate. A better formulation would prohibit placing a queen in any square that is already attacked:
This formulation reduces the 8Queens space from 1.8 x 10^{14} to just 2,057 and solutions are easy to find. On the other hand, for 100 queens the reduction is from roughly 10^{400} state to about 10^{52} states. A big improvement, but not enough to make the problem tractable. The Knuth SequenceOur final toy problem was devised by Donald Knuth in 1964 and illustrates how infinite spaces can arise. Knuth conjectured that one can start with the number 4, apply a sequency of factorial, square root, and floor operations, and arrive at any desired positive integer. For example:
To our knowledge there is no bound on how large a number might be constructed in the process of reaching a given target  for example, 620,448,401,733,239,439,360,000 is generated in the expression for 5  so the state space for this problem is infinite. Such state spaces arise very frequently in tasks involving the generation of mathematical expressions, circuits, proofs, programs, and other recursively defined objects. Real World ProblemsRoute Finding ProblemsWe have already seen how the routefinding problem is defined in terms of specified locations and transitions along links between them. Routefinding algorithms are used in a variety of applications. Some, such as Web sites and incar systems that provide driving directions, are relatively straightforward extensions of the Romania example. Others, such as routing video streams in computer networks, military operations planning, and airline travel planning systems, involve much more complex speciifcations. Consider the airline travel problems that must be solved by a travel planning Web site:
Commercial travel advice systems use a problem formulation of this kind, with many additional complications to handle the byzantine fare structures that airlines impose, e.g. They want to charge me for a whole row when I forget to put on my deodorant. If it is such a big deal, then why don't they just have a community antiperspirant, that we all could use? As any seasoned traveler knows, however, that not all air travel goes according to plan. A really good system should include contingency plans  such as backup reservations on alternate flights  to the extent that these are justified by the cost and likelihood of failure of the original plan. Touring ProblemsTouring Problems are closely related to routefinding problems, but, with an important, very important, difference. Consider, just consider, for a moment, if you will, the problem "Visit every city in Figure Agent2 at least once, starting and ending in Bucharest." As with route finding, the actions correspond to trips between adjacent cities. The state space, however is quite different. Each state must include not just the current location but also the set of cities the agent has visited. So, the initial state would be: In(Bucharest), Visited({Bucharest}), a typical intermediate state would be: In(Vaslui), Visited({Bucharest, Urziceni, Vaslui}), and the goal test would check whether the agent is in Bucharest and all 20 cities have been visited. Traveling Salesperson ProblemThe Traveling Salesperson Problem (TSP) is a touring problem in which each city must be visited exaclty once. The aim is to find the shortest tour. The problem is known to NPhard, but an enormous amount of effort has been expended to improve the capabilities of TSP algorithms. In addition to planning trips for traveling salespersons, these algorithms have been used for tasks such as planning movements of automatic circuit board drills and of stocking machines on shop floors. VLSI LayoutA VLSI layout problem requires positioning millions of components and connections on a chip to minimize area, minimize circuit delays, minimize stray capacitances, and maximize manufacturing yield. The layout problem comes after the logical design phase, and is usually split into two parts: cell layout and channel routing. In cell layout, the primitive components of the circuit are grouped into cells, each of which performs some recognized function. Each cell has a fixed footprint (size and shape) and requires a certain number of connections to each of the other cells. The aim is to place the cells on the chip so that they do not overlap and so that there is room for the connecting wires to be placed between the cells. Channel routing finds a specific route for each wire through the gaps between the cells. These search algorithms are extremely complex, but definitely worth solving. Robot NavigationRobot Navigation is a generalization of the routefinding problem described earlier. Rather than a discrete set of routes, a robot can move in a continuous space with (in principle) an infinite set of possible actions and states. For a circular robot moving on a flat surface, the space is essentially twodimensional. When the robot has arms and legs or wheels that must also be controlled, the search space becomes manydimensional. Advanced techniques are required just to make the search space finite. In addition to the complexity of the problem, real robots must also deal with errors in their sensor readings and motor controls. Automatic Assembly SequencingAutomatic assembly sequencing of complex objects by a robot was first demonstrated by Freddy. Progress since then has been slow but sure, to the point where the assembly of intricate objects such as electric motors is economically feasible. In assembly problems, the aim is to find an order in which to assemble the parts of some object. If the wrong order is chosen, there will be no way to add some part later in the sequence without undoing some of the work already done. Checking a step in the sequence for feasibility is a difficult geometrical search problem closely related to robot navigation. Thus, the generation of legal actions is the expensive part of assembly sequencing. Any practical algorithm must avoid exploring all but a tiny fraction of the state space. Another important assembly problem is protein design, in which the goal is to find a sequence of amino acids that will fold into a threedimensional protein with the right properties to cure some disease. Searching 4 SolutionsHaving formulated some problems, we now need to solve them. A solution is an action sequence, so search algorithms work by considering various possible actions sequences. the possible action sequences starting at the initial state from a search tree with the initial state at the root; the branches are actions and the nodes correspond to states in the state space of the problem. Figure Agent6 shows the first few steps in growing the search tree for finding a route from Arad to Bucharest:
The root node of the tree corresponds to the initial state, In(Arad). The first step is to test whether this is a goal state. (Clearly it is not, but it is important to check so that we can solve trick problems like "Starting in Arad, get to Arad"). Then we need to consider taking various actions. This is done by expanding the current state; that is, applying each legal action to the current state, thereby generating a new set of states. In this case, we add three branches from the parent node: In(Arad) leading to the three new child nodes: In(Sibiu), In(Timisoara), and In(Zerind). Now we must choose which of these three possibilities to consider further. This is the esssence of the search  following up one option now and putting the others aside for later, in case the first choice does not lead to a solution. Suppose we choose Sibiu first. We check to see whether it is a goal state (it is not) and then expand it to get In(Arad), In(Fagaras), In(Oradea), and In(RimnicuVilcea). We can then choose any of these four, or go back and choose Timisoara or Zerind. Each of these six nodes is a leaf node, that is, a node with no children in the tree. The set of all leaf nodes available for expansion at any given point is called the frontier. (Many authors call it the open list, which is both geographically less evocative and inaccurate, as it need not be stored as a list at all.) In Figure Agent6, the frontier of each tree consists of those nodes with bold outlines. The process of choosing and expanding nodes in the frontier continues until either a solution is found or there are no more states to be expanded. The general TreeSearch algorithm is shown in Figure Agent7. Search algorithms all share this basic structure; they vary primarily according to how they choose which state to expand next  the socalled search strategy.
Turning back to Figure Agent6, we can see quite a dilemma in that it is possible to return to Arad, thus potentially making this a very long journey. The official term for this is that In(Arad) is a repeated state in the search tree, generated by a loopy path, or unofficially: our case of Budweieser is going to run out long before our trip is over. Considering such loopy paths means that the complete search tree for Romania is infinite, because you can get stuck running around in circles, if you're not careful. On the other hand, the state space as they call it, or I would just say the number of towns on the map, has only 20 states. So, since this initial algorithm allows us to repeat our path, we obviously need to make some minor modifications. Fortunately, since we are trying to cut down our trip distance, we need not consider ever returning to a place we have already visited. Loopy paths are a special case of the more general concept of redundant paths, which exist whenever there is more than one way to get from one state to another. Consider the paths AradSibiu, about 140 km, and AradZerindOradeaSibiu, about 297 km.
Officially we would say that the second path is redundant, unofficially, we might say: We better have our navigator cut back on the Bud a little bit. If you are concerned about reaching the goal, there's never any reason to keep around more than one path to any given state, because any goal state that is reachable by extending the other. In some cases, it is possible to define the problem itself so as to eliminate redundant paths. For example, if we formulate the 8Queens problem so that a Queen can be placed in any column, then each state with n queens can be reached by n! different paths; but if we reformulate the problem so that each new queen is placed in the leftmost empty column, then each state can be reached only through one path. In other cases, redundant paths are unavoidable. This includes all problems where the actions are reversible, such as routefinding problems and slidingblock puzzles. Route finding on a rectangular grid is particularly important in computer games. Initially, our unexplored grid appears as follows:
In such a grid, each state has four successors, so when we initialize our first state it may look like:
Expanding the frontier node above the root node gives us:
A search tree of depth 5 has 4^{5} or 1024 leaves, but only 2 * 5 ^{2} (50) distinct states within 5 steps of any given state. However, if we have a 20 x 20 grid, there may be a trillion nodes but only 800 distinct states. Thus, following redundant paths can cause a tractable problem to become intractable. This can be true, even if the algorithm knows how to avoid infinite loops. As the saying goes, algorithms that forget their history are doomed to repeat it. The way to avoid exploring redundant paths is to remember where one has been. To do this, we augment the TreeSearch algorithm with a data structure called the explored set, which remembers every expanded node. Sometimes this is called a closed list or explored set = closed list. Newly generated nodes that match previously generated nodes  ones in the explored set or the frontier  can be discarded instead of potentially being added to the frontier. The new algorithm called GraphSearch is shown in the lower section of Figure Agent7: When the search tree is constructed by GraphSearch in the line:add the node to the explored set the algorithm contains at most one copy of each state(city) so we can think of it as growing a tree directly on the statespace graph, as shown in Figure Agent12:
In the next step we expand each of the frontier nodes starting with Zerind, then Sibiu, and finally Timisoara. Following the rules outlined above gives us the following expansion:
On the third pass, we first find out the Oradea is a dead end since Zerind and Sibiu are both now in the explored category. As we start to expand Fagaras we first check to see if Bucharest is the goal state  it is, and the search algorithm terminates, as we have found our goal. Infrastructure for Search AlgorithmsSearch algorithms require a data structure to keep track of the search tree that is being constructed. For each node n of the tree, we have a structure that contains 4 components:
Given the components for a parent node, it is easy to see how to compute the necessary components for a child node. The function ChildNode takes a parent node and an action and returns the resulting child node:
The node data structure is depicted in Figure Agent15. Notice how the Parent pointers string the nodes together into a tree structure. These pointers also allow the solution path to be extracted when a goal node is found; we use the Solution function to return the sequence of actions obtained by following parent pointers back to the root.
Up to now, we haven't been very careful to distinguish between nodes and states, but in writing detailed algorithms it's important to make that distinction. A node is a bookkeeping data structure used to represent the search tree. A state corresponds to a configuration of the world. Thus, nodes are on particular paths, as defined by Parent pointers, whereas states are not. Furthermore, two different nodes can contain the same world state if that state is generated via two different search paths. Now that we have nodes, we need somewhere to put them. The frontier needs to be stored in such a way that the search algorithm can easily choose the next node to expand according to its preferred strategy. The appropriate data structure for this is a queue. The operations on a queue are as follows:
Queues are characterized by the order in which they store the inserted nodes. Three common variants are the firstin, firstout or FIFO queue, which pops the oldest element of the queue; the lastin, firstout or LIFO queue (also known as a Stack), which pops the newest element of the queue; and the priority queue, which pops the element of the queue with the highest priority according to some ordering function. The explored set can be implemented with a hash table to allow efficient checking for repeated states. With a good implementation, insertion and lookup can be done in roughly constant time, independent of the number of states stored. One must take care to implement the hash table with the right notion of equality of states stored. One must take care to implement the hash table with the right notion of equality between states. For example, in the traveling salesperson problem, the hash table needs to know that the set of visited cities: {Bucharest, Urziceni, Vaslui} is the same as {Urziceni, Vaslui, Bucharest}. Sometimes this can be achieved most easily by insisting that the data structures for states be in some canonical form; that is, logically equivalent states should map to the same data structure. In the case of states described by sets, for example, a bitvector representation or a sorted list without repetition would be canonical, whereas an unsorted list would not. Measuring Problem Solving PerformanceBefore we get into the design of specific search algorithms, we need to consider the criteria that might be used to choose among them. We will evaluate an algorithm's performance in 4 ways:
Time and space complexity are always considered with respect to some measure of the problem difficulty. In theoretical computer science, the typical measure is the size of the state space graph, V + E, where V is the set of vertices (nodes) of the graph and E is the set of edges (links). This is appropriate when the graph is an explicit data structure that is input to the search program. (The map of Romania is an example of this.) In Artificial Intelligence, the graph is often represented implicitly by the initial state, actions and transition model and is frequently infinite. For these reasons, complexity is expressed in terms of three quantities:
Time is often measured in terms of the number of nodes generated during the search, and space in terms of the maximum number of nodes stored in memory. For the most part, we will describe time and space complexity for search on a tree; for a graph, the answer will depend on how "redundant" the paths in state space are. To assess the effectiveness of a search algorithm, we can consider just the search cost  which typically depends on the time complexity but can also include a term for memory usage  or we can use the total cost, which combines the search cost and the path cost of the solution found. For the problem of finding a route from Arad to Bucharest, the search cost is the amount of time taken by the search and the solution cost is the total length of the path in kilometers. Thus, to compute the total cost, we have to add milliseconds and kilometers. There is no "official exchange rate" between the two, but, in this case, it might be reasonable to convert kilometers into milliseconds by using an estimate of the car's average speed (because time is what the agent cares about). This enables the agent to find an optimal tradeoff point at which further computation to find a shorter path becomes counterproductive. 
