Part IV · Ch. 16 — Planning and Search
Symbolic · Planning/decision · State-space search. Finds a sequence of actions that leads from an initial state to a goal. Card:
../02-types-of-ai/01-symbolic.kmd.
🎨 Figure
F-IV.16.0— From the initial state to the goal. Brief: state graph with a path highlighted by A*; expanded vs. pruned nodes; goal flagged.
1. Definition and short history
Solves problems as search over a space of states/actions. Foundation of robotics, logistics and games since the 1970s (STRIPS, Shakey — see Part III, era 2).
2. Foundations
- Graph theory — state spaces as graphs.
- Combinatorics / complexity — explosion of the search space.
- Optimization / heuristics — admissible evaluation functions.
- Logic — representation of actions (preconditions/effects).
3. Algorithms and architectures
- Uninformed search — BFS, DFS, uniform cost.
- Heuristic search — A\*, IDA*, greedy best-first.
- Classical planning — STRIPS, PDDL (actions with precondition/effect).
- Under uncertainty — MDP/POMDP (bridge with RL, ch. 26).
4. Inputs
- Hardware: CPU; search can be intensive.
- Data: domain model (states, actions, costs) — not training data.
- Data structures: priority queue (A*), state graph, closed set.
- Systems: PDDL planners, search libraries.
5. Specialized lifecycle
| Stage | Specialization |
|---|---|
| 0 Problem | Define states, actions, goal, costs |
| 1 Data | Model the domain (PDDL); heuristics |
| 2 EDA | Size of the space, branching factor |
| 3 Modeling | Choose algorithm and admissible heuristic |
| 4 "Training" | There is none — there is modeling of the domain (or learn a heuristic) |
| 5 Evaluation | Optimality, expanded nodes, time |
| 5.5 Acceptance | Edge cases, guarantee of solution |
| 6 Production | Plan online/replan under changes |
| 7 Monitoring | Plan failures, response time |
| 8 Maintenance | Update the domain model |
| 9 Governance | Safety of the planned actions |
6. Capabilities, modes and modalities
Strategic/intellectual: routes, logistics, scheduling, robotics, games; optimal and guaranteed solutions when the domain is modelable.
7. Limits, risks and ethics
Combinatorial explosion; depends on an exact model of the domain; little adaptation to uncertainty/noise (hence the bridge with RL and heuristic learning).
8. State of the art and examples
A* in maps/games, PDDL planners, task and motion planning in robotics; neural-guided search (a network learns a heuristic) links this chapter to neuro-symbolic AI (ch. 32) and to AlphaZero (ch. 27).