Skip to main content

sas_plus/
projection.rs

1use alloc::vec;
2use alloc::vec::Vec;
3
4use crate::{Abstraction, LabeledTransitionSystem, State, Task, Transition, VarId};
5
6/// Projection of a task onto a subset of variables (a "pattern"); the
7/// abstraction underlying pattern databases.
8#[derive(Clone, Debug)]
9pub struct Projection {
10    pattern: Vec<VarId>,
11    multipliers: Vec<usize>,
12    lts: LabeledTransitionSystem,
13}
14
15impl Projection {
16    pub fn new(task: &Task, mut pattern: Vec<VarId>) -> Self {
17        pattern.sort_unstable();
18        pattern.dedup();
19        let domains: Vec<usize> = pattern
20            .iter()
21            .map(|&v| task.variables[v].domain_size as usize)
22            .collect();
23        let mut multipliers = Vec::with_capacity(pattern.len());
24        let mut num_states = 1usize;
25        for &d in &domains {
26            multipliers.push(num_states);
27            num_states = num_states
28                .checked_mul(d)
29                .expect("projection too large to enumerate");
30        }
31        let mut position = vec![None; task.num_variables()];
32        for (i, &v) in pattern.iter().enumerate() {
33            position[v] = Some(i);
34        }
35        let value = |s: usize, i: usize| (s / multipliers[i]) % domains[i];
36
37        let mut transitions = Vec::new();
38        for (label, op) in task.operators.iter().enumerate() {
39            for src in 0..num_states {
40                let consistent = op.pre.iter().all(|f| match position[f.var] {
41                    Some(i) => value(src, i) == f.value as usize,
42                    None => true,
43                });
44                if !consistent {
45                    continue;
46                }
47                let mut dst = src;
48                for f in &op.eff {
49                    if let Some(i) = position[f.var] {
50                        dst = dst - value(dst, i) * multipliers[i]
51                            + f.value as usize * multipliers[i];
52                    }
53                }
54                transitions.push(Transition { src, label, dst });
55            }
56        }
57        let goal = (0..num_states)
58            .map(|s| {
59                task.goal.iter().all(|f| match position[f.var] {
60                    Some(i) => value(s, i) == f.value as usize,
61                    None => true,
62                })
63            })
64            .collect();
65        let mut this = Self {
66            pattern,
67            multipliers,
68            lts: LabeledTransitionSystem {
69                num_states,
70                num_labels: task.operators.len(),
71                transitions,
72                goal,
73                initial: None,
74            },
75        };
76        this.lts.initial = Some(this.rank(&task.initial));
77        this
78    }
79
80    pub fn pattern(&self) -> &[VarId] {
81        &self.pattern
82    }
83
84    /// Index of the abstract state that `state` projects to.
85    pub fn rank(&self, state: &State) -> usize {
86        self.pattern
87            .iter()
88            .zip(&self.multipliers)
89            .map(|(&v, &m)| state.0[v] as usize * m)
90            .sum()
91    }
92}
93
94impl Abstraction for Projection {
95    fn lts(&self) -> &LabeledTransitionSystem {
96        &self.lts
97    }
98    fn abstract_state(&self, state: &State) -> Option<usize> {
99        Some(self.rank(state))
100    }
101}