Visual Graphplan Solver

 

An interactive, didactic web app that is, to every effect, a real Graphplan solver (Blum & Furst, 1997) — not just a static diagram generator. Given a propositional STRIPS domain, the engine actually expands the planning graph, computes every mutex, runs the goal test, and performs backward plan extraction with backtracking to either produce a valid, executable plan or correctly prove the problem unsolvable. The visual layer on top builds, renders, and explains that solving process step by step: the alternating layers of the planning graph, the persistence (no-op) actions, the mutex relations between actions and between literals, the goal test at each level, the level-off condition, and the backward extraction of the plan.

Try it now: visual-graphplan-solver.vercel.app

Screenshots

Planning graph as rendered by the app:

Custom-problem editor:

Goal of the Project

The app is a single-page solver and teaching tool, not an industrial-scale planner — the scope is deliberately small propositional domains rather than large grounded PDDL problems. Within that scope it solves for real: it does not pre-script or fake the plans it shows, it derives them by actually running Graphplan's expansion and backward-extraction algorithm on whatever domain is loaded, built-in or user-supplied. The focus is making the solving process observable: graph construction, insertion of persistence actions, computation of mutexes, goal testing, and backward plan extraction, all visible at every step. The target user is a student or a teacher who wants to see both the answer and exactly how Graphplan got there.

The engine is intentionally separated from the user interface, so the solving logic can be read, tested, and reused independently of the visualization.

Quick Start

Requirements: Node.js 18 or newer.

npm install
npm run dev        # development server at http://localhost:5173

Other commands:

npm test           # engine unit + scenario tests (Vitest)
npm run build      # production build into dist/
npm run preview    # serve the production build

Features

• Expansion of the planning graph as an alternating sequence of state and action levels (S0, A0, S1, A1, …).
• Automatic no-op (persistence) actions for every literal present at a level, treated as first-class actions but clearly marked.
• Action mutexes: inconsistent effects, interference, competing needs.
• Proposition mutexes: negation (user-declared complementary pairs) and inconsistent support.
• Goal test at every level: all goals present and no goal pair mutually exclusive.
• Backward plan extraction with backtracking, plus an outer expand-then-extract loop so problems that need extra levels (goal interactions such as the Sussman anomaly or Have-Cake) are solved correctly.
• Level-off detection: the graph is marked stabilized when a new level adds no propositions and does not change the mutex set. If goals are still not extractable, the problem is reported as unsolvable.
• Three input formats for custom problems: Form, JSON, and PDDL (lifted domain + problem, grounded on the fly).
• Contextual explanation panel that justifies, in readable form, why a node or a mutex exists.

Interface

Three panels:

• Left — domain selector, initial state and goals, step-by-step controls (stepper and slider to reveal the graph one level at a time), plan extraction, view toggles (mutexes, no-ops, dependencies, plan-only), light/dark theme, and JSON export of the current graph.
• Center — the planning-graph canvas. Layout is deterministic and level-based, never force-directed, mirroring Graphplan's layered temporal and causal structure. Propositions are pills, actions are cards, no-ops are dashed cards, goals are highlighted, mutexes are dashed red arcs, and the extracted plan is shown with a colored glow. On startup no domain is loaded: an empty canvas invites you to pick a demo or add a problem.
• Right — a collapsible explanation panel. Click a node or a mutex for its formal justification; when nothing is selected it shows the algorithm state, the extracted plan, and the backward regression step by step.

Demo Domains

Domain	Teaching purpose
Gripper (simplified)	Solvable in a few levels: pick at A, move A→B, drop at B.
Blocksworld (2 blocks)	Solvable: pickup A, then stack A on B.
Rocket (parallel actions)	Parallel actions in the same level: load both packages, fly, unload both.
Spare Tire	Classic Russell & Norvig example: mounting the spare tire.
Sussman Anomaly (3 blocks)	Goal interaction: the subgoals cannot be achieved independently. Optimal six-step plan.
Monkey and Bananas	Textbook AI planning problem: go, push, climb, grab.
Have Cake and Eat It	Goals present but mutex at S1, extractable at S2.
Vault	Unsolvable: the key is missing, the graph levels off immediately.

