# 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-11-01

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# hevake-planner —— 通用 C++ 行为规划库

`hevake-planner` 是一个轻量、纯头文件（header-only）的 C++11 库，用于**带持续时间、
并发、资源约束的规划**。它在 `hevake::planner` 命名空间下提供两个引擎：

- `easy`（声明式，字符串键，开箱即用）
- `fast`（高性能，用户自定义 POD 状态）

两者都从初始世界状态出发，计算一组**带时间戳的步骤（schedule）**，在始终保持一组
**硬约束（invariants）**成立的前提下到达目标，默认最小化总耗时（makespan）。

它是领域无关的：同一个内核既服务经营类游戏（木材/铁/石头/金币、工人、建筑），
也服务机器人行为规划（符号事实、电量、机械臂、多臂并发）。

- **数值变量（fluent）** —— `wood`、`gold`、`worker`、`battery`、`arm`…
- **布尔事实** —— `at_room_a`、`holding_box`、`door_open`…
- **分类（枚举）变量** —— `posture`、`leg_mode`、`mode`（取有限集合中的一个标签，
  如 `stand`/`walk`/`run` 或 `1`/`2`/`4`/`5`）
- **带持续时间动作**，效果在动作的**开始**或**结束**触发。
- **并发**用"借用某个变量"来表达（工人 / 机械臂 / 槽位）。
- **硬约束**贯穿整个计划（如 `gold >= 0`、`wood <= 300`）。
- **动态容量** —— 工人只是一个普通变量，动作可以生产更多（建营地 → 工人 2 → 4）。

---

## 概念一览

| 概念 | 类型 | 含义 |
| --- | --- | --- |
| 世界状态 | `hevake::planner::easy::State` | 数值变量 + 布尔事实 + 分类标签 |
| 条件 | `hevake::planner::easy::Condition` | `ge/le/fact/notFact/enumEq/enumNe` 谓词 |
| 效果 | `hevake::planner::easy::Effect` | `NumberAdd/NumberSet/FactAdd/FactDel/EnumSet`，`AtStart`/`AtEnd` |
| 动作 | `hevake::planner::easy::Action` | 时长 + 前置条件 + 效果（+ 自定义钩子） |
| 目标 | `hevake::planner::easy::Goal` | 需要达到的一组条件的合取 |
| 硬约束 | `Problem::invariants` | 在每个持续动作边界和目标处都必须成立 |
| 问题 | `hevake::planner::easy::Problem` | 初始状态 + 动作 + 约束 + 目标 |
| 计划结果 | `hevake::planner::easy::Schedule` | 带时间戳步骤（`start`/`end`）+ 最终状态 |

`easy` 引擎的所有名字都在命名空间 `hevake::planner::easy` 下。`Numeric` 是 `double`
（整数值的游戏资源用 double 也是精确的；若想用 `int64_t`/`float`，改
`hevake/planner/easy/state.hpp` 里的一个 `using` 即可）。

---

## 快速上手

```cpp
#include <hevake/planner/easy/planner.hpp>

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), // 瞬时
    Action("sell_wood").consume("wood", 50).produce("gold", 2),    // 瞬时
    Action("build_camp").duration(5).needs("worker", 1)
        .consume("wood", 100).consume("stone", 200).consume("gold", 50)
        .produce("camp", 1).produce("worker", 1), // 营地永久 +1 工人
};

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
```

这个例子的最优计划是 **5 天**：先卖木头降到存储上限以下，然后用两个工人并行建两座
营地。建营地会产出工人，所以工人池从 2 增长到 4。

> 上面的代码是精简示意。随库发布的 `examples/settlement_easy.cpp` 是另一个更大的场景：
> 从零开始（木头/石头/金币为 `0`/`0`/`100`），通过建两座营地再雇佣，把工人从 2 扩到 4，
> 最优 makespan 为 **15 天**。

运行示例程序：

