graphplan

package
v0.2.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 10, 2026 License: MIT Imports: 6 Imported by: 0

README

graphplan

Package graphplan implements the Graphplan planning algorithm (Blum & Furst 1997) for STRIPS domains with typing and equality constraints.

It constructs a planning graph and uses backward-chaining search with memoization to find shortest parallel plans.

Key Types

  • Domain -- types, predicates, and operator templates
  • Problem -- objects, initial state, and goal propositions
  • 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.

Documentation

Overview

Package graphplan implements the Graphplan algorithm for solving STRIPS planning problems. It constructs a Planning Graph and uses backward-chaining search with memoization to find shortest parallel plans.

Index

Constants

This section is empty.

Variables

View Source 
var (
	// ErrNoValidPlan indicates no valid plan exists for
	// the given problem.
	ErrNoValidPlan = errors.New("no valid plan exists")

	// ErrMaxLevelsExceeded indicates the solver hit the
	// configured level cap without finding a plan.
	ErrMaxLevelsExceeded = errors.New(
		"max levels exceeded",
	)
)

Functions

This section is empty.

Types

type Action 

type Action struct {
	Operator      string
	Args          []string
	Preconditions []Proposition
	AddEffects    []Proposition
	DeleteEffects []Proposition
}

Action is a grounded operator with all parameters bound to concrete objects.

func GroundActions 

func GroundActions(
	domain *Domain,
	objects []Object,
) []Action

GroundActions instantiates all operators with all type-compatible object bindings. It handles :equality constraints (neq) by filtering at grounding time.

func (*Action) IsNoOp 

func (a *Action) IsNoOp() bool

IsNoOp returns true if this is a frame/no-op action that preserves a single proposition across time steps.

func (*Action) Key 

func (a *Action) Key() string

Key returns a unique string key for map lookups.

func (*Action) String 

func (a *Action) String() string

String returns the human-readable representation.

type Domain 

type Domain struct {
	Name       string
	Types      []Type
	Predicates []Predicate
	Operators  []Operator
	Constants  []Object
}

Domain holds the complete STRIPS domain definition.

type Graph 

type Graph struct {
	// contains filtered or unexported fields
}

Graph is a directed, leveled planning graph alternating between proposition levels and action levels as described by Blum & Furst (1997).

func NewGraph 

func NewGraph(prob *Problem) *Graph

NewGraph creates a planning graph with proposition level 0 containing the initial state. Negative propositions are seeded via the closed-world assumption for predicates used in negative preconditions.

func (*Graph) ActLevelSize 

func (g *Graph) ActLevelSize(level int) int

ActLevelSize returns the number of actions at the given level.

func (*Graph) ActionsAreMutex 

func (g *Graph) ActionsAreMutex(
	level int,
	actA, actB *Action,
) bool

ActionsAreMutex returns true if two actions are mutually exclusive at the given action level.

func (*Graph) Extend 

func (g *Graph) Extend()

Extend adds one action level and one proposition level to the graph.

func (*Graph) GoalsReachable 

func (g *Graph) GoalsReachable(
	goals []Proposition,
	level int,
) bool

GoalsReachable returns true if all goals exist at the given proposition level and no pair is mutex.

func (*Graph) HasProp 

func (g *Graph) HasProp(
	level int,
	prop Proposition,
) bool

HasProp returns true if proposition prop exists at the given proposition level.

func (*Graph) Leveled 

func (g *Graph) Leveled() bool

Leveled returns true if the last two proposition levels are identical (same props and same mutexes).

func (*Graph) NumPropLevels 

func (g *Graph) NumPropLevels() int

NumPropLevels returns the number of proposition levels.

func (*Graph) PropLevelSize 

func (g *Graph) PropLevelSize(level int) int

PropLevelSize returns the number of propositions at the given level.

func (*Graph) PropsAreMutex 

func (g *Graph) PropsAreMutex(
	level int,
	prop, other Proposition,
) bool

PropsAreMutex returns true if two propositions are mutually exclusive at the given proposition level.

