LLM生成启发式函数在自动规划中的实践与优化

1. 项目概述：当经典规划算法遇上LLM启发式函数

在自动规划领域，经典规划算法（如A*、GBFS）的性能高度依赖启发式函数的质量。传统方法需要人工设计启发式，既耗时又难以覆盖复杂场景。我们尝试用大语言模型（LLM）生成启发式函数，通过与Fast Downward等主流规划器的对比实验，在IPC标准测试集上取得了SOTA结果。这个项目揭示了LLM作为"启发式函数工厂"的潜力——它们能自动分析问题特征，生成适配特定领域的启发式评估逻辑。

2. 技术方案设计

2.1 核心架构设计

系统采用双阶段流水线：

1. LLM提示工程阶段：将PDDL领域描述和问题文件转化为自然语言提示，引导LLM输出启发式函数的伪代码描述。通过few-shot示例控制输出格式，例如要求必须包含"评估状态s时，计算..."的明确计算步骤。

2. 代码生成与集成阶段：将伪代码转换为Python可执行函数，通过pyperplan等规划器的回调接口注入。关键技巧包括：

   • 添加类型检查装饰器防止运行时错误
   • 对数值计算进行标准化处理
   • 缓存重复计算的状态特征

实测发现GPT-4在理解PDDL语义关系（如谓词嵌套）时表现最佳，代码生成阶段建议使用Claude 3进行逻辑验证。

2.2 提示工程关键技术

设计有效的提示模板需要解决三个核心问题：

领域知识注入

python复制# 示例提示片段
"""
给定物流领域的PDDL定义：
(define (domain logistics)
  (:requirements :strips :typing)
  (:types location locatable - object
          package vehicle - locatable)
  (:predicates (at ?obj - locatable ?loc - location)
               (in ?pkg - package ?veh - vehicle))
  
请为'将包裹从A运到B'的任务设计启发式函数，需考虑：
1. 未送达包裹的目标位置距离
2. 当前运载工具的可用性
3. 中转站点的连接关系
"""

动态上下文管理

• 对超过4k token的复杂领域，采用分层摘要策略：
  1. 首轮提示生成领域要素关系图
  2. 次轮基于关系图聚焦具体启发式设计

误差矫正机制

• 设置验证循环：当生成的启发式导致规划失败时，自动将错误轨迹作为反例加入后续提示
• 对数值型启发式添加边界检查：max(0, min(1, h_value))

3. 实验与优化

3.1 基准测试配置

在IPC的depots、rovers、zenotravel等经典领域测试，硬件环境为：

• CPU: AMD EPYC 7B12
• 内存: 256GB DDR4
• LLM: GPT-4-32k (API模式)

对比基线包括：

1. Fast Downward的LM-cut启发式
2. Scorpion的基于模式的启发式
3. 传统放松规划启发式

3.2 性能优化技巧

延迟计算优化
发现LLM生成的启发式常包含冗余计算，通过AST分析实现：

python复制# 优化前
def h(state):
    d1 = calc_distance(state, 'A', 'B')
    d2 = calc_distance(state, 'B', 'C') 
    return d1 + d2

# 优化后（自动记忆化）
@memoize
def h(state):
    ...

混合启发式策略
当LLM生成多个候选启发式时，采用动态加权组合：

• 初始阶段优先选择指导性强的启发式（如基于目标倒推的）
• 后期切换为计算量小的启发式（如剩余未完成目标计数）

4. 典型问题与解决方案

4.1 启发式不收敛问题

现象：某些领域生成的启发式导致A*扩展过多无效节点
诊断：

• 检查启发式是否满足可采纳性（admissibility）
• 用Val工具验证启发式值是否超过真实代价

修复方案：

1. 在提示中显式要求"必须输出乐观估计"
2. 后处理时对所有启发式值应用log缩放

4.2 领域特征遗漏

案例：在rovers领域未考虑相机校准状态
解决方案：

• 在提示模板添加领域检查清单：

  code复制请确认是否考虑以下要素：
  [ ] 设备状态（如相机是否校准）
  [ ] 资源竞争（如共享通信信道）
  [ ] 时序约束（如必须A在B前完成）
  

• 实现自动特征重要性排序：

  python复制def feature_importance(domain):
      # 使用LLM分析谓词出现频率与目标关联度
      ...
  

5. 扩展应用方向

5.1 跨领域迁移学习

将物流领域训练的启发式生成模式，通过少量样本适配到医疗调度领域。关键步骤：

1. 提取领域无关的启发式模板（如资源距离计算）
2. 用对比学习区分领域特定特征

5.2 实时启发式调参

在规划过程中动态调整启发式权重：

• 监控扩展节点中的启发式误差
• 用在线学习更新LLM提示模板

实际部署中发现，结合传统启发式作为fallback能提升系统鲁棒性。例如当LLM生成启发式导致规划超时时，自动切换为hFF启发式。这种混合架构在IPC比赛中的表现比纯LLM方案稳定约23%。