#![no_std]
extern crate alloc;
pub mod fdr;
mod lts;
mod projection;
pub mod random;
pub use lts::{LabeledTransitionSystem, Transition};
pub use projection::Projection;
use alloc::string::String;
use alloc::vec::Vec;
use core::fmt;
pub type VarId = usize;
pub type Value = u32;
pub type OpId = usize;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Fact {
pub var: VarId,
pub value: Value,
}
impl Fact {
pub fn new(var: VarId, value: Value) -> Self {
Self { var, value }
}
}
#[derive(Clone, Debug)]
pub struct Variable {
pub name: String,
pub domain_size: u32,
}
#[derive(Clone, Debug)]
pub struct Operator {
pub name: String,
pub pre: Vec<Fact>,
pub eff: Vec<Fact>,
pub cost: u32,
}
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct State(pub Vec<Value>);
#[derive(Clone, Debug)]
pub struct Task {
pub variables: Vec<Variable>,
pub operators: Vec<Operator>,
pub initial: State,
pub goal: Vec<Fact>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum TaskError {
InitialStateArity,
ValueOutOfRange { fact: Fact },
UnknownVariable { fact: Fact },
DuplicateEffect { op: OpId, var: VarId },
}
impl fmt::Display for TaskError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::InitialStateArity => write!(f, "initial state has the wrong number of variables"),
Self::ValueOutOfRange { fact } => write!(f, "value out of range in {fact:?}"),
Self::UnknownVariable { fact } => write!(f, "unknown variable in {fact:?}"),
Self::DuplicateEffect { op, var } => {
write!(f, "operator {op} has two effects on variable {var}")
}
}
}
}
impl core::error::Error for TaskError {}
pub trait Abstraction {
fn lts(&self) -> &LabeledTransitionSystem;
fn abstract_state(&self, state: &State) -> Option<usize>;
}
impl<A: Abstraction + ?Sized> Abstraction for &A {
fn lts(&self) -> &LabeledTransitionSystem {
(**self).lts()
}
fn abstract_state(&self, state: &State) -> Option<usize> {
(**self).abstract_state(state)
}
}
impl Task {
pub fn validate(&self) -> Result<(), TaskError> {
if self.initial.0.len() != self.variables.len() {
return Err(TaskError::InitialStateArity);
}
let check = |fact: &Fact| -> Result<(), TaskError> {
let var = self
.variables
.get(fact.var)
.ok_or(TaskError::UnknownVariable { fact: *fact })?;
if fact.value >= var.domain_size {
return Err(TaskError::ValueOutOfRange { fact: *fact });
}
Ok(())
};
for (var, &value) in self.initial.0.iter().enumerate() {
check(&Fact::new(var, value))?;
}
self.goal.iter().try_for_each(check)?;
for (id, op) in self.operators.iter().enumerate() {
op.pre.iter().try_for_each(check)?;
op.eff.iter().try_for_each(check)?;
let mut vars: Vec<_> = op.eff.iter().map(|f| f.var).collect();
vars.sort_unstable();
if let Some(w) = vars.windows(2).find(|w| w[0] == w[1]) {
return Err(TaskError::DuplicateEffect { op: id, var: w[0] });
}
}
Ok(())
}
pub fn num_variables(&self) -> usize {
self.variables.len()
}
pub fn is_applicable(&self, op: OpId, state: &State) -> bool {
self.operators[op]
.pre
.iter()
.all(|f| state.0[f.var] == f.value)
}
pub fn apply(&self, op: OpId, state: &State) -> State {
let mut next = state.clone();
for f in &self.operators[op].eff {
next.0[f.var] = f.value;
}
next
}
pub fn applicable_operators<'a>(&'a self, state: &'a State) -> impl Iterator<Item = OpId> + 'a {
(0..self.operators.len()).filter(move |&op| self.is_applicable(op, state))
}
pub fn is_goal(&self, state: &State) -> bool {
self.goal.iter().all(|f| state.0[f.var] == f.value)
}
pub fn costs(&self) -> Vec<u64> {
self.operators.iter().map(|o| u64::from(o.cost)).collect()
}
pub fn validate_plan(&self, plan: &[OpId]) -> Option<u64> {
let mut state = self.initial.clone();
let mut cost = 0;
for &op in plan {
if !self.is_applicable(op, &state) {
return None;
}
state = self.apply(op, &state);
cost += u64::from(self.operators[op].cost);
}
self.is_goal(&state).then_some(cost)
}
pub fn perfect_heuristic(&self) -> impl Fn(&State) -> Option<u64> + '_ {
let full = Projection::new(self, (0..self.num_variables()).collect());
let h = full.lts().goal_distances(&self.costs());
move |s| h[full.rank(s)]
}
}