Search and Problem Solving
Search and problem solving is the branch of artificial intelligence concerned with formulating tasks as the exploration of a space of states or configurations and finding sequences of actions, assignments, or moves that reach a goal.
Definition
Search-based problem solving represents a task as an initial state, a set of actions that transform states, a goal test, and a path cost, and solves it by systematically exploring the reachable states until a goal state (or a least-cost path to one) is found.
Scope
This area covers the formulation of problems as state spaces and the algorithms that explore them: uninformed (blind) search such as breadth-first and depth-first, informed (heuristic) search such as A* and greedy best-first, adversarial search for two-player games, and constraint satisfaction. It treats how problems are modelled as states, actions, and goal tests, and how completeness, optimality, time, and space are analysed. It excludes learning the search heuristics or evaluation functions from data, which belongs to the separate machine-learning subfield.
Sub-topics
Core questions
- How is a real-world task formulated as a state space with states, actions, and a goal test?
- When is a search algorithm complete (guaranteed to find a solution if one exists) and optimal (guaranteed to find a least-cost solution)?
- How does a heuristic function guide search toward the goal while preserving optimality?
- How can the combinatorial explosion of the state space be controlled by pruning or informed ordering?
- How does search change when an adversary is choosing some of the moves?
Key concepts
- state space
- search tree and search graph
- uninformed (blind) search
- heuristic function
- admissibility and consistency
- A* search
- branching factor and search depth
- completeness and optimality
- constraint satisfaction
Key theories
- Admissible heuristics and A* optimality
- If a heuristic never overestimates the true cost to the goal (is admissible), A* search expands nodes in best-first order of f = g + h and is guaranteed to return an optimal solution; consistency additionally guarantees no node is re-expanded.
- Uninformed vs. informed search trade-off
- Blind strategies (breadth-first, uniform-cost, depth-first, iterative deepening) differ only in node ordering and offer guarantees without domain knowledge, whereas heuristic estimates of remaining cost can dramatically reduce the explored space at the risk of losing optimality if the heuristic is inadmissible.
- Problem formulation as state-space search
- A wide range of tasks become tractable once cast as search over states connected by actions, making the choice of state representation and operators a central design decision that determines branching factor and solution depth.
Clinical relevance
Search underlies a huge range of practical systems: route planning and navigation (A* on road networks), puzzle and game engines, automated configuration and scheduling, robot motion planning, and as the backbone of automated planning and constraint solvers used in logistics and operations research.
History
Search was central to AI from its earliest days, with Newell and Simon's General Problem Solver (late 1950s) framing intelligence as search through problem spaces. The A* algorithm (Hart, Nilsson, Raphael, 1968) gave heuristic search a rigorous optimality footing, and Pearl's 1984 monograph systematized heuristic search theory. The framework remains a standard organizing lens in AI textbooks.
Key figures
- Nils J. Nilsson
- Judea Pearl
- Peter E. Hart
- Bertram Raphael
- Allen Newell
- Herbert A. Simon
Related topics
Seminal works
- hart1968
- pearl1984
- russell2020
Frequently asked questions
- What is the difference between uninformed and informed search?
- Uninformed (blind) search, such as breadth-first or depth-first search, uses no information about how close a state is to the goal and explores purely by the structure of the state space. Informed (heuristic) search uses an estimate of the remaining cost to the goal to prioritize which states to expand, which can be far more efficient.
- Why is A* so widely used?
- A* combines the actual cost from the start (g) with a heuristic estimate to the goal (h), and when the heuristic is admissible it is guaranteed to find an optimal solution while typically exploring far fewer states than uninformed search. This balance of optimality and efficiency makes it a default choice for pathfinding.