49 · 附录：规划模块（Planning Module）

摘要（Abstract）

用于规划与调度的低层模块，供 Embabel Agent Platform 使用。

A* GOAP 规划算法概览

A* GOAP（Goal-Oriented Action Planning，目标导向动作规划）规划器是 A* 搜索算法的一种实现， 专门用于规划达成指定目标的动作序列。 该算法通过探索潜在的动作序列并最小化总体成本，高效地从初始世界状态找到通往目标状态的最优路径。

核心算法组件

• A* 搜索：通过探索状态空间找出最优动作序列；
• 前向规划（Forward Planning）：从起始状态向目标模拟动作；
• 后向规划（Backward Planning）：从目标反向推导，以优化计划；
• 计划仿真（Plan Simulation）：验证计划确实达成了预期目标；
• 剪枝（Pruning）：移除无关动作，产出高效的计划；
• 未知条件处理（Unknown Condition Handling）：管理不完整的世界状态信息。

A* 搜索算法

A* 搜索算法通过维护以下结构运作：

• Open List（开放列表）：待探索状态的优先队列，按 f-score 排序；
• Closed Set（封闭集）：已完全探索过的状态；
• g-score：到达某状态已累积的成本；
• h-score：到达目标剩余成本的启发式估计；
• f-score：总估计成本（g-score + h-score）。

处理流程（Process Flow）

1. 初始化

• 把起始状态放入开放列表；
• 将其 g-score 置为 0，并计算其 h-score。

2. 主循环

当开放列表非空时：

• 从开放列表选出 f-score 最低的状态；
• 如果该状态满足目标，构造并返回计划；
• 否则把该状态标记为已处理（加入封闭集）；
• 对每一个适用动作，生成下一个状态；若它优于已有路径，则加入开放列表。

3. 路径重建

找到目标状态时，沿着前驱指针回溯重建路径，产出一个由动作序列构成的计划。

参考：AStarGoapPlanner.kt → AStarGoapPlanner:planToGoalFrom:

前向与后向规划的优化

规划器实现了两趟（two-pass）优化策略，用来消除不必要的动作。

后向规划优化

这一趟从目标条件反向推导，只保留对达成目标有贡献的动作。

参考：AStarGoapPlanner.kt → _backwardPlanningOptimization

前向规划优化

这一趟从起始状态模拟整个计划，移除那些并未朝目标推进的动作。

参考：AStarGoapPlanner.kt → _forwardPlanningOptimization

计划仿真（Plan Simulation）

计划仿真按顺序执行动作，以验证计划的正确性。

参考：函数 simulatePlan(startState, actions)

对规划系统剪枝（Pruning Planning Systems）

规划器可以对整个规划系统剪枝，移除无关动作：

PlanningSystem prune(PlanningSystem planningSystem) {
    // 取出通往所有目标的所有计划
    List<Plan> allPlans = plansToGoals(planningSystem);
    // 只保留至少出现在一个计划中的动作
    Set<Action> filteredActions = planningSystem.getActions().stream()
            .filter(action -> allPlans.stream()
                    .anyMatch(plan -> plan.getActions().contains(action)))
            .collect(Collectors.toSet());
    return planningSystem.withActions(filteredActions);
}

启发函数（Heuristic Function）

启发函数用于估计"从给定状态到达目标的成本"。

完整规划流程

• 用起始状态、动作与目标条件进行初始化；
• 运行 A* 搜索，找出初始动作序列；
• 应用后向规划优化消除不必要的动作；
• 应用前向规划优化进一步精炼计划；
• 通过仿真验证计划；
• 返回优化后的动作序列；若不存在合法计划则返回 null。

Agent 剪枝流程（Agent Pruning Process）

当为特定目标对某个 Agent 剪枝时：

• 识别规划系统中所有已知条件；
• 基于输入条件设置初始状态；
• 找出通往每个目标的所有可能计划；
• 只保留至少出现在一个计划中的动作；
• 用剪枝后的动作集合创建新的 Agent。

这种周全的做法确保 Agent 只包含达成其既定目标所必需的动作， 从而提升效率，并防止动作在不同 Agent 之间"泄漏"。

A* GOAP 规划中的"进展判定"逻辑

方法 forwardPlanningOptimization 中的进展判定逻辑是 A* GOAP 算法前向规划优化的关键部分。 该逻辑确保只有真正让状态朝目标推进的动作才会被纳入最终计划。

进展判定表达式

boolean progressMade = !nextState.equals(currentState) &&
        action.getEffects().entrySet().stream().anyMatch(entry -> {
            String key = entry.getKey();
            Object value = entry.getValue();
            return goal.getPreconditions().containsKey(key) &&
                    !Objects.equals(currentState.get(key), goal.getPreconditions().get(key)) &&
                    (Objects.equals(value, goal.getPreconditions().get(key)) || !nextState.containsKey(key));
        });

逐项解释

该表达式仅当动作对达成目标状态产生了有意义的推进时才为 true。逐项拆解：

• nextState != currentState —— 验证该动作确实改变了世界状态，防止把无效果的动作算进来。
• action.effects.any { ... } —— 检查该动作产生的每一个效果；只要有任意一个效果满足内部条件就返回 true。
• goal.preconditions.containsKey(key) —— 确保只考虑与目标所要求的条件相关的效果，忽略那些修改与目标无关条件的动作。
• currentState[key] != goal.preconditions[key] —— 检查当前条件值与目标要求是否不同；只有当我们在改变一个"需要被改变"的条件时才算作进展。
• (value == goal.preconditions[key] || key not in nextState) —— 检查动作产生进展的两种可能方式：
  • value == goal.preconditions[key]：动作把该条件改成与目标要求完全一致 —— 这是对目标达成的直接推进；
  • key not in nextState：动作把该条件从状态中彻底移除 —— 如果该条件此前处于不正确的状态，这被视为进展； 它也允许"清除障碍或重置条件"这类动作。