1#![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#[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#[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
93pub trait Abstraction {
97 fn lts(&self) -> &LabeledTransitionSystem;
98 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 pub fn costs(&self) -> Vec<u64> {
171 self.operators.iter().map(|o| u64::from(o.cost)).collect()
172 }
173
174 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 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}