PDDL Parser — PDDL to deterministic transition systems

Overview

Classical planning describes a problem declaratively: a set of predicates, a set of actions with preconditions and effects, an initial state and a goal. This tool takes that description and produces the object a graph algorithm actually wants — every reachable state, and every action that leads from one state to another.

Parse

Reads STRIPS-style PDDL with :typing and :negative-preconditions: predicates, typed parameters, conjunctive preconditions and add/delete effects.

Ground

Instantiates every lifted action over the objects of its declared types, so the search operates on fully ground actions.

Explore

Breadth-first search from the initial state, recording every applicable ground action at every reachable state.

Export

Pickles the state-indexed transition table so downstream tools — planners, MDP solvers, attack-graph analysis — can load it directly.

Interactive demo

Edit either file and press Build transition system. This runs a JavaScript port of the Python parser entirely in your browser — nothing is uploaded. The port is checked against the Python implementation and produces identical graphs on every example here.

Example

domain.pddl

problem.pddl

States are labelled by how they differ from the initial state, since planning states share a large common core. Self-loops are drawn as a small arc: an action whose effects already hold does not change the state, but it is still an applicable action and belongs in the graph.

Install

Python 3.7 or newer. The tool itself has no third-party dependencies; pytest is only needed to run the test suite.

git clone https://github.com/leelening/pddl_parser.git
cd pddl_parser

# optional, to run the tests
pip install pytest
pytest

Usage

Command line

python constructor.py examples/domain.pddl examples/problem.pddl

The total number of states: 		 9

Time: 		 0.0007s

The total number of transitions: 		 33

The transition system is written to transitions.pickle in the working directory.

As a library

from constructor import Constructor

transitions, initial_state = Constructor().construct(
    'examples/domain.pddl', 'examples/problem.pddl')

# every state reachable from the initial one
for state, edges in transitions.items():
    for action_label, successor in edges.items():
        ...

Inspecting a parse

python PDDL.py examples/domain.pddl examples/problem.pddl

Prints the token tree, every parsed action with its preconditions and effects, and the problem's objects, initial state and goals — the fastest way to see how a file was understood.

Reloading the pickle

import pickle

with open('transitions.pickle', 'rb') as handle:
    transitions, initial_state = pickle.load(handle)

print(len(transitions), 'states')
print(transitions[initial_state])   # {action_label: successor_state}

How it works

Three files, each one stage of the pipeline.

File	Role
`PDDL.py`	Tokenizes the s-expressions and turns them into a domain (predicates, typed actions) and a problem (objects, initial state, goals). PDDL is case-insensitive, so all identifiers are folded to lower case.
`action.py`	Holds one action. `groundify()` instantiates a lifted action over every combination of objects of its parameter types; `label()` in `constructor.py` gives each grounding a unique key.
`constructor.py`	Grounds every action, then breadth-first searches from the initial state, recording each applicable action and the state it leads to.

The state update

A STRIPS action is applicable in a state when all of its positive preconditions hold and none of its negative preconditions do. Applying it deletes its delete-effects and then adds its add-effects — deletion first, so a fact that is both deleted and added survives.

def apply(self, state, positive, negative):
    new_state = []
    for i in state:
        if i not in negative:
            new_state.append(i)
    for i in positive:
        if i not in new_state:
            new_state.append(i)
    return new_state

A state is a set of ground facts, so convert() sorts and deduplicates the facts before the result is used as a dictionary key. Skipping that step is what made the same state appear under several different keys — see the fixes below.

Output format

The pickle holds [transitions, initial_state].

Value	Type	Meaning
`state`	`tuple[tuple[str, ...], ...]`	A sorted, deduplicated tuple of ground facts; each fact is the predicate name followed by its arguments, e.g. `('at', 'ana', 'p1')`.
`transitions`	`dict[state, dict[str, state]]`	For every reachable state, a mapping from action label to successor state.
action label	`str`	`name` for a parameterless action, otherwise `name(arg1,arg2)` — unique per grounding.
`initial_state`	`state`	The problem's `:init`, canonicalized. Always a key of `transitions`.

Every successor is itself a key of transitions, so the structure is a closed graph: you can walk it without bounds checks.

Fixed bugs