```sh
cmake -S . -B build
cmake --build build
./build/examples/settlement_easy # 打印 15 天计划（工人 2 -> 4）
./build/examples/settlement_fast # 同一场景，planner_fast 模型
./build/examples/robot_easy      # 完整机器人场景（枚举变量 + 电量）
./build/examples/robot_fast      # 同一机器人场景，planner_fast 模型
./build/examples/sweeper_fast    # 家庭扫拖机器人（planner_fast + 可采纳启发式）
./build/examples/sweeper_easy    # 同一扫拖场景，planner_easy 模型
ctest --test-dir build --output-on-failure
```

---

## 建模指南

### 动作（Action）

```cpp
Action("name").duration(days)          // 0（默认）= 瞬时
    .when(Condition)                   // 前置条件，开始时检查
    .needs(key, n)                     // 整个时长内借用 n
    .consume(key, n)                   // 开始时永久消耗 n
    .produce(key, n)                   // 结束时产出 n
    .set(key, v)                       // 结束时赋值为 v
    .setEnum(key, "label")             // 结束时赋分类标签
    .addFact(key) / .delFact(key)      // 布尔事实
    .effect(Effect{...})               // 原始效果兜底
    .customPrecondition(fn)            // 非声明式守卫
    .customEffect(fn);                 // 非声明式修改
```

- **`needs(key, n)`** 是并发原语：它隐式加前置条件 `key >= n`，开始时消耗 n，结束时
  归还 n。`needs("worker", 1)` 表示"该动作在持续期间占用 1 个工人"，所以两个工人并行
  跑两份，一个工人串行跑两份。对机械臂、机器槽位、电量同样适用。
- **`consume`** 是永久消耗（前置 `key >= n`，开始时 `-n`）。
- **`produce`** 是延迟产出（结束时 `+n`）。
- **效果有时机。** `AtStart` 效果在动作开始时触发（`needs`/`consume` 用它）；`AtEnd`
  效果在动作完成时触发（`produce` 用它）。零时长动作两者在同一时刻触发。

### 工人 / 容量只是变量

没有特殊的"资源池"类型。`worker` 只是一个普通数值变量。改变容量的动作只是
生产/消耗它：

```cpp
Action("build_camp").duration(5).needs("worker", 1)
    .produce("worker", 1);  // 营地建成时，+1 工人
```

### 分类（枚举）状态

分类变量在任意时刻只持有**一个字符串标签**，相当于单值枚举：
`posture ∈ {stand, walk, run}` 或 `mode ∈ {1, 2, 4, 5}`。标签总是存成字符串——
整数便捷重载只是把数字转成十进制字符串，所以 `setEnum("mode", 4)` 等价于
`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"
    Action("run").duration(1)
        .when(Condition::enumEq("posture", "walk"))
        .setEnum("posture", "run"),
};

p.goal = Goal{ { Condition::enumEq("posture", "run") } };
```

- **赋值**用 `.setEnum(key, "label")`（结束时，同 `.set`）或原始
  `.effect(Effect{Effect::Kind::EnumSet, key, 0, EffectTiming::AtStart, "label"})`。
- **比较**用 `Condition::enumEq(key, "label")` / `Condition::enumNe(key, "label")`。
  这是仅有的两种比较——没有集合成员判断。
- **未设置是一个真实状态。** 尚无标签的变量只是"不等于任何标签"：`enumEq` 为假、
  `enumNe` 为真。第一次设置它的动作，其前置条件不要依赖它。
- **读回**用 `getEnum(state, key)`（未设置时返回 `nullptr`）或直接 `state.enums.at(key)`。
- **整数就是十进制字符串。** `setEnum("mode", 4)` 写入 `"4"`，`Condition::enumEq("mode", 4)`
  与 `"4"` 比较——选哪个读起来顺眼就用哪个，底层是同一个变量值。

### 硬约束（Invariants）

`Problem::invariants`（`fast` 中为单数的 `Problem::invariant`）是对计划的硬约束，
其形式因引擎而异。

`planner_easy` 的 invariant 是状态条件，在以下时机检查：

- 每个**持续**动作的 `AtStart` 效果之后；
- 时间推进到某个完成时刻、其 `AtEnd` 效果之后；
- 目标处。

