# state-planner **Repository Path**: cpp-master/state-planner ## Basic Information - **Project Name**: state-planner - **Description**: 状态空间规划器 用户提供机器人的初始状态、目标状态，以及为达成目标状态而可选的动作（路径），它能计算出达成目标所要做的动作序列。 可用在机器人自动行为规划、经营类游戏的策略规划场景。 - **Primary Language**: Unknown - **License**: MIT - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2026-10-31 - **Last Updated**: 2026-10-31 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # hevake-planner — a general C++ behavior planner `hevake-planner` is a small, header-only C++11 library for **durative, concurrent, resource-constrained planning**. It ships two engines under the `hevake::planner` namespace: `easy` (declarative, string-keyed, batteries-included) and `fast` (high-performance, user-defined POD states). Each computes the schedule (a set of timed steps) that reaches a goal from a starting world state while keeping a set of hard invariants true, minimizing total time (makespan) by default. It is domain-agnostic on purpose: the same core serves a management game (wood/iron/stone/gold, workers, buildings) and robot behavior planning (symbolic facts, battery, robot arms, multi-arm concurrency). - **Numeric fluents** — `wood`, `gold`, `worker`, `battery`, `arm`, … - **Boolean facts** — `at_room_a`, `holding_box`, `door_open`, … - **Categorical (enum) fluents** — `posture`, `leg_mode`, `mode` (one of a finite set of labels, e.g. `stand`/`walk`/`run` or `1`/`2`/`4`/`5`) - **Durative actions** with effects that fire at the action's start *or* end. - **Concurrency** expressed as *borrowing* a fluent (workers / arms / slots). - **Hard invariants** enforced throughout the plan (e.g. `gold >= 0`, `wood <= 300`). - **Dynamic capacity** — workers are just a fluent, so an action can produce more of them (build a camp → workers go from 2 to 4). --- ## Concepts at a glance | Concept | Type | Meaning | | -------------- | ----------------------------- | --------------------------------------------------- | | World state | `hevake::planner::easy::State` | numeric fluents + boolean facts + categorical labels | | Condition | `hevake::planner::easy::Condition` | `ge/le/fact/notFact/enumEq/enumNe` predicate | | Effect | `hevake::planner::easy::Effect` | `NumberAdd/NumberSet/FactAdd/FactDel/EnumSet`, `AtStart`/`AtEnd` | | Action | `hevake::planner::easy::Action` | duration + preconditions + effects (+ custom hooks) | | Goal | `hevake::planner::easy::Goal` | conjunction of conditions to reach | | Hard invariant | `Problem::invariants` | must hold at every durative-action boundary + goal | | Problem | `hevake::planner::easy::Problem` | initial state + actions + invariants + goal | | Plan result | `hevake::planner::easy::Schedule` | timed steps (`start`/`end`) + final state | All names live in namespace `hevake::planner::easy`. `Numeric` is `double` (integer-valued game resources are exact as doubles; change one `using` in `hevake/planner/easy/state.hpp` if you prefer `int64_t`/`float`). --- ## Quick start ```cpp #include using namespace hevake::planner::easy; Problem p; p.initial = State{ {{"wood", 500}, {"iron", 300}, {"stone", 500}, {"gold", 200}, {"camp", 0}, {"worker", 2}}, {} }; p.actions = { Action("chop_wood").duration(1).needs("worker", 1).produce("wood", 100), Action("mine_iron").duration(2).needs("worker", 1).produce("iron", 10), Action("mine_stone").duration(1).needs("worker", 1).produce("stone", 30), Action("buy_stone").consume("gold", 10).produce("stone", 100), // instant Action("sell_wood").consume("wood", 50).produce("gold", 2), // instant Action("build_camp").duration(5).needs("worker", 1) .consume("wood", 100).consume("stone", 200).consume("gold", 50) .produce("camp", 1).produce("worker", 1), // camp permanently +1 worker }; p.invariants = { Condition::ge("gold", 0), Condition::le("wood", 300) }; p.goal = Goal{ { Condition::ge("camp", 2) } }; Schedule s = Planner{}.plan(p); // s.found == true, s.makespan == 5, s.final_state.numbers["worker"] == 4 ``` The optimal schedule for this example is **5 days**: sell wood to get under the storage cap, then build both camps in parallel with the two workers. Building a camp produces a worker, so the worker pool grows from 2 to 4. > The snippet above is a compact illustration. The shipped > `examples/settlement_easy.cpp` is a different, larger scenario: it starts from > nothing (wood/stone/gold `0`/`0`/`100`) and grows the worker pool from 2 to 4 > by building two camps and then hiring, for an optimal makespan of **15 days**. Run the example programs: ```sh cmake -S . -B build cmake --build build ./build/examples/settlement_easy # prints the 15-day schedule (grow 2 workers -> 4) ./build/examples/settlement_fast # the same scenario in the planner_fast model ./build/examples/robot_easy # the full robot scenario (enum fluents + battery) ./build/examples/robot_fast # the same robot scenario in the planner_fast model ./build/examples/sweeper_fast # home sweep-and-mop robot (planner_fast + admissible heuristic) ./build/examples/sweeper_easy # the same sweep-and-mop scenario in the planner_easy model ctest --test-dir build --output-on-failure ``` --- ## Modeling guide ### Actions ```cpp Action("name").duration(days) // 0 (default) = instant .when(Condition) // precondition, checked at start .needs(key, n) // borrow n for the whole duration .consume(key, n) // permanently spend n at start .produce(key, n) // yield n at end .set(key, v) // assign v at end .setEnum(key, "label") // assign a categorical label at end .addFact(key) / .delFact(key) // boolean facts .effect(Effect{...}) // raw effect escape hatch .customPrecondition(fn) // non-declarative guard .customEffect(fn); // non-declarative mutation ``` - **`needs(key, n)`** is the concurrency primitive: it adds an implicit precondition `key >= n`, consumes `n` at the start, and returns `n` at the end. `needs("worker", 1)` means "this action occupies 1 worker for its duration", so two workers run two copies in parallel, one worker runs them in series. It works identically for robot arms, machine slots, or battery. - **`consume`** is a permanent spend (precondition `key >= n`, `-n` at start). - **`produce`** is a delayed yield (`+n` at end). - **Effects have timing.** `AtStart` effects fire when the action starts (used by `needs`/`consume`); `AtEnd` effects fire when it completes (used by `produce`). For a zero-duration action both fire at the same moment. ### Workers / capacity are just fluents There is no special "resource pool" type. `worker` is an ordinary numeric fluent. An action that changes capacity simply produces/consumes it: ```cpp Action("build_camp").duration(5).needs("worker", 1) .produce("worker", 1); // when the camp finishes, +1 worker ``` ### Categorical (enum) states A categorical fluent holds **one string label at a time**, like a single-valued enum: `posture ∈ {stand, walk, run}` or `mode ∈ {1, 2, 4, 5}`. Labels are always stored as strings — an integer convenience overload just turns the number into its decimal string, so `setEnum("mode", 4)` is identical to `setEnum("mode", "4")`. ```cpp p.initial = State{ {}, {}, {{"posture", "stand"}} }; // numbers, facts, enums p.actions = { Action("walk").duration(2) .when(Condition::enumEq("posture", "stand")) // posture == "stand" .setEnum("posture", "walk"), // -> "walk" at end Action("run").duration(1) .when(Condition::enumEq("posture", "walk")) .setEnum("posture", "run"), }; p.goal = Goal{ { Condition::enumEq("posture", "run") } }; ``` - **Set with** `.setEnum(key, "label")` (at end, like `.set`) or the raw `.effect(Effect{Effect::Kind::EnumSet, key, 0, EffectTiming::AtStart, "label"})`. - **Compare with** `Condition::enumEq(key, "label")` / `Condition::enumNe(key, "label")`. These are the only two supported comparisons — no set-membership. - **Unset is a real state.** A fluent with no label yet is simply *not equal* to any label: `enumEq` is false, `enumNe` is true. Set it the first time with an action whose precondition doesn't depend on it. - **Read it back** with `getEnum(state, key)` (returns `nullptr` when unset) or directly via `state.enums.at(key)`. - **Integers are decimal strings.** `setEnum("mode", 4)` writes `"4"`, and `Condition::enumEq("mode", 4)` compares against `"4"` — pick whichever reads better; both are the same fluent value underneath. ### Invariants (hard constraints) `Problem::invariants` are checked: - after every **durative** action's `AtStart` effects, - after the `AtEnd` effects when time advances to a completion, and - at the goal. **Instant (zero-duration) actions are atomic and batchable** and are exempt from invariant checks. This lets a batch of instant actions repair an out-of-bounds initial state — e.g. an initial `wood == 500` above a `wood <= 300` storage cap is fixed by selling wood before any time passes. ### Optimization objective `Problem::objective` selects what to minimize: `Makespan` (default), `TotalCost` (sum of `Action::cost`), or `TotalActionCount`. --- ## Design notes - **Event-driven forward search.** A node is `(state, time, running-actions)`. Two edge kinds expand it: *start an action* (zero-time) and *advance time to the next completion* (applies that action's `AtEnd` effects). Time only ever advances to a completion time, so optimal schedules are never missed. - **Optimal by default, greedy on request.** `Planner::Options{...}` controls `max_nodes`, `time_limit_sec`, and `optimal`. `optimal = false` runs a greedy satisficing search (start everything applicable, no backtracking), useful for large state spaces or high-frequency robot re-planning. - **Progress reporting & cancellation.** Set `Planner::Options::on_progress` to receive a `Progress{expanded, open, closed, g, h, f, elapsed_sec, optimal}` snapshot during the search. It is delivered on the planning thread at most once per `progress_every_nodes` expansions (default 1000) or `progress_every_sec` seconds, whichever comes first. Returning `false` stops the search immediately and yields `Schedule::cancelled == true`. With no callback set the overhead is a single `if` per node. ```cpp Planner::Options opts; opts.progress_every_nodes = 10000; // 0 disables the node throttle opts.progress_every_sec = 1.0; // 0 disables the time throttle opts.on_progress = [](const Progress& pr) { std::cerr << pr.expanded << " nodes, " << pr.elapsed_sec << " s\n"; return true; // false -> abort (Schedule::cancelled) }; Schedule s = Planner{}.plan(p, opts); ``` Both engines expose the same `Progress` shape and `Options` fields. - **Admissible makespan heuristic.** The optimal search is A* guided by a regression lower bound: for each unsatisfied goal condition it finds the cheapest action that can move that fluent/fact in the needed direction, then adds that action's duration to the max time its own preconditions take to achieve (preconditions overlap, so they combine with `max`). Resource amounts, capacity and numeric bounds are ignored and unlimited parallel copies are assumed, so the result stays admissible; regression cycles are broken optimistically. - **"Free" actions run one concurrent copy.** An action with no start-time resource cost (`needs`/`consume`) can be restarted without bound, which would blow up the search (e.g. `open_door` with no precondition and no resource use). The search therefore starts at most one concurrent copy of such a *free* action. Actions that borrow or spend a fluent are unaffected and may run as many copies as the fluent allows. - **Re-planning friendly.** `Planner::plan(Problem)` is stateless — no internal cache — so it can be called every tick with the current world state. - **Header-only.** Include ``; link nothing. CMake exposes the `planner_easy::planner_easy` interface target for `add_subdirectory`/`find_package` integration. --- ## Integration (CMake) ```cmake add_subdirectory(third_party/hevake-planner) # or find_package(planner_easy) target_link_libraries(your_target PRIVATE planner_easy::planner_easy) ``` The library requires C++11. --- ## `planner_fast` — high-performance variant `planner_easy` optimizes for expressiveness: string-keyed fluents, declarative conditions/effects, and an automatic admissible heuristic. For high-frequency re-planning (e.g. a robot calling the planner every tick), the string hashing and map lookups on that hot path can dominate. `planner_fast` is the **same search engine**, with the state and action model handed to the user as plain code. | | `planner_easy` | `planner_fast` | | --- | --- | --- | | Namespace | `hevake::planner::easy` | `hevake::planner::fast` | | State | `State` (three string-keyed maps) | a user `Status` subclass, POD fields | | Keys / labels | strings | `enum class` / member names (compile-time) | | Conditions / effects | declarative `Condition` / `Effect` | virtual methods (`canStart` / `applyStart` / `applyEnd`) | | Heuristic | automatic regression lower bound | none by default (`h=0`, still optimal); optional user-provided | | Concurrency | inferred ("free" actions capped at one) | explicit opt-in via `allowConcurrent()` | Two base classes carry the model (namespace `hevake::planner::fast`): ```cpp #include using namespace hevake::planner::fast; class Status { // your state: no std containers/strings virtual Status* clone() const = 0; virtual std::size_t hash() const = 0; // closed-set fast path virtual bool equals(const Status&) const = 0; }; class Action { // your operators virtual const char* name() const = 0; virtual double duration() const { return 0; } // 0 = instant virtual bool canStart(const Status&) const = 0; // precondition virtual void applyStart(Status&) const {} // borrow/consume virtual void applyEnd(Status&) const {} // return/produce virtual double cost() const { return 0; } // TotalCost only virtual bool allowConcurrent() const { return false; } // opt-in parallelism }; ``` `clone()`/`hash()`/`equals()` are the only three things the planner requires of a state; `hash()` is the closed-set fast path and `equals()` resolves the rare collision. `applyStart`/`applyEnd` implement the `needs`/`consume`/`produce` idiom by hand (borrow a resource at start, return it at end), and `allowConcurrent()` opts an action into running several parallel copies (one per free worker/arm, bounded by `canStart`). ### Problem, Step, Schedule, Options ```cpp struct Problem { const Status* initial = nullptr; std::vector actions; std::function goal; // required std::vector> invariants; // optional std::function heuristic; // optional, admissible Objective objective = Objective::Makespan; // Makespan | TotalCost }; struct Step { // one scheduled action occurrence const Action* action = nullptr; double start = 0; double end = 0; std::shared_ptr after; // state right after it completes }; struct Schedule { bool found = false; double makespan = 0; std::vector steps; // sorted by start time std::unique_ptr final_state; }; Planner::Options opts; // max_nodes (1e6), time_limit_sec (0 = unlimited), optimal (true) Schedule s = Planner{}.plan(p, opts); ``` The planner fills `Step::after` with a snapshot of the state **after that action completes** (it replays the returned schedule), so you can print a step-by-step trace without re-simulating it yourself: ```cpp for (const auto& step : s.steps) { std::cout << step.action->name() << " " << step.start << ".." << step.end; if (step.after) std::cout << " -> " << describe(*step.after); // your own formatter std::cout << '\n'; } ``` The fast planner ships **no automatic heuristic**: without a `Problem::heuristic` it runs as uniform-cost A* (`h = 0`, still optimal). You may supply an **admissible** lower bound (it must never over-estimate the true remaining makespan, and must return `0` at the goal) to keep a hard resource problem tractable — `sweeper_heuristic()` in `examples/sweeper_fast.cpp` is a worked example. See `examples/robot_fast.cpp` (robot port), `examples/settlement_fast.cpp` (management game), and `examples/sweeper_fast.cpp` (home sweep-and-mop robot with battery/water/dust resources + an admissible heuristic). Link the `planner_fast::planner_fast` target: ```cmake target_link_libraries(your_target PRIVATE planner_fast::planner_fast) ``` **Rule of thumb:** use `planner_easy` for authoring and one-off plans (declarative model, automatic heuristic); reach for `planner_fast` when the same plan is re-run at high frequency and you want the per-node cost to be a few POD copies and virtual calls instead of string hashes and map lookups. --- ## File layout ``` behavior-planner/ ├── CMakeLists.txt ├── include/hevake/planner/ │ ├── easy/ │ │ ├── state.hpp // State, Numeric, Comparison, Condition │ │ ├── effect.hpp // Effect, EffectTiming │ │ ├── action.hpp // Action fluent API │ │ ├── goal.hpp // Goal, Objective │ │ ├── problem.hpp // Problem │ │ ├── schedule.hpp // ScheduledStep, Schedule │ │ └── planner.hpp // Planner, Options, search │ └── fast/ │ ├── status.hpp // Status base (clone/hash/equals) + hash helpers │ ├── action.hpp // Action base (virtuals) │ ├── problem.hpp // Problem, Step, Schedule, Objective │ └── planner.hpp // Planner, Options, search ├── examples/ │ ├── settlement_easy.cpp // the management-game scenario (planner::easy model) │ ├── settlement_fast.cpp // the same scenario in the planner::fast model │ ├── robot_easy.cpp // the full robot scenario (planner::easy model) │ ├── robot_fast.cpp // the same robot scenario in the planner::fast model │ ├── sweeper_easy.cpp // the same sweep-and-mop robot (planner::easy model) │ └── sweeper_fast.cpp // home sweep-and-mop robot (planner::fast + heuristic) └── tests/ // unit tests (planner::easy + planner::fast) ``` ## Scope `hevake-planner` targets **deterministic, fully-observable, classical planning**. Partial observability, probabilistic outcomes, and hierarchical (HTN) decomposition are left as future extensions; the `customPrecondition`/`customEffect` hooks are the escape hatches for anything non-declarative.