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 SasFile;
let file: SasFile = read_to_string?.parse?;
let task = file.to_task; // Task with conditional effects and axioms
// ... search ...
print!; // 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 foroutput.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 aTask, keeping conditional effects and axioms.- Metric
0means 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.LabeledTransitionSystemand theAbstractiontrait, 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*) andrandom::random_task.
Features
fdr(default): theoutput.sasreader and writer.random(default): the random task generator.serde:SerializeandDeserializefor the task model, transition systems, the causal graph andSasFile.
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.rschecks on random tasks, with conditional effects and axioms, that projections simulate every concrete transition and never overestimate, and thatperfect_heuristicsatisfies the Bellman equation.task fuzz: fuzzes theoutput.sasreader with cargo-fuzz (nightly). Accepted input must round-trip and convert to a task thatvalidaterejects 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
pddlcrate, behind its optionalsas-plusfeature, that grounds PDDL into anfdr::SasFile.