**瞬时（零时长）动作是原子的、可批处理的**，在 `planner_easy` 中豁免于上述检查。
这让一批瞬时动作能修复一个越界的初始状态——例如初始 `wood == 500` 超过
`wood <= 300` 的存储上限，可先卖木头把数值修回，再让时间流逝。

`planner_fast` 的 `Problem::invariant` 是单个
`bool(const Status&, double time, double cost)` 可调用对象：除状态外，还能看到路径
已流逝的计划时间，以及已启动动作的 `Action::cost()` 之和。它在每个动作边界检查
——持续动作开始、时间推进到完成时刻、**以及瞬时动作之后**——并在目标处检查，
因此成本上限不会被一批瞬时动作绕过。用同一机制即可表达路径级上限：

```cpp
p.invariant = [](const Status& s, double time, double cost) {
    return checkState(s) && time <= 5000 && cost <= 500;  // 截止时间 + 成本预算
};
```

一旦返回 false，该分支即被永久剪枝。请把时间/成本部分写成单调收紧的上限
（`time <= T`、`cost <= C`），因为搜索对每个 `(状态, 时间, 运行中动作)` key 只保留
累计 cost 最低的路径。相关字段见 `Schedule::cost` 与 `Progress::pruned`。

### 优化目标

`Problem::objective` 选择最小化什么：`Makespan`（默认）、`TotalCost`（各动作
`Action::cost` 之和）或 `TotalActionCount`（仅 `planner_easy`；`planner_fast`
支持 `Makespan` 与 `TotalCost`）。

---

## 设计说明

- **事件驱动的正向搜索。** 节点是 `(状态, 时间, 运行中的动作)`。两类边扩展它：
  *开始一个动作*（零时间）和 *推进时间到下一个完成时刻*（应用该动作的 `AtEnd` 效果）。
  时间只会推进到完成时刻，所以不会漏掉最优计划。

- **最优搜索。** `Planner::Options{...}` 控制 `max_nodes` 与 `time_limit_sec`
  （0 = 不限）。搜索是带可采纳启发式的 A*（未提供启发式时即一致代价搜索）。

- **进度回调与取消。** 设置 `Planner::Options::on_progress` 即可在搜索过程中收到
  `Progress{expanded, open, closed, g, h, f, elapsed_sec}` 快照（`planner_fast`
  额外提供 `pruned`，即被 invariant 拒绝的子转移数）。回调在
  规划线程上同步执行，最多每 `progress_every_nodes` 个扩展节点（默认 1000）或每
  `progress_every_sec` 秒回调一次（先到者触发）。回调返回 `false` 会立即中止搜索，
  结果是 `Schedule::cancelled == true`。不设置回调时，每节点开销只是一个 `if`。

  ```cpp
  Planner::Options opts;
  opts.progress_every_nodes = 10000;  // 0 = 关闭节点节流
  opts.progress_every_sec   = 1.0;    // 0 = 关闭时间节流
  opts.on_progress = [](const Progress& pr) {
      std::cerr << pr.expanded << " 节点, " << pr.elapsed_sec << " 秒\n";
      return true;                    // 返回 false -> 中止（Schedule::cancelled）
  };
  Schedule s = Planner{}.plan(p, opts);
  ```

  两个引擎的 `Progress` 数值字段相同；`planner_fast` 额外报告 `pruned`。

- **可采纳的 makespan 启发式。** 最优搜索由 A* 引导，用的是回归下界：对每个未满足的
  目标条件，找出能让该变量/事实朝所需方向移动的最便宜动作，再把这个动作的时长加上它
  自身前置条件达成所需的最大时间（前置条件互相重叠，用 `max` 合并）。资源数量、容量和
  数值边界被忽略，且假设副本可无限并行，因此结果仍可采纳；回归环被乐观地打破。

