Home / 4. Symbolic AI / Search and state spaces

Search and state spaces

When the goal is a future situation, model actions as edges between states and search for a path.

Observable facts define the current state. Actions move you to new states. Draw a graph: nodes = states, edges = actions. Solving = find a path from start to goal (and remember visited nodes so cycles do not loop forever).

Printer paper jam

Four states: jammed/cleared × lid open/closed. Actions: open lid, close lid, remove jam (only works if open).

Start: jammed + closed. Goal: cleared + closed. One sensible path: open → remove jam → close.

JC jammed+closed JO jammed+open CC cleared+closed CO cleared+open open remove jam close Goal path: JC → JO → CO → CC
State graph for the printer jam: start JC, goal CC.

Key takeaways

  • State + actions = graph.
  • Goal finding = path search.
  • Track visited states to avoid cycles.