1#![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#[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 pub axiom_layer: Option<u32>,
63}
64
65impl Variable {
66 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#[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 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 pub eff: Vec<Effect>,
106 pub cost: u32,
107}
108
109#[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#[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 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 ContradictoryPrecondition {
151 op: OpId,
152 var: VarId,
153 },
154 ContradictoryGoal {
156 var: VarId,
157 },
158 DerivedVariableEffect {
160 op: OpId,
161 var: VarId,
162 },
163 AxiomHeadNotDerived {
165 axiom: usize,
166 },
167 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
204pub trait Abstraction {
208 fn lts(&self) -> &LabeledTransitionSystem;
209 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 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 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 pub fn evaluate_axioms(&self, state: &mut State) {
324 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 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 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 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 pub fn costs(&self) -> Vec<u64> {
381 self.operators.iter().map(|o| u64::from(o.cost)).collect()
382 }
383
384 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 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 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
438fn 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}