func (*Graph) Search 

func (g *Graph) Search(
	goals []Proposition,
) ([]PlanStep, bool)

Search attempts to extract a valid plan from the current graph. Returns the plan steps and true if successful, or nil and false if no plan can be extracted. Uses backward-chaining with memoization.

type Literal 

type Literal struct {
	Predicate string
	Args      []string // variable names like "?r", "?p"
	Negated   bool
}

Literal is an ungrounded predicate reference used in operator preconditions and effects.

type Object 

type Object struct {
	Name string
	Type string
}

Object is a typed object in the problem.

type Operator 

type Operator struct {
	Name          string
	Parameters    []Parameter
	Preconditions []Literal
	AddEffects    []Literal
	DeleteEffects []Literal
}

Operator defines an operator template with typed parameters, preconditions, and effects.

type Parameter 

type Parameter struct {
	Name string // e.g. "?r"
	Type string // e.g. "rocket"
}

Parameter is a typed variable in an operator.

type PlanStep 

type PlanStep struct {
	Actions []Action
	Time    int
}

PlanStep is one time step in the output plan, containing a set of non-interfering parallel actions.

type Predicate 

type Predicate struct {
	Name       string
	ParamTypes []string
}

Predicate defines a predicate template with typed parameter slots.

type Problem 

type Problem struct {
	Name         string
	Domain       *Domain
	Objects      []Object
	InitialState []Proposition
	Goals        []Proposition
}

Problem defines a planning problem: a domain, objects, initial state, and goal propositions.

type Proposition 

type Proposition struct {
	Predicate string
	Args      []string
	Negated   bool
}

Proposition is a grounded predicate — fully instantiated with concrete objects. When Negated is true, it represents the absence of the fact (closed-world assumption).

func GroundPredicates added in v0.2.0 

func GroundPredicates(
	domain *Domain,
	objects []Object,
	predicateNames map[string]bool,
) []Proposition

GroundPredicates enumerates all type-compatible ground instances of the given predicates. It reuses buildTypeIndex and enumerateBindings to generate all valid argument combinations for each predicate.

func (Proposition) BaseKey added in v0.2.0 

func (p Proposition) BaseKey() string

BaseKey returns the key without negation, useful for interference checks between positive and negative propositions.

func (Proposition) Key 

func (p Proposition) Key() string

Key returns a unique string key for map lookups. Negated propositions are prefixed with "NOT-".

func (Proposition) Negate added in v0.2.0 

func (p Proposition) Negate() Proposition

Negate returns a copy with Negated flipped.

func (Proposition) String 

func (p Proposition) String() string

String returns the human-readable representation.

type Solver 

type Solver struct {
	SolverConfig
}

Solver runs the Graphplan extend/search loop to find shortest parallel plans for STRIPS problems.

func NewSolver 

func NewSolver(
	cfg *SolverConfig,
) (*Solver, error)

NewSolver creates a solver. A nil config uses defaults.

func (*Solver) Solve 

func (s *Solver) Solve(
	prob *Problem,
) ([]PlanStep, error)

Solve finds the shortest parallel plan for the given problem. Returns ErrNoValidPlan if no plan exists, or ErrMaxLevelsExceeded if the level cap is hit.

type SolverConfig 

type SolverConfig struct {
	// MaxLevels caps graph expansion. Nil means no limit.
	MaxLevels *int `json:"max_levels,omitempty" yaml:"max_levels"`
}

SolverConfig controls solver behavior.

func (*SolverConfig) Validate 

func (c *SolverConfig) Validate() error

Validate checks that config values are semantically valid.

type Type 

type Type struct {
	Name   string
	Parent string // empty for root type "object"
}

Type represents a PDDL type in the type hierarchy.

Source Files

View all Source files

Directories

Path Synopsis
examples
rocket command
Command rocket demonstrates solving the rocket transport problem using the graphplan package.
 Command rocket demonstrates solving the rocket transport problem using the graphplan package.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.