graphplan

graphplan

Package graphplan implements the Graphplan planning algorithm (Blum & Furst 1997) for STRIPS and ADL planning domains.

It constructs a planning graph and uses backward-chaining search with memoization to find shortest parallel plans. ADL support includes disjunctive preconditions, conditional effects, universally/existentially quantified formulas, and derived predicates (axioms) computed via fixed-point evaluation.

Key Types

• Domain -- types, predicates, operator templates, and axioms
• Problem -- objects, initial state, and goal propositions
• Operator -- action template with Formula preconditions and effects
• Axiom -- derived predicate rule (head predicate + Formula body)
• Formula -- interface for logical formulas (And, Or, Imply, Forall, Exists, When, Atom)
• Solver -- runs the extend/search loop
• SolverConfig -- optional settings (e.g. max graph levels)
• PlanStep -- one time step of parallel actions in the result

Usage

Build a Domain and Problem, create a Solver, call Solve:

domain := &graphplan.Domain{
    Name:       "logistics",
    Types:      []graphplan.Type{{Name: "pkg", Parent: "object"}},
    Predicates: []graphplan.Predicate{{Name: "at", ParamTypes: []string{"pkg", "place"}}},
    Operators:  []graphplan.Operator{ /* ... */ },
}

problem := &graphplan.Problem{
    Name:         "deliver",
    Domain:       domain,
    Objects:      []graphplan.Object{{Name: "p1", Type: "pkg"}},
    InitialState: []graphplan.Proposition{{Predicate: "at", Args: []string{"p1", "src"}}},
    Goals:        []graphplan.Proposition{{Predicate: "at", Args: []string{"p1", "dst"}}},
}

solver, err := graphplan.NewSolver(nil)
if err != nil {
    log.Fatal(err)
}

plan, err := solver.Solve(problem)
if err != nil {
    log.Fatal(err)
}

for _, step := range plan {
    for _, a := range step.Actions {
        if !a.IsNoOp() {
            fmt.Println(a)
        }
    }
}

See examples/rocket/ for a complete working example.