- **"免费"动作只跑一份并发副本。** 没有开始时资源开销（`needs`/`consume`）的动作可以
  无界重启，这会让搜索爆炸（例如没有前置、不占资源的 `open_door`）。因此搜索对这类
  *免费*动作最多启动一份并发副本。借用或消耗变量的动作不受影响，可跑到变量允许的份数。

- **适合重规划。** `Planner::plan(Problem)` 无状态——没有内部缓存——所以可以每个 tick
  用当前世界状态调用一次。

- **纯头文件。** 包含 `<hevake/planner/easy/planner.hpp>`（或 fast 版），无需链接任何库。
  CMake 暴露 `planner_easy::planner_easy` / `planner_fast::planner_fast` 接口目标，供
  `add_subdirectory`/`find_package` 集成。

---

## `planner_fast` —— 高性能版

`planner_easy` 以表达力优先：字符串键变量、声明式条件/效果、自动的可采纳启发式。
对于高频重规划（例如机器人每个 tick 都调用规划器），热路径上的字符串哈希和 map
查找会成为瓶颈。`planner_fast` 是**同一套搜索内核**，只是把状态和动作模型交给用户用
纯代码书写。

| | `planner_easy` | `planner_fast` |
| --- | --- | --- |
| 命名空间 | `hevake::planner::easy` | `hevake::planner::fast` |
| 状态 | `State`（三张字符串键 map） | 用户 `Status` 子类，POD 字段 |
| 键 / 标签 | 字符串 | `enum class` / 成员名（编译期） |
| 条件 / 效果 | 声明式 `Condition` / `Effect` | 虚函数（`canStart` / `applyStart` / `applyEnd`） |
| 启发式 | 自动回归下界 | 默认无（`h=0`，仍最优）；可选用户提供 |
| 并发 | 自动推断（"免费"动作上限一份） | 通过 `allowConcurrent()` 显式开启 |

两个基类承载模型（命名空间 `hevake::planner::fast`）：

```cpp
#include <hevake/planner/fast/planner.hpp>
using namespace hevake::planner::fast;

class Status {                              // 你的状态：不要用 std 容器/字符串
    virtual Status* clone() const = 0;
    virtual std::size_t hash() const = 0;   // 关闭集合快速路径
    virtual bool equals(const Status&) const = 0;
};

class Action {                              // 你的算子
    virtual const char* name() const = 0;
    virtual double duration() const { return 0; }          // 0 = 瞬时
    virtual bool canStart(const Status&) const = 0;        // 前置条件
    virtual void applyStart(Status&) const {}              // 借用/消耗
    virtual void applyEnd(Status&) const {}                // 归还/产出
    virtual double cost() const { return 0; }              // TotalCost + 成本预算
    virtual bool allowConcurrent() const { return false; } // 显式开启并发
};
```

规划器对状态只要求 `clone()`/`hash()`/`equals()` 三样东西；`hash()` 是关闭集合的快速
路径，`equals()` 只在罕见的哈希碰撞时被调用。`applyStart`/`applyEnd` 用手写方式实现
`needs`/`consume`/`produce` 惯用法（开始借用资源，结束归还），`allowConcurrent()` 让一个
动作可以同时跑多份（每份占用一个空闲工人/机械臂，份数受 `canStart` 约束）。

### Problem、Step、Schedule、Options

```cpp
struct Problem {
    const Status* initial = nullptr;
    std::vector<const Action*> actions;
    std::function<bool(const Status&)> goal;                    // 必填
    // 可选；(状态, 已流逝时间, 累计成本)
    std::function<bool(const Status&, double, double)> invariant;
    std::function<double(const Status&)> heuristic;              // 可选，须可采纳
    Objective objective = Objective::Makespan;                   // Makespan | TotalCost
};

struct Step {                                  // 一次被调度的动作
    const Action* action = nullptr;
    double start = 0;
    double end = 0;
    std::shared_ptr<const Status> after;       // 该动作结束后的状态
};

struct Schedule {
    bool found = false;
    double makespan = 0;
    double cost = 0;                           // 各动作 Action::cost() 之和
    std::vector<Step> steps;                   // 按开始时间排序
    std::unique_ptr<Status> final_state;
};

Planner::Options opts;   // max_nodes(1e6)、time_limit_sec(0=∞)
Schedule s = Planner{}.plan(p, opts);
```

