foundations-ai-planning-search

AI 规划与搜索基础

用途

本技能将规划与搜索理论（A*、CSP、MCTS、PDDL、HTN 等）应用于 AI 智能体。适用场景包括：

任务可表述为状态、动作、转移、目标与代价。
需要 A*、一致代价搜索、束搜索、回溯、alpha-beta、MCTS、STRIPS/PDDL、HTN 或 CSP 推理。
LLM 智能体臆造动作序列，需要显式有效性检查。
工作流需要规划器作为工具，而不仅是提示分解。
搜索或规划算法选择会改变运行时、完备性、最优性或失败行为。

不适用场景：产品搜索、向量检索、排序或查询匹配（转用软件搜索或 ai-rag）；期望效用、信息价值、实物期权或老虎机（转用决策理论基础）；反馈控制、设定点跟踪或 MPC（转用控制理论基础）；策略激励设计或均衡（转用博弈论基础）；共享收益与分区信息的协作子智能体分配（转用团队理论基础）；通用智能体架构、记忆、工具或 MCP/A2A 编排（在本技能界定规划器边界后转用 ai-agents）。

主要能力（十项原语）

问题形式化：状态、动作、转移模型、目标测试、路径代价。
无信息搜索：完备性基线，分支因子 b、深度 d、前沿策略。
启发式搜索：启发式 h(n)、可采纳性、一致性。
局部搜索：邻域、目标、重启/调度。
约束满足：变量、域、约束、MRV/LCV、弧一致性。
对抗搜索：效用、深度、alpha-beta 边界、rollout 策略。
经典规划：STRIPS/PDDL、进展/回归、规划图。
分层规划：方法、子任务、顺序约束。
偶然/信念状态规划：信念状态、感知动作、策略 vs 序列。
规划器-智能体集成：规划器工具、状态抽象、验证器、重规划触发。

使用方式（工作流）

将问题形式化为状态、动作、转移模型、目标测试与代价。
分类主导结构：路径搜索、分配/CSP、博弈树、符号计划、层次或不确定性。
选择保留所需保证的最简算法族：完备性、最优性、有界内存或足够好的解质量。
实现前显式写下搜索/规划假设。
对于 LLM 智能体，决定 LLM 可提议什么、规划器/验证器必须强制执行什么。
用小规模可手工核验案例、不可能案例与对抗性边界案例验证。
在声称保证前，记录单行保证台账：声明 | 算法 | 模型假设 | 运行时限制 | 验证器 | 反例测试。

组合配方

带有效计划的 LLM 智能体：问题形式化定义类型化状态与合法动作模式 → 经典规划编码前置条件/效果 → 规划器-智能体集成中 LLM 提议目标或抽象，规划器验证，执行器仅运行合法下一动作 → 在失败前置条件、外部状态漂移或新观测后重规划。
尊重约束的配置助手：CSP 将组件建模为变量、兼容规则为约束；若偏好为软约束且空间过大则用局部搜索；期望值或风险加权路由至决策理论基础。
博弈或仿真智能体：确定性博弈用 minimax 或 alpha-beta；随机或高分支博弈用 MCTS 与 rollout 评估；用领域启发式评估状态；均衡、机制或激励设计路由至博弈论基础。
面向人工操作的工作流规划器：HTN 编码标准分解与方法选择；经典规划验证步骤前置条件；交接修复与共同基础检查用 grounding-communication 基础。
演示可用、生产失败：按可能性排查生产分支因子、启发式/验证器与演示分布拟合、未建模非确定性、缺失或无界重规划触发、评估中存在但生产执行路径缺失的验证器、被延迟或成本限制悄悄缩减的搜索预算。

反模式示例

无状态模型直接“让 LLM 规划”：需定义状态、动作模式、前置条件、效果与代价。
承诺最优却用贪心搜索：使用可采纳/一致的启发式的 A*，或放弃最优承诺。
高分支无深度界的 BFS：改用 UCS/A*、迭代加深、剪枝或抽象。
约束埋在提示文字中：建模为带传播与回溯的 CSP。
真实世界谈判用 minimax：收益与策略并非有限博弈树，路由至博弈论基础。
生成 PDDL 却从不验证：运行域/问题验证并检查计划前置条件/效果。
每个 token/工具调用都重规划：仅在状态漂移、前置条件失败或新观测时重规划。
把有效计划当安全计划：有效性检查前置条件/效果，不检查目标或路径是否应被执行；需在动作集上另加安全/权限门。
无验证器就加树搜索提升准确率：先确认评分器/验证器可靠性，再在匹配算力下按难度分桶与 best-of-N 比较。

误用边界

把提示大纲称为计划：缺少可执行动作模型或有效性检查，需转换为状态/动作/前置条件/效果模型。
把局部最优当全局最优：局部搜索在缺乏强假设时不完备，需重启、小实例精确搜索或说明近似。
用过估计启发式声称 A* 最优：最优性依赖可采纳性/一致性，需证明 h(n) ≤ 真实剩余代价或降低声明。
将软偏好建模为硬 CSP 约束：搜索可能因可避免原因不可行，需分离硬约束与加权目标。
协作团队用对抗搜索：协作信息结构原语不同，路由至团队理论基础。
把部分可观测当确定性规划：动作可能需要感知与偶然分支，使用信念状态或偶然规划。
从规划能力推断计划安全：两者独立测量、互不跟随，需独立于规划器成功指标对动作集设门。

限制与注意事项

在声称搜索保证前，需加载保证矩阵：有限分支与非负代价本身不足以在无限空间建立 UCS/A* 完备性；标准界要求步代价下界为正 epsilon。A* 图搜索在使用可采纳但不一致启发式时必须重新打开改进状态，或使用一致性永久关闭节点。规划器有效性要求正确的前置条件/效果。不得编造基准数字。若推荐规划器或求解器，应报告假设、问题规模与验证案例，而非泛泛速度声明。

LLM 规划基准数字变化快且跨论文鲜有可比性：成功率取决于领域、实例规模、提示编码、重试次数及验证器是否在环。应引用具体设置或定性陈述结果，不得跨领域沿用标题百分比。

完备性或最优性属于所建模问题，不自动属于真实执行器。若生产环境中的前置条件、效果、代价、可观测性或资源限制不同，应报告为经验证的启发式计划，而非继承算法定理。

技能介绍