The bundled attack-graph example used to report 19 states and 18 transitions. The reachable state space actually has 9 states and 33 transitions. Six defects accounted for the difference; a regression test pins down each one.

state space States were keyed by insertion order

A state is a set of facts, but it was stored as a list and keyed by that list's order. Reaching {a, b} by adding a then b produced a different key from reaching it the other way round, so a single state was explored and recorded several times over — the reported state count grew combinatorially with the number of independent action orderings. Sorting the facts makes the key canonical.

before

def convert(list):
    return tuple(i[0] for i in list)

after

def convert(state):
    return tuple(sorted(set(
        tuple(i) for i in state)))

missing edges Transitions into known states were dropped

The edge was only recorded inside the branch that discovered a new state, so every transition leading back into an already-visited state vanished — including every self-loop. Goal states came out with no outgoing edges at all, which makes the result useless as a transition system for an MDP or a model checker. The edge is now recorded for every applicable action, independently of whether the successor is new.

before

if new_state not in visited:
    visited.append(new_state)
    need_visit.append(new_state)
    transitions[...][act.name] = ...

after

transitions[key][label(act)] = new_key
if new_key not in visited:
    visited.add(new_key)
    need_visit.append(new_state)

collision Groundings of one action overwrote each other

Edges were keyed by act.name, which every grounding of a lifted action shares. With move(ana,p1,p2) and move(ana,p1,p3) both applicable, only one survived in the dictionary — the graph silently lost the other branch. Edges are now keyed by label(act), which includes the arguments.

crash A goal true in the initial state raised ValueError

construct() returned a bare [] in that case, while every caller unpacks two values — including its own __main__ block. Worse, the early return threw away the rest of the reachable state space: the goal is not a search cutoff, and a goal state reached later is expanded like any other. Both are fixed — try the Goal already true initially example above.

state space Fact arguments were discarded

Each fact was reduced to its predicate name, so at(ana,p1) and at(ana,p2) collapsed into the same fact at. That is harmless for a MulVAL attack graph, where every predicate takes the same single object, but it silently corrupts any domain with more than one object per predicate. Facts now keep their arguments.

state space A repeated `:init` fact created a phantom state

convert() sorted the facts but never deduplicated them, while apply() never emits a repeated fact. So (:init (at ana p1) (at ana p1)) left the initial state under a key no action could ever produce again — an extra node hanging off the front of the graph.

robustness Smaller fixes

Action defined __eq__ without __hash__, which makes a class unhashable in Python 3; replace() substituted parameters one at a time, re-scanning tokens it had already substituted, and groundify() raised a bare KeyError for a parameter type the problem declares no objects for; :objects a - pos b - pos kept only the last group of a repeated type; parse_problem() failed with an AttributeError when called before parse_domain(); the module shadowed the str and list builtins; visited was a list, making membership checks linear in the size of the state space; and the README advertised a pandas dependency the code never imported.

Regression tests

pytest -q
................................                                [100%]
32 passed

Each defect above has a test named test_bug_* in tests/test_parser.py, so a regression fails loudly rather than quietly changing a state count.

MulVAL integration

The tool was written for attack-graph analysis, where the "planner" is an attacker and the plan is an exploit chain.

Run MulVAL over a network description to get an attack graph.
Convert it with MulVAL-to-PDDL, which emits the domain.pddl / problem.pddl pair.
Build the transition system with this tool.
Analyse the graph: shortest exploit chain, reachability of a privileged state, or an MDP over attacker actions.

In that encoding each MulVAL derivation rule becomes an action, each network fact a predicate, and the goal is the compromise you are testing for. The bundled example is exactly that: two hosts, an OpenSSH and an OpenSSL vulnerability, and a goal of code execution on both.

Limitations

STRIPS only: :strips, :typing and :negative-preconditions. No numeric fluents, conditional effects, durative actions, disjunctive preconditions, quantifiers or derived predicates.
Type hierarchies are not resolved — a parameter of type t is grounded over the objects declared exactly as t.
The state space is enumerated exhaustively, so it must be finite and small enough to hold in memory. Grounding cost grows as the product of the type domain sizes.
Effects are deterministic by construction; the result is a transition system, not a probabilistic model.
The browser demo stops exploring at 6,000 states and draws at most 90 of them. A capped build is still a closed graph — a prefix of the reachable state space — but run the Python tool for anything larger.