fast 的 invariant 会收到状态、路径已流逝的 `time` 与累计 `cost`，
并且在瞬时动作后也会检查——参见[硬约束](#硬约束invariants)中的路径上限示例。

规划器会把 `Step::after` 填成**该动作完成之后**的状态快照（它回放返回的计划），
这样你无需自己重演就能打印逐步轨迹：

```cpp
for (const auto& step : s.steps) {
    std::cout << step.action->name() << "  " << step.start << ".." << step.end;
    if (step.after)
        std::cout << "  ->  " << describe(*step.after);  // 你自己的格式化函数
    std::cout << '\n';
}
```

`planner_fast` **没有自动启发式**：不提供 `Problem::heuristic` 时它按统一代价 A* 搜索
（`h = 0`，仍然最优）。你可以提供一个**可采纳**的下界（它必须永远不高于真实剩余
makespan，且目标处返回 `0`）来引导搜索，使困难的资源问题仍可解——
`examples/sweeper_fast.cpp` 里的 `sweeper_heuristic()` 就是一个完整范例。

参见 `examples/robot_fast.cpp`（机器人移植）、`examples/settlement_fast.cpp`（经营游戏）
和 `examples/sweeper_fast.cpp`（家庭扫拖机器人，含电量/水量/尘盒资源 + 可采纳启发式）。
链接 `planner_fast::planner_fast` 目标：

```cmake
target_link_libraries(your_target PRIVATE planner_fast::planner_fast)
```

**经验法则：** 用 `planner_easy` 做原型和一次性计划（声明式模型、自动启发式）；当同一份
计划需要高频反复运行、你希望每个节点的开销只是几次 POD 拷贝和虚调用（而不是字符串哈希
和 map 查找）时，改用 `planner_fast`。

---

## CMake 集成

```cmake
add_subdirectory(third_party/hevake-planner)     # 或 find_package(planner_easy)
target_link_libraries(your_target PRIVATE planner_easy::planner_easy)
# 或 fast 版：
# target_link_libraries(your_target PRIVATE planner_fast::planner_fast)
```

库要求 C++11。

---

## 目录结构

```
behavior-planner/
├── CMakeLists.txt
├── include/hevake/planner/
│   ├── easy/
│   │   ├── state.hpp        // State、Numeric、Comparison、Condition
│   │   ├── effect.hpp       // Effect、EffectTiming
│   │   ├── action.hpp       // Action 流式 API
│   │   ├── goal.hpp         // Goal、Objective
│   │   ├── problem.hpp      // Problem
│   │   ├── schedule.hpp     // ScheduledStep、Schedule
│   │   └── planner.hpp      // Planner、Options、搜索
│   └── fast/
│       ├── status.hpp       // Status 基类（clone/hash/equals）+ 哈希辅助
│       ├── action.hpp       // Action 基类（虚函数）
│       ├── problem.hpp      // Problem、Step、Schedule、Objective
│       └── planner.hpp      // Planner、Options、搜索
├── examples/
│   ├── settlement_easy.cpp // 经营游戏场景（planner::easy 模型）
│   ├── settlement_fast.cpp // 同一场景，planner::fast 模型
│   ├── robot_easy.cpp      // 完整机器人场景（planner::easy 模型）
│   ├── robot_fast.cpp      // 同一机器人场景，planner::fast 模型
│   ├── sweeper_easy.cpp    // 同一扫拖机器人（planner::easy 模型）
│   └── sweeper_fast.cpp    // 家庭扫拖机器人（planner::fast + 启发式）
└── tests/               // 单元测试（planner::easy + planner::fast）
```

## 适用范围

`hevake-planner` 面向**确定性、完全可观测的经典规划**。部分可观测、概率性结果和
层次化（HTN）分解留作未来扩展；`customPrecondition`/`customEffect` 钩子是非声明式需求的
兜底出口。