Problem-solving

A problem is a situation which is experienced by an agent as different from the situation which the agent ideally would like to be in. A problem is solved by a sequence of actions that reduce the difference between the initial situation and the goal.

A problem can be analysed into more specific components. First of all it consists of the two situations, the present one which we will call the initial state, and the desired one, which we can call the goal state. The agent's task is to get from the initial state to the goal state by means of series of actions that change the state. The problem is solved if such a series of actions has been found, and the goal has been reached. In general, problem-solving is a component of goal-directed action or control.


In simple control problems, the solution is trivial. For example, the thermostat is a control system or agent whose goal is to reach or maintain a specific temperature. The initial state is the present temperature. The action consists in either heating to increase the temperature or cooling to decrease it. The decision which of these two possible actions to apply is trivial: if the initial temperature is lower than the goal temperature, then heat; if it is higher, then cool; if it is the same, then do nothing. Such problems are solved by a deterministic algorithm: at every decision point there is only one correct choice. This choice is guaranteed to bring the agent to the desired solution.


The situations we usually call "problems" have a more complex structure. There is choice of possible actions, none of which is obviously the right one. The most general approach to tackle such processes is generate and test: apply an action to generate a new state, then test whether the state is the goal state; if it is not, then repeat the procedure. This principle is equivalent to trial-and-error, or to evolution's variation and selection. The repeated application of generate and test determines a search process, exploring different possibilities until the goal is found. Searches can be short or long depending on the complexity of the problem and the efficiency of the agent's problem-solving strategy or heuristic. Searches may in fact be infinitely long: even if a solution exists, there is no guarantee that the agent will find it in a finite time.


Such a search process requires a series of actions, carefully selected from a repertoire of available actions to bring the present state closer to the goal. Different actions will have different effects on the state. Some of these effects will bring the present state closer to the goal, others will rather push it farther away. To choose the best action at every moments of the problem-solving process, the agent needs some knowledge of the problem domain. This knowledge will have the general form of a production rule: if the present state has certain properties, then perform a certain action. Such heuristic knowledge requires that the problem states be distinguished by their properties. This leads us to a further analysis of problems.


Problem states will generally involve objects, which are the elements of the situation that are invariant under actions, and properties or predicates, which are the variable attributes of the objects. A problem state then can be formulated as a combination of propositions, where elementary propositions attribute a particular predicate to a particular object. The different values of the predicates determine a set of possible propositions, and thus of possible states. Since states that differ only in one value of one predicate can be said to be "closer" together than states that differ in several values, the state set gets the structure of a space, ordered by an elementary "distance" function. Actions can now be represented as operators or transformations, which map one element of the state space onto another, usually neighbouring, element.


The final component we need to decide between actions is a selection criterion, which tells the agent which of the several actions that can be applied to a given state is most likely to bring it closer to the goal. In the simplest case, an action consists simply of moving to one of the neighbouring states. Each state will then be associated with a certain value which designates the degree to which it satisfies the goal. This value may be called "fitness". The search space then turns into a fitness landscape, where every point in the space ("horizontal") is associated with a "vertical" fitness value, so that a landscape with valleys and peaks appears. Problem-solving then reduces to "hill-climbing": following the path through the fitness landscape that leads most directly upward.


The efficiency of problem-solving is strongly determined by the way the problem is analysed into separate components: objects, predicates, state space, operators, selection criteria. This is called the problem representation. Changing the problem representation, i.e. analysing the problem domain according to different dimensions or distinctions, is likely to make the problem much easier or much more difficult to solve. States which are near to each other in one representation may be far apart in another representation of the same problem. Therefore, a goal state that could be reached easily in one representation may be virtually impossible to find in another one. Problem representations are usually also models of the situation as experienced by the agent.