use std::fmt::{Debug, Display};
use std::hash::Hash;
use std::iter::FromIterator;
use std::collections::{HashMap, HashSet, BTreeSet, VecDeque};
use log::{debug};
use crate::proposition::Proposition;
use crate::action::{Action, ActionType};
use crate::pairset::{pairs_from_sets};
use crate::layer::{MutexPairs, Layer};
use crate::plangraph::{PlanGraph, Solution};
pub trait GraphPlanSolver<'a,
ActionId: Hash + Ord + Clone + Debug,
PropositionId: Hash + Ord + Clone + Debug + Display> {
fn search<'b>(plangraph: &'b PlanGraph<'a, ActionId, PropositionId>) -> Option<Solution<'a, ActionId, PropositionId>>;
}
#[derive(Default)]
pub struct SimpleSolver;
type GoalIndex = usize;
type Attempts<'a, ActionId, PropositionId> = HashMap<usize, BTreeSet<&'a Action<'a, ActionId, PropositionId>>>;
#[derive(Clone, Debug, PartialEq)]
struct ActionCombination<'a,
ActionId: Hash + PartialEq + Clone + Debug ,
PropositionId: Hash + Eq + PartialEq + Clone + Debug + Display>(
HashMap<GoalIndex, &'a Action<'a, ActionId, PropositionId>>
);
#[derive(Clone, Debug)]
struct GoalSetActionGenerator<'a,
ActionId: Debug + Hash + Clone + Eq + Ord,
PropositionId: Debug + Display + Hash + Clone + Eq + Ord> {
goals: BTreeSet<&'a Proposition<PropositionId>>,
actions: BTreeSet<&'a Action<'a, ActionId, PropositionId>>,
mutexes: Option<MutexPairs<&'a Action<'a, ActionId, PropositionId>>>,
}
impl<'a,
ActionId: Ord + Clone + Hash + Debug,
PropositionId: Ord + Clone + Hash + Debug + Display>
GoalSetActionGenerator<'a, ActionId, PropositionId> {
pub fn new(goals: BTreeSet<&'a Proposition<PropositionId>>,
actions: BTreeSet<&'a Action<'a, ActionId, PropositionId>>,
mutexes: Option<MutexPairs<&'a Action<'a, ActionId, PropositionId>>>,)
-> GoalSetActionGenerator<'a, ActionId, PropositionId> {
GoalSetActionGenerator {goals, actions, mutexes}
}
}
impl<'a,
ActionId: Ord + Clone + Hash + Debug,
PropositionId: Ord + Clone + Hash + Debug + Display>
IntoIterator for GoalSetActionGenerator<'a, ActionId, PropositionId> {
type Item = ActionCombination<'a, ActionId, PropositionId>;
type IntoIter = ActionCombinationIterator<'a, ActionId, PropositionId>;
fn into_iter(self) -> Self::IntoIter {
ActionCombinationIterator::new(self)
}
}
#[derive(Clone, Debug)]
struct ActionCombinationIterator<'a,
ActionId: Ord + Clone + Hash + Debug,
PropositionId: Ord + Clone + Hash + Debug + Display> {
meta: GoalSetActionGenerator<'a, ActionId, PropositionId>,
attempts: Attempts<'a, ActionId, PropositionId>,
goals_met: bool,
accum: HashMap<GoalIndex, &'a Action<'a, ActionId, PropositionId>>
}
impl<'a,
ActionId: Ord + Debug + Hash + Clone,
PropositionId: Ord + Debug + Display + Hash + Clone>
ActionCombinationIterator<'a, ActionId, PropositionId> {
pub fn new(action_combinations: GoalSetActionGenerator<ActionId, PropositionId>) -> ActionCombinationIterator<ActionId, PropositionId> {
ActionCombinationIterator {
meta: action_combinations,
attempts: Attempts::new(),
goals_met: false,
accum: HashMap::new(),
}
}
}
impl<'a,
ActionId: Ord + Clone + Hash + Debug + PartialEq,
PropositionId: Ord + Clone + Hash + Debug + Display + PartialEq>
Iterator for ActionCombinationIterator<'a, ActionId, PropositionId> {
type Item = ActionCombination<'a, ActionId, PropositionId>;
fn next(&mut self) -> Option<Self::Item> {
let goals = Vec::from_iter(&self.meta.goals);
let actions = &self.meta.actions;
let goal_len = goals.len();
let mut stack = VecDeque::new();
if self.goals_met {
self.goals_met = false;
let goal_idx = goal_len - 1;
self.accum.remove(&goal_idx);
stack.push_front(goal_idx);
} else {
stack.push_front(0);
}
while let Some(goal_idx) = stack.pop_front() {
let available_actions = if let Some(acts) = self.attempts.get(&goal_idx) {
acts.to_owned()
} else {
let goal = &goals[goal_idx];
debug!("Working on goal {:?}", goal);
let mut available = BTreeSet::new();
let accum = &self.accum;
for a in actions {
if !a.effects.contains(*goal) {
continue
};
if accum.get(&goal_idx).map(|i| i == a).unwrap_or(false) {
available.insert(a.clone());
break
};
let acts = accum.values().into_iter().map(|i| *i).collect();
let pairs = pairs_from_sets(hashset!{*a}, acts);
debug!("Checking pairs: {:?} against mutexes: {:?}", &pairs, &self.meta.mutexes);
if let Some(muxes) = &self.meta.mutexes {
if muxes.intersection(&pairs).next().is_none() {
available.insert(a.clone());
}
};
};
available
};
if available_actions.is_empty() {
if goal_idx == 0 {
break;
}
debug!("Unable to find actions for goal {:?}. Going back to previous goal...", goal_idx);
self.attempts.remove(&goal_idx);
stack.push_front(goal_idx - 1);
} else {
let next_action = available_actions.iter().next().unwrap();
self.accum.insert(goal_idx, next_action.clone());
let mut remaining_actions = available_actions.clone();
remaining_actions.remove(next_action);
self.attempts.insert(goal_idx, remaining_actions);
if goal_idx < goal_len - 1 {
stack.push_front(goal_idx + 1);
} else {
self.goals_met = true;
}
};
};
if self.goals_met {
Some(ActionCombination(self.accum.clone()))
} else {
None
}
}
}
#[cfg(test)]
mod goal_set_action_generator_test {
use super::*;
#[test]
fn single_goal() {
let p1 = Proposition::from("coffee");
let p2 = Proposition::from("caffeinated");
let goals = btreeset!{&p2};
let mut actions = BTreeSet::new();
let a1 = Action::new(
String::from("drink coffee"),
hashset!{&p1},
hashset!{&p2}
);
actions.insert(&a1);
let mutexes = Some(MutexPairs::new());
let expected = ActionCombination(hashmap!{0usize => &a1});
let actual = GoalSetActionGenerator::new(goals, actions, mutexes)
.into_iter()
.next()
.unwrap();
assert_eq!(expected, actual);
}
#[test]
fn multiple_goals() {
let p1 = Proposition::from("coffee");
let p2 = Proposition::from("caffeinated");
let p3 = Proposition::from("breakfast");
let p4 = Proposition::from("full");
let a1 = Action::new(
String::from("drink coffee"),
hashset!{&p1},
hashset!{&p2}
);
let a2 = Action::new(
String::from("eat breakfast"),
hashset!{&p3},
hashset!{&p4}
);
let actions = btreeset!{&a1, &a2};
let goals = btreeset!{&p2, &p4};
let mutexes = Some(MutexPairs::new());
let expected = ActionCombination(hashmap!{0usize => &a1, 1usize => &a2});
let actual = GoalSetActionGenerator::new(goals, actions, mutexes)
.into_iter()
.next()
.unwrap();
assert_eq!(expected, actual);
}
#[test]
fn yields_all() {
let p1 = Proposition::from("tea");
let p2 = Proposition::from("coffee");
let p3 = Proposition::from("caffeinated");
let p4 = Proposition::from("scone");
let p5 = Proposition::from("muffin");
let p6 = Proposition::from("full");
let a1 = Action::new("drink coffee", hashset!{&p2}, hashset!{&p3});
let a2 = Action::new("drink tea", hashset!{&p1}, hashset!{&p3});
let a3 = Action::new("eat scone", hashset!{&p4}, hashset!{&p6});
let a4 = Action::new("eat muffin", hashset!{&p5}, hashset!{&p6});
let actions = btreeset!{&a1, &a2, &a3, &a4};
let goals = btreeset!{&p3, &p6};
let mutexes = Some(MutexPairs::new());
let expected = vec![
vec![&a1, &a4],
vec![&a1, &a3],
vec![&a2, &a4],
vec![&a2, &a3],
];
let generator = GoalSetActionGenerator::new(goals, actions, mutexes);
let actual: Vec<Vec<&Action<_, _>>> = generator.into_iter()
.map(|combo| {
let mut out = combo.0.values()
.into_iter()
.map(|i| *i)
.collect::<Vec<&Action<&str, &str>>>();
out.sort();
out
})
.collect();
assert_eq!(expected, actual);
}
}
type SearchStack<'a, ActionId, PropositionId> = VecDeque<(usize, BTreeSet<&'a Proposition<PropositionId>>, Option<ActionCombinationIterator<'a, ActionId, PropositionId>>)>;
impl<'a,
ActionId: Ord + Clone + Hash + Debug,
PropositionId: Ord + Clone + Hash + Debug + Display>
GraphPlanSolver<'a, ActionId, PropositionId> for SimpleSolver {
fn search<'b>(plangraph: &'b PlanGraph<'a, ActionId, PropositionId>) -> Option<Solution<'a, ActionId, PropositionId>> {
let mut success = false;
let mut plan = Vec::new();
let mut failed_goals_memo: HashSet<(usize, BTreeSet<&Proposition<PropositionId>>)> = HashSet::new();
let mut stack: SearchStack<ActionId, PropositionId> = VecDeque::new();
let init_goals = BTreeSet::from_iter(plangraph.goals.clone());
let init_layer_idx = plangraph.layers.len() - 1;
let init_action_gen = None;
stack.push_front((init_layer_idx, init_goals, init_action_gen));
while let Some((idx, goals, action_gen)) = stack.pop_front() {
debug!("Working on layer {:?} with goals {:?}", idx, goals);
let goals_as_btree = BTreeSet::from_iter(goals.clone());
if failed_goals_memo.contains(&(idx, goals_as_btree.clone())) {
continue;
}
let actions = plangraph.layers.get(idx - 1).map_or(
Err(format!("Layer {} does not exist", idx - 1)),
|layer| {
match layer {
Layer::ActionLayer(actions) => {
let acts = actions
.iter()
.cloned()
.collect::<BTreeSet<_>>();
Ok(acts)
},
Layer::PropositionLayer(_) => {
Err(format!("Tried to get actions from proposition layer {}",
idx - 1))
}
}
}
).expect("Failed to get actions");
let mutexes = plangraph.mutex_actions.get(&(idx - 1)).cloned();
let mut gen = action_gen
.or_else(|| Some(GoalSetActionGenerator::new(goals.clone(),
actions.clone(),
mutexes).into_iter()))
.unwrap();
if let Some(goal_actions) = gen.next() {
debug!("Actions: {:?} for goals: {:?}", goal_actions, goals);
let goal_action_set = goal_actions.0.values()
.into_iter()
.filter(|a| match a.id {
ActionType::Action(_) => true,
ActionType::Maintenance(_) => false
})
.map(|i| *i)
.collect::<HashSet<&'a Action<ActionId, PropositionId>>>();
if (idx - 2) == 0 {
plan.push(goal_action_set);
debug!("Found plan! {:?}", plan);
success = true;
break;
} else {
let next_goals = goal_action_set.iter()
.flat_map(|action| action.reqs.clone())
.collect();
plan.push(goal_action_set);
stack.push_front((idx, goals, Some(gen)));
stack.push_front((idx - 2, next_goals, None));
};
} else {
debug!("Unable to find actions for goals {:?} from actions {:?}",
goals, actions);
failed_goals_memo.insert((idx, goals_as_btree));
plan.pop();
}
};
if success {
plan.reverse();
Some(plan)
} else {
None
}
}
}
#[cfg(test)]
mod simple_solver_test {
use super::*;
#[test]
fn solver_works() {
let p1 = Proposition::from("tired");
let not_p1 = p1.negate();
let p2 = Proposition::from("dog needs to pee");
let not_p2 = p2.negate();
let a1 = Action::new(
String::from("coffee"),
hashset!{&p1},
hashset!{¬_p1}
);
let a2 = Action::new(
String::from("walk dog"),
hashset!{&p2, ¬_p1},
hashset!{¬_p2},
);
let a3 = Action::new_maintenance(&p1);
let a4 = Action::new_maintenance(¬_p1);
let a5 = Action::new_maintenance(&p2);
let a6 = Action::new_maintenance(¬_p2);
let initial_props = hashset!{&p1, &p2};
let goals = hashset!{¬_p1, ¬_p2};
let actions = hashset!{&a1, &a2, &a3, &a4, &a5, &a6};
let mut pg = PlanGraph::new(
initial_props,
goals,
actions,
);
pg.extend();
pg.extend();
let expected = vec![hashset!{&a1}, hashset!{&a2}];
let actual = SimpleSolver::search(&pg).unwrap();
assert_eq!(expected, actual);
}
}
#[cfg(test)]
mod btreeset_test {
use std::collections::BTreeSet;
#[test]
fn is_sorted () {
let mut b = BTreeSet::new();
b.insert(2);
b.insert(3);
b.insert(1);
assert_eq!(b.into_iter().collect::<Vec<_>>(), vec![1, 2, 3]);
let mut b = BTreeSet::new();
b.insert(1);
b.insert(2);
b.insert(3);
assert_eq!(b.into_iter().collect::<Vec<_>>(), vec![1, 2, 3]);
}
}