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 may also use Fast Downward's two extensions of SAS+: conditional
9//! effects and axioms (derived variables).
10//!
11//! Tasks come from Fast Downward's translator via `fdr::SasFile` (the
12//! `output.sas` format, feature `fdr`), from your own grounder, or from
13//! `random` for tests (feature `random`).
14
15#![no_std]
16
17extern crate alloc;
18
19mod causal_graph;
20#[cfg(feature = "fdr")]
21pub mod fdr;
22mod lts;
23mod projection;
24#[cfg(feature = "random")]
25pub mod random;
26mod ranking;
27
28pub use causal_graph::CausalGraph;
29pub use lts::{LabeledTransitionSystem, Transition};
30pub use projection::Projection;
31
32use alloc::string::String;
33use alloc::vec;
34use alloc::vec::Vec;
35use core::fmt;
36
37pub type VarId = usize;
38pub type Value = u32;
39pub type OpId = usize;
40
41/// A variable/value assignment `var = value`.
42#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
43#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
44pub struct Fact {
45    pub var: VarId,
46    pub value: Value,
47}
48
49impl Fact {
50    pub fn new(var: VarId, value: Value) -> Self {
51        Self { var, value }
52    }
53}
54
55#[derive(Clone, Debug, PartialEq, Eq)]
56#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
57pub struct Variable {
58    pub name: String,
59    pub domain_size: u32,
60    /// `None` for state variables, `Some(layer)` for derived variables, which
61    /// only axioms set. Axioms of lower layers are evaluated first.
62    pub axiom_layer: Option<u32>,
63}
64
65impl Variable {
66    /// A state variable (not derived).
67    pub fn new(name: impl Into<String>, domain_size: u32) -> Self {
68        Self {
69            name: name.into(),
70            domain_size,
71            axiom_layer: None,
72        }
73    }
74
75    pub fn is_derived(&self) -> bool {
76        self.axiom_layer.is_some()
77    }
78}
79
80/// An effect `fact` that fires when all `conditions` hold in the state the
81/// operator is applied in. Unconditional effects have no conditions.
82#[derive(Clone, Debug, PartialEq, Eq)]
83#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
84pub struct Effect {
85    pub conditions: Vec<Fact>,
86    pub fact: Fact,
87}
88
89impl Effect {
90    /// An unconditional effect.
91    pub fn new(fact: Fact) -> Self {
92        Self {
93            conditions: Vec::new(),
94            fact,
95        }
96    }
97}
98
99#[derive(Clone, Debug, PartialEq, Eq)]
100#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
101pub struct Operator {
102    pub name: String,
103    pub pre: Vec<Fact>,
104    /// Applied in order, so a later effect on the same variable wins.
105    pub eff: Vec<Effect>,
106    pub cost: u32,
107}
108
109/// A rule `conditions → head` that sets the derived variable `head.var`.
110#[derive(Clone, Debug, PartialEq, Eq)]
111#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
112pub struct Axiom {
113    pub conditions: Vec<Fact>,
114    pub head: Fact,
115}
116
117/// A complete assignment: `state.0[var]` is the value of `var`.
118#[derive(Clone, Debug, PartialEq, Eq, Hash)]
119#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
120pub struct State(pub Vec<Value>);
121
122#[derive(Clone, Debug, PartialEq, Eq)]
123#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
124pub struct Task {
125    pub variables: Vec<Variable>,
126    pub operators: Vec<Operator>,
127    /// As in Fast Downward, the values of derived variables here are their
128    /// defaults, which hold unless an axiom derives otherwise. Use
129    /// [`Task::initial_state`] for the state with axioms evaluated.
130    pub initial: State,
131    pub goal: Vec<Fact>,
132    pub axioms: Vec<Axiom>,
133}
134
135#[derive(Debug, Clone, PartialEq, Eq)]
136#[non_exhaustive]
137pub enum TaskError {
138    InitialStateArity,
139    ValueOutOfRange {
140        fact: Fact,
141    },
142    UnknownVariable {
143        fact: Fact,
144    },
145    DuplicateEffect {
146        op: OpId,
147        var: VarId,
148    },
149    /// An operator requires two values of one variable.
150    ContradictoryPrecondition {
151        op: OpId,
152        var: VarId,
153    },
154    /// The goal requires two values of one variable.
155    ContradictoryGoal {
156        var: VarId,
157    },
158    /// An operator sets a derived variable.
159    DerivedVariableEffect {
160        op: OpId,
161        var: VarId,
162    },
163    /// An axiom sets a state variable.
164    AxiomHeadNotDerived {
165        axiom: usize,
166    },
167    /// An axiom depends on a derived variable of a higher layer, or on one of
168    /// its own layer being at its default (negation needs a lower layer).
169    AxiomLayer {
170        axiom: usize,
171    },
172}
173
174impl fmt::Display for TaskError {
175    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
176        match self {
177            Self::InitialStateArity => write!(f, "initial state has the wrong number of variables"),
178            Self::ValueOutOfRange { fact } => write!(f, "value out of range in {fact:?}"),
179            Self::UnknownVariable { fact } => write!(f, "unknown variable in {fact:?}"),
180            Self::DuplicateEffect { op, var } => {
181                write!(f, "operator {op} has two effects on variable {var}")
182            }
183            Self::ContradictoryPrecondition { op, var } => {
184                write!(f, "operator {op} requires two values of variable {var}")
185            }
186            Self::ContradictoryGoal { var } => {
187                write!(f, "the goal requires two values of variable {var}")
188            }
189            Self::DerivedVariableEffect { op, var } => {
190                write!(f, "operator {op} sets derived variable {var}")
191            }
192            Self::AxiomHeadNotDerived { axiom } => {
193                write!(f, "axiom {axiom} sets a state variable")
194            }
195            Self::AxiomLayer { axiom } => {
196                write!(f, "axiom {axiom} depends on a higher axiom layer")
197            }
198        }
199    }
200}
201
202impl core::error::Error for TaskError {}
203
204/// Something that maps concrete states onto an abstract transition system
205/// whose labels are operator ids. Goal distances in the abstract system are
206/// admissible estimates for the concrete task.
207pub trait Abstraction {
208    fn lts(&self) -> &LabeledTransitionSystem;
209    /// `None` means the state was pruned (provably a dead end or unreachable).
210    fn abstract_state(&self, state: &State) -> Option<usize>;
211}
212
213impl<A: Abstraction + ?Sized> Abstraction for &A {
214    fn lts(&self) -> &LabeledTransitionSystem {
215        (**self).lts()
216    }
217    fn abstract_state(&self, state: &State) -> Option<usize> {
218        (**self).abstract_state(state)
219    }
220}
221
222impl Task {
223    pub fn validate(&self) -> Result<(), TaskError> {
224        if self.initial.0.len() != self.variables.len() {
225            return Err(TaskError::InitialStateArity);
226        }
227        let check = |fact: &Fact| -> Result<(), TaskError> {
228            let var = self
229                .variables
230                .get(fact.var)
231                .ok_or(TaskError::UnknownVariable { fact: *fact })?;
232            if fact.value >= var.domain_size {
233                return Err(TaskError::ValueOutOfRange { fact: *fact });
234            }
235            Ok(())
236        };
237        for (var, &value) in self.initial.0.iter().enumerate() {
238            check(&Fact::new(var, value))?;
239        }
240        self.goal.iter().try_for_each(check)?;
241        if let Some(var) = contradiction(&self.goal) {
242            return Err(TaskError::ContradictoryGoal { var });
243        }
244        for (id, op) in self.operators.iter().enumerate() {
245            op.pre.iter().try_for_each(check)?;
246            if let Some(var) = contradiction(&op.pre) {
247                return Err(TaskError::ContradictoryPrecondition { op: id, var });
248            }
249            for e in &op.eff {
250                e.conditions.iter().try_for_each(check)?;
251                check(&e.fact)?;
252                if self.variables[e.fact.var].is_derived() {
253                    return Err(TaskError::DerivedVariableEffect {
254                        op: id,
255                        var: e.fact.var,
256                    });
257                }
258            }
259            // Conditional effects on one variable may coexist; the last firing one wins.
260            let mut vars: Vec<_> = op
261                .eff
262                .iter()
263                .filter(|e| e.conditions.is_empty())
264                .map(|e| e.fact.var)
265                .collect();
266            vars.sort_unstable();
267            if let Some(w) = vars.windows(2).find(|w| w[0] == w[1]) {
268                return Err(TaskError::DuplicateEffect { op: id, var: w[0] });
269            }
270        }
271        for (id, axiom) in self.axioms.iter().enumerate() {
272            axiom.conditions.iter().try_for_each(check)?;
273            check(&axiom.head)?;
274            let Some(layer) = self.variables[axiom.head.var].axiom_layer else {
275                return Err(TaskError::AxiomHeadNotDerived { axiom: id });
276            };
277            if axiom.conditions.iter().any(|c| {
278                self.variables[c.var]
279                    .axiom_layer
280                    .is_some_and(|l| l > layer || (l == layer && c.value == self.initial.0[c.var]))
281            }) {
282                return Err(TaskError::AxiomLayer { axiom: id });
283            }
284        }
285        Ok(())
286    }
287
288    pub fn num_variables(&self) -> usize {
289        self.variables.len()
290    }
291
292    pub fn is_applicable(&self, op: OpId, state: &State) -> bool {
293        holds(&self.operators[op].pre, state)
294    }
295
296    /// The successor state. Effect conditions are evaluated in `state`;
297    /// derived variables are then re-evaluated.
298    ///
299    /// Like [`Task::is_applicable`] and [`Task::is_goal`], this reads derived
300    /// variables from `state` as given, so `state` must have them evaluated:
301    /// start from [`Task::initial_state`] (not [`Task::initial`]) or call
302    /// [`Task::evaluate_axioms`] first. States returned by `apply` are.
303    pub fn apply(&self, op: OpId, state: &State) -> State {
304        let mut next = state.clone();
305        for e in &self.operators[op].eff {
306            if holds(&e.conditions, state) {
307                next.0[e.fact.var] = e.fact.value;
308            }
309        }
310        self.evaluate_axioms(&mut next);
311        next
312    }
313
314    /// Recomputes all derived variables of `state` from its state variables:
315    /// each derived variable is reset to its default (its value in
316    /// [`Task::initial`]), then the axioms fire layer by layer until nothing
317    /// changes, as in Fast Downward. A variable keeps the first non-default
318    /// value derived for it.
319    ///
320    /// This allocates nothing but rescans the rules of a layer until none
321    /// fires; search code that needs speed on axiom-heavy tasks should index
322    /// the rules itself.
323    pub fn evaluate_axioms(&self, state: &mut State) {
324        // Reset first: a derived variable without rules still holds its default.
325        for (var, v) in self.variables.iter().enumerate() {
326            if v.is_derived() {
327                state.0[var] = self.initial.0[var];
328            }
329        }
330        if self.axioms.is_empty() {
331            return;
332        }
333        let mut done: Option<u32> = None;
334        // Layers in ascending order, without collecting them.
335        while let Some(layer) = self
336            .variables
337            .iter()
338            .filter_map(|v| v.axiom_layer)
339            .filter(|&l| done.is_none_or(|d| l > d))
340            .min()
341        {
342            done = Some(layer);
343            let mut changed = true;
344            while changed {
345                changed = false;
346                for a in &self.axioms {
347                    if self.variables[a.head.var].axiom_layer != Some(layer) {
348                        continue;
349                    }
350                    // Only a variable still at its default is derived, so the fixpoint is reached.
351                    let default = self.initial.0[a.head.var];
352                    if state.0[a.head.var] == default
353                        && a.head.value != default
354                        && holds(&a.conditions, state)
355                    {
356                        state.0[a.head.var] = a.head.value;
357                        changed = true;
358                    }
359                }
360            }
361        }
362    }
363
364    /// The initial state with derived variables evaluated.
365    pub fn initial_state(&self) -> State {
366        let mut state = self.initial.clone();
367        self.evaluate_axioms(&mut state);
368        state
369    }
370
371    pub fn applicable_operators<'a>(&'a self, state: &'a State) -> impl Iterator<Item = OpId> + 'a {
372        (0..self.operators.len()).filter(move |&op| self.is_applicable(op, state))
373    }
374
375    pub fn is_goal(&self, state: &State) -> bool {
376        holds(&self.goal, state)
377    }
378
379    /// Operator costs indexed by operator id (the label cost function).
380    pub fn costs(&self) -> Vec<u64> {
381        self.operators.iter().map(|o| u64::from(o.cost)).collect()
382    }
383
384    /// Checks that `plan` is applicable from the initial state and reaches the goal.
385    /// Returns the plan cost.
386    pub fn validate_plan(&self, plan: &[OpId]) -> Option<u64> {
387        let mut state = self.initial_state();
388        let mut cost = 0;
389        for &op in plan {
390            if !self.is_applicable(op, &state) {
391                return None;
392            }
393            state = self.apply(op, &state);
394            cost += u64::from(self.operators[op].cost);
395        }
396        self.is_goal(&state).then_some(cost)
397    }
398
399    /// Optimal plan cost from `state` (with derived variables evaluated),
400    /// by building the full state space over all state variables.
401    /// Exponential; intended for tests on tiny tasks.
402    pub fn perfect_heuristic(&self) -> impl Fn(&State) -> Option<u64> + '_ {
403        let vars = (0..self.num_variables())
404            .filter(|&v| !self.variables[v].is_derived())
405            .collect();
406        let ranking = ranking::Ranking::new(self, vars);
407        let mut state = self.initial.clone();
408        let mut transitions = Vec::new();
409        for (label, op) in self.operators.iter().enumerate() {
410            // Preconditions on state variables pick the candidates; derived ones are checked after.
411            for src in ranking.matching(&op.pre) {
412                ranking.unrank(src, &mut state);
413                self.evaluate_axioms(&mut state);
414                if self.is_applicable(label, &state) {
415                    let dst = ranking.rank(&self.apply(label, &state));
416                    transitions.push(Transition { src, label, dst });
417                }
418            }
419        }
420        let mut goal = vec![false; ranking.num_states];
421        for index in ranking.matching(&self.goal) {
422            ranking.unrank(index, &mut state);
423            self.evaluate_axioms(&mut state);
424            goal[index] = self.is_goal(&state);
425        }
426        let lts = LabeledTransitionSystem {
427            num_states: ranking.num_states,
428            num_labels: self.operators.len(),
429            transitions,
430            goal,
431            initial: Some(ranking.rank(&self.initial)),
432        };
433        let h = lts.goal_distances(&self.costs());
434        move |s| h[ranking.rank(s)]
435    }
436}
437
438/// A variable that `facts` assign two different values, if any.
439fn contradiction(facts: &[Fact]) -> Option<VarId> {
440    let mut sorted = facts.to_vec();
441    sorted.sort_unstable();
442    sorted.dedup();
443    sorted
444        .windows(2)
445        .find(|w| w[0].var == w[1].var)
446        .map(|w| w[0].var)
447}
448
449fn holds(facts: &[Fact], state: &State) -> bool {
450    facts.iter().all(|f| state.0[f.var] == f.value)
451}