sas-plus 0.2.0

Minimal SAS+ planning task representation, labeled transition systems and abstractions
Documentation
  • Coverage
  • 35.38%
    46 out of 130 items documented1 out of 44 items with examples
  • Size
  • Source code size: 117.9 kB This is the summed size of all the files inside the crates.io package for this release.
  • Documentation size: 1.2 MB This is the summed size of all files generated by rustdoc for all configured targets
  • Ø build duration
  • this release: 8s Average build duration of successful builds.
  • all releases: 5s Average build duration of successful builds in releases after 2024-10-23.
  • Links
  • sunsided/sas-plus
    0 0 0
  • crates.io
  • Dependencies
  • Versions
  • Owners
  • sunsided

sas-plus

SAS+ / finite-domain planning tasks for Rust, compatible with Fast Downward's translator.

What is SAS+?

SAS stands for Simplified Action Structures (Bäckström & Klein, 1991). The + is the extension by Bäckström & Nebel (1995, Complexity Results for SAS+ Planning): preconditions and goals may leave variables undefined, so they are partial states.

A SAS+ task has:

  • finite-domain state variables instead of Boolean facts, e.g. ball1 ∈ {at rooma, at roomb, carry left, carry right};
  • operators with preconditions, effects and a cost;
  • a complete initial state and a partial goal.

Because the variables capture mutual exclusion directly, many heuristics (pattern databases, merge-and-shrink, cost partitioning) are defined on SAS+ rather than on STRIPS. Fast Downward calls its version the finite-domain representation (FDR): SAS+ plus conditional effects and axioms.

What it's for

sas-plus provides building blocks for planning heuristics and search in Rust, in the spirit of crates like tower: small pieces you can reason about one at a time. It is not a planner itself, but meant for people who write or test such algorithms.

Task and LabeledTransitionSystem are plain structs with public fields: a task is its variables, operators, initial state, goal and axioms, and a transition system is a list of labeled transitions with a goal flag per state. The one abstraction on top is the Abstraction trait, which maps a concrete state to a state of a transition system; anything that implements it, a Projection or a type of your own, can stand in wherever a heuristic needs abstract goal distances. The crate has no required dependencies and is no_std; it only needs alloc.

For testing, Task::perfect_heuristic() computes the exact goal distance h* on small tasks, and random::random_task generates reproducible tasks from a seed, so a heuristic can be checked against h* over as many seeds as you care to run. On top of that, the fdr module reads Fast Downward's translator output, which brings real benchmark domains in without writing a grounder.

There is no search algorithm and no PDDL parser. To ground PDDL in Rust, see the roadmap.

Usage

Ground PDDL with Fast Downward's translator, then load the result in Rust:

use sas_plus::fdr::SasFile;

let file: SasFile = std::fs::read_to_string("output.sas")?.parse()?;
let task = file.to_task();               // Task with conditional effects and axioms
// ... search ...
print!("{}", file.format_plan(&plan));   // sas_plan format, ready for VAL

To try both steps with Docker and Task, run task ground:load. It grounds a fixture with the aibasel/downward image and loads the result with examples/load.rs. Pass DOMAIN=... PROBLEM=... to ground your own PDDL (paths inside the repository).

What's in it

  • fdr: reader and writer for output.sas (file version 3).
    • Faithful to the format: mutex groups, conditional effects, axioms, and fact names are all kept.
    • Writes back byte-for-byte what it reads.
    • Parse errors carry line numbers.
    • to_task() converts to a Task, keeping conditional effects and axioms.
    • Metric 0 means unit costs, exactly as in Fast Downward's search.
  • Task, Operator, Effect, Axiom, Fact, State, with validation, applicability and plan checking. Effects may have conditions, and derived variables are computed by layered axioms with Fast Downward's semantics.
  • LabeledTransitionSystem and the Abstraction trait, the common interface for abstraction heuristics such as projections, merge-and-shrink, and cost partitioning over them.
  • Projection: the pattern-database abstraction. Derived variables are left out of patterns, and conditional effects whose conditions lie outside the pattern may or may not fire, so projections stay admissible.
  • CausalGraph: arcs from preconditions and effect conditions to effects, between co-occurring effects, and from axiom conditions to derived variables.
  • Test oracles: Task::perfect_heuristic() (exact h*) and random::random_task.

Features

  • fdr (default): the output.sas reader and writer.
  • random (default): the random task generator.
  • serde: Serialize and Deserialize for the task model, transition systems, the causal graph and SasFile.

Use default-features = false if you only need the task model.

Fixtures

  • tests/fixtures/translated/: real Fast Downward translator output for nine problems, from the VHPOP and Potoroo corpora plus three written for this repo. It covers unit costs, action costs, conditional effects and derived predicates. Every file round-trips byte for byte, and the small tasks are checked against their known optima. The folder includes GPL-2.0 / Apache-2.0 test inputs and is excluded from the published crate.
  • tests/fixtures/: small hand-encoded files, including a minimal axiom (derived-variable) example.

Testing

  • task test: unit, fixture and property tests. tests/properties.rs checks on random tasks, with conditional effects and axioms, that projections simulate every concrete transition and never overestimate, and that perfect_heuristic satisfies the Bellman equation.
  • task fuzz: fuzzes the output.sas reader with cargo-fuzz (nightly). Accepted input must round-trip and convert to a task that validate rejects or that steps without panics.
  • task bench: criterion benchmarks for parsing, projections and the perfect heuristic on translator output.

Roadmap

  • A PDDL bridge in the pure-Rust pddl crate, behind its optional sas-plus feature, that grounds PDDL into an fdr::SasFile.