3 Searching for Solutions

3.1 Problem Solving as Search

In the simplest case of an agent deciding what it should do, the agent has a perfect model of the world, with no uncertainty, and a goal to achieve. This is either a flat (non-hierarchical) representation or a single level of a hierarchy.

This problem can be abstracted to the mathematical problem of finding a path from the start node to a goal node in a directed graph. Many other problems can also be mapped to this abstraction, so it is worthwhile considering this level of abstraction. Most of this chapter explores various algorithms for finding such paths.

Example 3.1.

Computer maps provide path finding: showing how to go (drive, ride, walk, or take transit) from one location to another. Finding the best route from a current location to a destination is a search problem. The state includes mode of transportation (e.g., on foot or on a bus), the location of the traveler, and the direction of travel. A legal route will include the roads (going the correct way down one-way streets) and intersections the traveler will traverse.

The best route could mean

  • •

    the shortest (least distance) route

  • •

    the quickest route

  • •

    the route that uses the least energy

  • •

    the lowest-cost route, where the cost takes into account time, money (e.g., fuel and tolls), and the route’s attractiveness.

Finding the shortest route is usually easiest to implement, because maps contain distances and they can be assumed to not change, ignoring detours due to roadworks or accidents. Estimating the time or the energy used is more difficult. The route planner might need to take into account regular traffic volumes, as well as local conditions, such as the weather or accidents. To estimate the time, machine learning algorithms can be used.

This example is discussed more in Section 3.9 on social issues.

This notion of search is computation solely inside the agent. It is different from searching in the world, when an agent may have to act in the world; for example, a robot searching for keys, lifting up cushions, and so on. It is also different from searching the Web, which involves searching for information by indexing huge amounts of data and trying to find the best response for each search query. Searching in this chapter means finding a path to a goal node in a graph.

Search underlies much of AI. When an agent is given a problem, it is usually given only a description that lets it recognize a solution, not an algorithm to solve it. It has to search for a solution. The existence of NP-complete problems, with efficient means to recognize solutions but no efficient methods for finding them, indicates that searching is a necessary part of problem solving.

It is often believed that humans are able to use intuition to jump to solutions to difficult problems. However, humans cannot find optimal solutions to computationally difficult problems. Humans do not tend to solve general problems; instead, they solve specific instances about which they may know much more than the underlying search space. They often do not find optimal solutions, but find satisficing, or good enough, solutions. Problems with little structure, or ones in which the structure cannot be related to the physical world, are very difficult for humans to solve. The existence of public key encryption codes, where the search space is clear and the test for a solution is given – which humans nevertheless have no hope of solving and computers cannot solve in a realistic time frame – demonstrates the difficulty of search.

The difficulty of search and the fact that humans are able to solve some search problems efficiently suggests that computer agents should exploit knowledge about special cases to guide them to a solution. This extra knowledge beyond the search space is called heuristic knowledge. This chapter considers one kind of heuristic knowledge in the form of an estimate of the cost from a node to a goal.