Problem Solving
Problem solving, in the sense used in artificial intelligence, is the process by which an agent that has been given or has chosen a goal finds a sequence of actions that achieves it. The classic recipe has four steps: formulate a goal, formulate the problem (decide which states and actions to consider), search for a sequence of actions that reaches the goal, and execute that sequence. The scope is narrower than the everyday phrase suggests. It covers well-defined situations in which the world can be modelled, the possible moves enumerated and success recognized, and it leaves out the muddier human activity of noticing that something is a problem in the first place.
The foundations were laid by Allen Newell and Herbert Simon, whose 1972 book Human Problem Solving gave the field its vocabulary and its method. Working with Cliff Shaw from the mid-1950s, they built the Logic Theorist and then the General Problem Solver as programs meant to model how people think, not merely to produce answers. Human Problem Solving gathered more than a decade of experiments in which subjects solved cryptarithmetic puzzles, logic problems and chess positions while talking aloud, and the transcripts, called protocols, were compared with the traces of simulating programs. Their central claim was that a problem solver works inside a problem space, a set of knowledge states connected by operators, and that skill lies in selecting operators with knowledge about where promising paths lie. Brain, mind and machine were treated as instances of one information-processing system.
The AI problem-solving agent is a deliberately simple design, which is its strength and its limit. Given a goal, it constructs a model of the relevant world, runs a search such as breadth-first, uniform-cost or A-star over the resulting states, and then carries out the resulting plan, typically without looking at the environment again. This open-loop execution is safe only when the environment is observable, deterministic and static. If actions can fail, the world changes, or the agent can see only part of it, the plan must be monitored, revised or replaced by contingent strategies, which is where conditional planning, replanning and decision-theoretic methods begin. Formulation is where much of the skill lies, since the right abstraction can make a problem trivial and the wrong one makes it impossible.
Problem solving is often confused with two neighboring ideas, and the differences are worth stating exactly. Optimization asks for the best setting of some variables under an objective, as in fitting a curve or allocating a budget; it may involve no sequence of steps at all, and the solver usually does not care how it got there. Search-based problem solving cares about the path, a series of actions through states. Learning, for its part, improves a system's behaviour from data, and a learner may have no explicit model to search. The boundaries are porous: a shortest-path computation is an optimization; reinforcement learning learns to solve sequential problems; planning can be learned. But conflating them hides what each needs, namely a model and a goal for search, an objective for optimization, and data or experience for learning.
A widespread misconception is that the general in the General Problem Solver meant generality of competence. The program separated task knowledge from a general-purpose method (means-ends analysis), which was a real conceptual advance, but it could handle only problems that had been carefully encoded in its own terms, and it scaled poorly. The lesson drawn in the 1970s was that strong methods need strong domain knowledge, which led to expert systems, while the weak methods remained useful as scaffolding. Another pitfall is equating human problem solving with search alone: Newell and Simon's own subjects relied on recognition, analogy and learned chunks as well, a theme later developed in studies of expert chess players.
The framework remains current wherever agents must reach goals. Route finding, scheduling, robotic planning, theorem proving and game playing use classical search; AlphaGo-style systems combine tree search with learned evaluation; and recent work on large language models, for example Tree of Thoughts in 2023, explicitly casts reasoning as search over intermediate steps, with the model proposing and scoring candidate moves. The vocabulary of goals, states, operators and plans that Newell and Simon fixed in the 1950s and 1960s is still how researchers describe such systems.
Read problem solving as goal-directed search through a modelled space of possibilities: its power comes from choosing a good formulation and good guidance, and its boundary is the set of situations in which that model can be written down.