Skip to main content

sas_plus/
lib.rs

1//! Minimal SAS+ planning tasks, labeled transition systems, and the
2//! [`Abstraction`] trait for abstraction heuristics.
3//!
4//! SAS+ (*Simplified Action Structures*, extended; Bäckström & Nebel 1995)
5//! describes planning tasks with finite-domain state variables, operators
6//! with preconditions and effects, and partial goals.
7//!
8//! Tasks come from Fast Downward's translator via [`fdr::SasFile`] (the
9//! `output.sas` format), from your own grounder, or from [`random`] for tests.
10
11#![no_std]
12
13extern crate alloc;
14
15pub mod fdr;
16mod lts;
17mod projection;
18pub mod random;
19
20pub use lts::{LabeledTransitionSystem, Transition};
21pub use projection::Projection;
22
23use alloc::string::String;
24use alloc::vec::Vec;
25use core::fmt;
26
27pub type VarId = usize;
28pub type Value = u32;
29pub type OpId = usize;
30
31/// A variable/value assignment `var = value`.
32#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
33pub struct Fact {
34    pub var: VarId,
35    pub value: Value,
36}
37
38impl Fact {
39    pub fn new(var: VarId, value: Value) -> Self {
40        Self { var, value }
41    }
42}
43
44#[derive(Clone, Debug)]
45pub struct Variable {
46    pub name: String,
47    pub domain_size: u32,
48}
49
50#[derive(Clone, Debug)]
51pub struct Operator {
52    pub name: String,
53    pub pre: Vec<Fact>,
54    pub eff: Vec<Fact>,
55    pub cost: u32,
56}
57
58/// A complete assignment: `state.0[var]` is the value of `var`.
59#[derive(Clone, Debug, PartialEq, Eq, Hash)]
60pub struct State(pub Vec<Value>);
61
62#[derive(Clone, Debug)]
63pub struct Task {
64    pub variables: Vec<Variable>,
65    pub operators: Vec<Operator>,
66    pub initial: State,
67    pub goal: Vec<Fact>,
68}
69
70#[derive(Debug, Clone, PartialEq, Eq)]
71pub enum TaskError {
72    InitialStateArity,
73    ValueOutOfRange { fact: Fact },
74    UnknownVariable { fact: Fact },
75    DuplicateEffect { op: OpId, var: VarId },
76}
77
78impl fmt::Display for TaskError {
79    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
80        match self {
81            Self::InitialStateArity => write!(f, "initial state has the wrong number of variables"),
82            Self::ValueOutOfRange { fact } => write!(f, "value out of range in {fact:?}"),
83            Self::UnknownVariable { fact } => write!(f, "unknown variable in {fact:?}"),
84            Self::DuplicateEffect { op, var } => {
85                write!(f, "operator {op} has two effects on variable {var}")
86            }
87        }
88    }
89}
90
91impl core::error::Error for TaskError {}
92
93/// Something that maps concrete states onto an abstract transition system
94/// whose labels are operator ids. Goal distances in the abstract system are
95/// admissible estimates for the concrete task.
96pub trait Abstraction {
97    fn lts(&self) -> &LabeledTransitionSystem;
98    /// `None` means the state was pruned (provably a dead end or unreachable).
99    fn abstract_state(&self, state: &State) -> Option<usize>;
100}
101
102impl<A: Abstraction + ?Sized> Abstraction for &A {
103    fn lts(&self) -> &LabeledTransitionSystem {
104        (**self).lts()
105    }
106    fn abstract_state(&self, state: &State) -> Option<usize> {
107        (**self).abstract_state(state)
108    }
109}
110
111impl Task {
112    pub fn validate(&self) -> Result<(), TaskError> {
113        if self.initial.0.len() != self.variables.len() {
114            return Err(TaskError::InitialStateArity);
115        }
116        let check = |fact: &Fact| -> Result<(), TaskError> {
117            let var = self
118                .variables
119                .get(fact.var)
120                .ok_or(TaskError::UnknownVariable { fact: *fact })?;
121            if fact.value >= var.domain_size {
122                return Err(TaskError::ValueOutOfRange { fact: *fact });
123            }
124            Ok(())
125        };
126        for (var, &value) in self.initial.0.iter().enumerate() {
127            check(&Fact::new(var, value))?;
128        }
129        self.goal.iter().try_for_each(check)?;
130        for (id, op) in self.operators.iter().enumerate() {
131            op.pre.iter().try_for_each(check)?;
132            op.eff.iter().try_for_each(check)?;
133            let mut vars: Vec<_> = op.eff.iter().map(|f| f.var).collect();
134            vars.sort_unstable();
135            if let Some(w) = vars.windows(2).find(|w| w[0] == w[1]) {
136                return Err(TaskError::DuplicateEffect { op: id, var: w[0] });
137            }
138        }
139        Ok(())
140    }
141
142    pub fn num_variables(&self) -> usize {
143        self.variables.len()
144    }
145
146    pub fn is_applicable(&self, op: OpId, state: &State) -> bool {
147        self.operators[op]
148            .pre
149            .iter()
150            .all(|f| state.0[f.var] == f.value)
151    }
152
153    pub fn apply(&self, op: OpId, state: &State) -> State {
154        let mut next = state.clone();
155        for f in &self.operators[op].eff {
156            next.0[f.var] = f.value;
157        }
158        next
159    }
160
161    pub fn applicable_operators<'a>(&'a self, state: &'a State) -> impl Iterator<Item = OpId> + 'a {
162        (0..self.operators.len()).filter(move |&op| self.is_applicable(op, state))
163    }
164
165    pub fn is_goal(&self, state: &State) -> bool {
166        self.goal.iter().all(|f| state.0[f.var] == f.value)
167    }
168
169    /// Operator costs indexed by operator id (the label cost function).
170    pub fn costs(&self) -> Vec<u64> {
171        self.operators.iter().map(|o| u64::from(o.cost)).collect()
172    }
173
174    /// Checks that `plan` is applicable from the initial state and reaches the goal.
175    /// Returns the plan cost.
176    pub fn validate_plan(&self, plan: &[OpId]) -> Option<u64> {
177        let mut state = self.initial.clone();
178        let mut cost = 0;
179        for &op in plan {
180            if !self.is_applicable(op, &state) {
181                return None;
182            }
183            state = self.apply(op, &state);
184            cost += u64::from(self.operators[op].cost);
185        }
186        self.is_goal(&state).then_some(cost)
187    }
188
189    /// Optimal plan cost from `state`, by exhaustive projection onto all
190    /// variables. Exponential; intended for tests on tiny tasks.
191    pub fn perfect_heuristic(&self) -> impl Fn(&State) -> Option<u64> + '_ {
192        let full = Projection::new(self, (0..self.num_variables()).collect());
193        let h = full.lts().goal_distances(&self.costs());
194        move |s| h[full.rank(s)]
195    }
196}