hikmah_kernel/
planner.rs

1use crate::error::{KernelError, Result};
2use serde::{Deserialize, Serialize};
3use std::collections::{BTreeSet, HashSet, VecDeque};
4
5#[derive(Debug, Clone, Serialize, Deserialize)]
6pub struct PlanProblem {
7    pub initial: Vec<String>,
8    pub goal: Vec<String>,
9    pub actions: Vec<Action>,
10    #[serde(default = "default_max_depth")]
11    pub max_depth: usize,
12    /// Hard budget on explored states; the search stops and reports `budget_exhausted`.
13    #[serde(default = "default_max_states")]
14    pub max_states: usize,
15}
16
17#[derive(Debug, Clone, Serialize, Deserialize)]
18pub struct Action {
19    pub name: String,
20    #[serde(default)]
21    pub requires: Vec<String>,
22    #[serde(default)]
23    pub adds: Vec<String>,
24    #[serde(default)]
25    pub removes: Vec<String>,
26}
27
28#[derive(Debug, Clone, Serialize, Deserialize)]
29pub struct PlanResult {
30    pub found: bool,
31    pub actions: Vec<String>,
32    pub final_state: Vec<String>,
33    pub explored_states: usize,
34    /// True when `max_states` stopped the search before it could prove no plan exists.
35    #[serde(default)]
36    pub budget_exhausted: bool,
37}
38
39pub fn plan(problem: &PlanProblem) -> Result<PlanResult> {
40    if problem.goal.is_empty() {
41        return Err(KernelError::Invalid("planning goal cannot be empty".into()));
42    }
43    if problem.max_depth > MAX_DEPTH_LIMIT {
44        return Err(KernelError::Invalid(format!(
45            "max_depth {} exceeds the limit of {MAX_DEPTH_LIMIT}",
46            problem.max_depth
47        )));
48    }
49    if problem.max_states == 0 {
50        return Err(KernelError::Invalid("max_states must be positive".into()));
51    }
52    let initial: BTreeSet<String> = problem.initial.iter().cloned().collect();
53    let goal: BTreeSet<String> = problem.goal.iter().cloned().collect();
54    if goal.is_subset(&initial) {
55        return Ok(PlanResult {
56            found: true,
57            actions: Vec::new(),
58            final_state: initial.into_iter().collect(),
59            explored_states: 1,
60            budget_exhausted: false,
61        });
62    }
63
64    let mut queue = VecDeque::new();
65    queue.push_back((initial.clone(), Vec::<String>::new()));
66    let mut seen = HashSet::new();
67    seen.insert(state_key(&initial));
68    let mut explored = 0_usize;
69
70    let mut budget_exhausted = false;
71    while let Some((state, path)) = queue.pop_front() {
72        if explored >= problem.max_states {
73            budget_exhausted = true;
74            break;
75        }
76        explored += 1;
77        if path.len() >= problem.max_depth {
78            continue;
79        }
80        for action in &problem.actions {
81            let requires: BTreeSet<String> = action.requires.iter().cloned().collect();
82            if !requires.is_subset(&state) {
83                continue;
84            }
85            let mut next = state.clone();
86            for fact in &action.removes {
87                next.remove(fact);
88            }
89            for fact in &action.adds {
90                next.insert(fact.clone());
91            }
92            let mut next_path = path.clone();
93            next_path.push(action.name.clone());
94            if goal.is_subset(&next) {
95                return Ok(PlanResult {
96                    found: true,
97                    actions: next_path,
98                    final_state: next.into_iter().collect(),
99                    explored_states: explored,
100                    budget_exhausted: false,
101                });
102            }
103            let key = state_key(&next);
104            if seen.insert(key) {
105                queue.push_back((next, next_path));
106            }
107        }
108    }
109
110    Ok(PlanResult {
111        found: false,
112        actions: Vec::new(),
113        final_state: initial.into_iter().collect(),
114        explored_states: explored,
115        budget_exhausted,
116    })
117}
118
119fn state_key(state: &BTreeSet<String>) -> String {
120    state.iter().cloned().collect::<Vec<_>>().join("\u{1f}")
121}
122
123const MAX_DEPTH_LIMIT: usize = 64;
124
125fn default_max_depth() -> usize {
126    12
127}
128
129fn default_max_states() -> usize {
130    100_000
131}
hikmah_kernel/planner.rs

hikmah_kernel/
planner.rs
