sas-plus 0.1.0

Minimal SAS+ planning task representation, labeled transition systems and abstractions
Documentation
  • Coverage
  • 26.61%
    29 out of 109 items documented1 out of 38 items with examples
  • Size
  • Source code size: 70.1 kB This is the summed size of all the files inside the crates.io package for this release.
  • Documentation size: 997.6 kB This is the summed size of all files generated by rustdoc for all configured targets
  • Ø build duration
  • this release: 2s 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 and goal, 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 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, and Task does not yet support conditional effects or axioms (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()?;              // plain SAS+ task
// ... 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 plain Task and rejects conditional effects and axioms with a typed error.
    • Metric 0 means unit costs, exactly as in Fast Downward's search.
  • Task, Operator, Fact, State, with validation, applicability and plan checking.
  • 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.
  • Test oracles: Task::perfect_heuristic() (exact h*) and random::random_task.

Fixtures

  • tests/fixtures/translated/: real Fast Downward translator output for eight problems, from the VHPOP and Potoroo corpora plus two written for this repo. It covers unit costs, action costs and conditional effects. 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 the only axiom (derived-variable) example.

Roadmap

  • A translator fixture with axioms (derived predicates).
  • Conditional effects and axioms in Task itself.
  • A bridge from a pure-Rust PDDL parser and grounder.
  • A causal graph.