Russell Norvig Chapter 03: Solving Problems by Searching
Metadata
Title: Solving Problems by Searching
Number: 3
Related Notes: Search Problems; Search Algorithms
<- Previous Russell Norvig Chapter 02: Intelligent Agents
Coverage
The chapter covers search algorithms that an agent can use to select action sequences in environments that are episodic, single agent, fully observable, deterministic, static, discrete, and completely known. It is a meaty chapter, most sections are broken into separate notes:
3.1 Problem Solving Agents
3.2 Search Problems
3.4 Uninformed Search Strategies
3.5 Informed (heuristic) Search Strategies
Summary
Before an agent can start searching, a well-defined problem must be formulated.
A problem consists of five parts: the initial state, a set of actions, a transition model describing the results of these actions, a set of goal states, and an action cost function.
The environment of the problem is represented by a state space graph. A path through the state space (a sequence of actions) from the initial state to a goal state is a solution.
Search algorithms treat states and actions as atomic, without any internal structure (although features of states come into play when it comes to learning heuristics).
Search algorithms are judged on the basis of completeness, cost optimality, time complexity, and space complexity.
Key Quotes
When the correct action to take is not immediately obvious, an agent may need to plan ahead: to consider a sequence of actions that form a path to a goal state. Such an agent is called a problem-solving agent, and the computational process it undertakes is called a search. Problem solving agents use atomic representations… that is, states of the world are considered as wholes, with no internal structure visible to the problem-solving algorithms. Agents that use factored or structured representations of states are called planning agents. (p. 81)
We distinguish between informed algorithms, in which the agent can estimate how far it is from the goal, and uninformed algorithms, where no such estimate is available.
Problem Solving Agents
Imagine you are travelling in a foreign country. You need to catch a flight from the capital that day, but you are in another city. Driving out of the city you see three roads forking. The road signs each list a different city, not the capital. Which road do you take?
If you have no additional information, ie the environment is unknown, you can do no better than choose a path at random. This situation is discussed elsewhere (next chapter). Here we assume that the agent has information about the world. They consider first the most simple environemnts: episodic, single agent, fully observable, deterministic, static, discrete, and known. More complex environments are covered in the next chapter.
With these situations, the agent can follow a four-phase problem-solving process:
Goal formulation: The agent adopts a goal (eg reaching the capital). “Goals organize behaviour by limiting the objectives and hence the actions to be considered.”
Problem formulation: The agent devises a description of the states and actions needed to reach the goal - a model of the relevant part of the world. In the travelling example, we could just model the fact of moving from one city to another with a single state change, the current city.
Search: The agent simulates sequences of actions in the model, searching until it finds a sequence of actions that reaches the goal. Such a sequence is called a solution. The agent may have to simulate multiple sequences before a solution is found, or it might conclude that no solution is possible.
Execution: The agent can execute the actions in the solution, one at a time.
It is an important property that in a fully observable, deterministic, known environment, the solution to any problem is a fixed sequence of actions… If the model is correct, then once the action has found a solution, it can ignore its percepts while it is executing the actions.
Contrast with partially observable, or nondeterministic environments where solutions would be branching paths recommending different actions depending on what future percepts arrive.
Search Problems
The rest of the chapter explains the concept of search problems and search algorithms. These concepts are so critical that they are separated out into separate notes.
Here is the note on Search Problems.
Search Algorithms
The chapter presents a general overview of Search Algorithms, including the procedural abstraction of best-first search, common data structures used in such algorithms, and performance measures used to evaluate algorithms.
Uninformed Search Strategies
The chapter compares several different Uninformed Search Strategies, namely:
Breadth-first Search: expands the shallowest nodes first; it is complete, optimal for unit action costs, but has exponential space complexity.
Uniform-cost Search or Dijkstra’s algorithm: expands the node with the lowest path cost, it is optimal for general action costs.
Depth-first Search: expands the deepest unexpanded node first. It is neither complete nor optimal, but has linear space complexity.
Depth-limited and iterative deepening Search: Depth-limited search adds a depth bound to depth-first search. Iterative deepening search calls depth-limited search with increasing depth limits until a goal is found. It is complete when full cycle checking is done, optimal for unit action costs, has time complexity comparable to breadth-first search, and has linear space complexity.
Bidirectional Search: expands two frontiers, one around the initial state, and one around the goal, stopping when the frontiers meet.
Informed Search Strategies
The chapter then compares major Informed (Heuristic) Search Strategies
It looks at Greedy Best-First Search and A* Search before focusing on how to handle the issue of memory management.
Heuristic Functions
The chapter concludes by looking at Heuristic Functions, how to evaluate them, and how to generate them.