Search Problems (Russell Norvig)

• This is presented in Russell Norvig Chapter 03: Solving Problems by Searching

• It is closely tied to their presentation of Search Algorithms

Definition

This definition is a direct quote from RN:

A search problem can be defined formally as follows:

• A set of possible states that the environment can be in. We call this the state space.

• The initial state that the agent starts in.

• A set of one or more goal states. Sometimes there is one goal state… sometimes there is a small set of alternative goal states, and sometimes the goal is defined by a property that applies to many states (potentially an infinite number)… We can account for all three of these possibilities by specifying an Is-Goal method for a problem…

• The actions available to the agent. Given a state s, Actions(s) returns a finite set of actions that can be executed in s. We say that each of these actions is applicable in s…

• A transition model, which describes what each action does. Result(s,a) returns the state that results from doing action a in state s.

• An action cost function, dentoted by Action-Cost(s,a,s') when we are programming or \(c(s,a,s’)\) when we are doing math, that gives the numeric cost of applying action a in state s to reach state s’. A problem-solving agent should use a cost function that reflects its own performance measure; for example, for route-finding agents, the cost of an action might be the length in miles… or it might be the time it takes to complete the action.

A sequence of actions forms a path, and a solution is a path from the initial state to a goal state… An optimal solution has the lowest path cost among all solutions.

The state space can be represented as a graph in which the vertices are states, and the directed edges between them are actions.

Formulating Problems

The process of removing detail from a representation is called abstraction. We remove irrelevant details that aren’t relevant to solving the problem. The result is a model - an abstract mathematical description.

A good problem formulation has the right level of detail. Can we be precise about the appropriate level of abstraction?

The abstraction is valid if we can elaborate any abstract solution into a solution in the more detailed world… The abstraction is useful if carrying out each of the actions in the solution is easier than the original problem… 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 be completely swamped by the real world. (p. 84)

Example Problems

The problem-solving approach has been applied to a large range of task environments. RN distinguish between standardized problems which are intended to illustrate or exercise problem-solving methods, and real-world problems, the solutions to which people actually use.

Standardized Problems

Some example standardized problems are given, incluing grid world problems like the robot vacuum example. These problems involve a two dimensional rectangular array of cells, with agents able to move from cell to cell. Cells might contain objects the agent can act on, walls might impede progress. See p. 85 for a formal definition of the vacuum problem in these terms. A sokoban puzzle is another grid world problem, where the agent has to push boxes to the correct storage location.

Another standardized problem set is the set of sliding tile puzzles. A number of tiles/blocks/pieces are arranged in a grid with one or more blank spaces into which they can slide. Famous example is a 3x3 grid with 8 numbered pieces that have to be arranged in sequence.

A final example (from Knuth) is given, with an infinite state space. The problem is to start with the number 4, and then apply a sequence of square root, floor, and factorial operations to provide a desired integer. Infinite state spaces arise often in tasks that involve generating mathematical expressions, circuits, proofs, programs, or any recursively defined object.

Real-world Problems

Route-finding problems can clearly be defined by specified locations and paths between them. Some are straightforward extensions of the toy example, others (like routing video streams, military ops, airline travel-planning) are much more complex. See p. 87 for a spec of airline routing.

Touring problmes extend the goal to involve a set of locations that must be visited (like the travelling salesman problem), with the goal to optimize the overall route cost. These have been used in eg planning movements of warehouse robots and school buses.

VLSI layout problems involve laying out cells and routing channels optimally.

Robot navigation generalizes the route-finding problem with freedom of movement, the robot making its own paths. Advanced techniques are needed to make the continuous search space finite.

Automatic assembly sequencing of complex objects (like motors) has been standard practice for decades. The generation of legal actions is the expensive part. Any practical algorithm must avoid exploring all but a tiny fraction of the state space.