Custom Problems

The Aggiungi problema button, under the domain selector, opens an editor with three modes. All of them go through the same validation and limits.

• Form — fields for name, initial state, goals, and a list of actions, each with preconditions, add effects, and delete effects (atoms separated by spaces or commas). Required fields are marked with a red asterisk; a popup lists any that are missing on submit. Literals are derived automatically from what you use.
• JSON — paste a problem, or load a .json file. Schema: { name, actions[], init[], goals[], literals?, complementary? }.
• PDDL — paste or load a lifted domain and problem (.pddl). Actions are grounded over the declared objects and pruned by type. See examples/pddl for ready-to-load pairs.

Mutexes stay automatic (computed by the engine). You may optionally declare complementary literal pairs (e.g. light-on / light-off) that exclude each other by nature and that the engine cannot infer structurally.

Validation is live: errors, warnings (such as an unreachable goal), and the list of detected literals update as you type. Custom problems are stored in localStorage, appear in the selector under a separate group, and can be downloaded as JSON or deleted.

Minimal importable JSON:

{
  "name": "Light Switch",
  "actions": [
    {
      "name": "turn on",
      "preconditions": ["off"],
      "addEffects": ["on"],
      "delEffects": ["off"]
    },
    {
      "name": "turn off",
      "preconditions": ["on"],
      "addEffects": ["off"],
      "delEffects": ["on"]
    }
  ],
  "init": ["off"],
  "goals": ["on"]
}

How the Solver Works

A few design decisions worth knowing:

• Positive STRIPS. No negative preconditions. Complementary states are modeled with distinct literals plus delete effects (have-cake / no-cake), which keeps the model small: negation mutexes then fall out of inconsistent effects → inconsistent support automatically.
• Two separated phases. graphplan.ts builds an immutable PlanningGraph (levels + mutexes); extract.ts only reads it. Each half is testable in isolation, and solver.ts drives the outer expand-then-extract loop.
• No-ops as first-class actions. noop:<lit> (pre = add = {lit}) participate in mutex computation and extraction, so literal persistence is handled correctly, yet they stay distinguishable in the data and UI.
• Precomputed explanations. Every mutex carries its reason and a textual explanation; the UI never recomputes why a mutex exists at render time.
• Deterministic layout. view/serialize.ts places nodes by level (column) and sorted index (row) — never force-directed, so the same graph always renders identically.

Limits

To keep the planning graph small enough to expand and extract in the browser without freezing, custom problems are capped at 60 literals, 120 actions, 20 goals, 12 preconditions/effects per action, 60 initial literals, and 14 expansion levels. Plan extraction additionally aborts after a fixed search budget so a pathological instance can never hang the tab; in practice all demo domains and reasonably sized custom problems solve in a few milliseconds.

Architecture

The engine is fully separated from the user interface.

src/
  engine/                # Graphplan engine (no UI dependency)
    types.ts             #   data model: Literal, Action, StateLevel, ...
    graphplan.ts         #   level expansion, mutexes, goal test, level-off
    extract.ts           #   backward extraction with backtracking + budget
    solver.ts            #   outer loop expand -> extract -> repeat
    validate.ts          #   validation / normalization + LIMITS
    pddl.ts              #   PDDL parser + grounder -> raw problem
    domains.ts           #   built-in demo problems
    *.test.ts            #   engine tests (expansion, mutexes, PDDL, ...)
  view/
    serialize.ts         # visualization mapper: PlanningGraph -> visual model
  ui/                    # React: layout, canvas, panels, styles
    App.tsx
    GraphCanvas.tsx
    ExplanationPanel.tsx
    ProblemBuilder.tsx   #   custom-problem editor (Form / JSON / PDDL)
    styles.css
examples/                # demo problems (JSON) and PDDL domain/problem pairs

License

MIT — see LICENSE. Author: Diego Scirocco.