HTN规划入门：TFD算法详解与Python实现

一、结论先行TFD全序向前分解是STN规划的核心算法特点是特性说明状态确定分解过程中始终知道当前状态数值计算友好可精确计算电量、时间等资源工程首选航天任务规划的主流方法表达受限无法表达状态维持约束二、TFD核心思想三个关键词Total-order全序任务始终保持确定的执行顺序Forward向前从第一个任务开始依次处理Decomposition分解用方法将复合任务展开为子任务与POP偏序规划的对比算法任务顺序状态适用场景TFD全序A→B→C确定工程实践POP偏序可并行不确定理论研究三、算法流程3.1 伪代码defTFD(state,tasks,methods,operators):TFD算法核心实现# 1. 任务网络为空成功ifnottasks:return[]# 2. 选择第一个任务全序的关键tasktasks[0]remainingtasks[1:]# 3. 原子任务尝试执行操作iftask.is_primitive:foropinoperators:ifop.nametask.nameandop.precondition(state):new_stateop.apply(state)resultTFD(new_state,remaining,methods,operators)ifresultisnotNone:return[op]resultreturnNone# 失败# 4. 复合任务尝试分解else:formethodinmethods:ifmethod.nametask.nameandmethod.precondition(state):subtasksmethod.decompose(task)resultTFD(state,subtasksremaining,methods,operators)ifresultisnotNone:returnresultreturnNone# 失败3.2 关键步骤输入: 状态s, 任务列表tn, 方法集合M, 操作集合O 1. tn为空 → 返回空解成功 2. 选择第一个任务t 3. t是原子任务 - 是 → 找匹配操作 → 检查前提 → 执行 → 更新状态 → 递归 - 否 → 找匹配方法 → 分解为子任务 → 递归 4. 所有尝试失败 → 回溯四、完整示例4.1 问题设定初始状态卫星指向东电量100目标拍摄目标A4.2 领域定义# 操作定义operators{slew:{precondition:lambdas:s[power]10,effect:lambdas,target:{**s,pointing:target,power:s[power]-10}},take_photo:{precondition:lambdas,target:(s[pointing]targetands[power]5),effect:lambdas,target:{**s,has_image:{**s.get(has_image,{}),target:True},power:s[power]-5}}}# 方法定义methods{observe:{precondition:lambdas:True,subtasks:lambdatarget:[(slew,target),(take_photo,target)]}}4.3 执行过程初始: state{pointingeast, power100}, tasks[(observe, A)] Step 1: observe(A) 是复合任务 → 匹配方法observe → 分解为 [(slew, A), (take_photo, A)] Step 2: slew(A) 是原子任务 → 前提检查: power100 10 ✓ → 执行: pointingA, power90 Step 3: take_photo(A) 是原子任务 → 前提检查: pointingA ✓, power90 5 ✓ → 执行: has_image(A)true, power85 Step 4: 任务列表为空 → 成功 解: [slew(A), take_photo(A)]五、Python完整实现classState:状态表示def__init__(self,**kwargs):self.datakwargsdef__getitem__(self,key):returnself.data.get(key)def__setitem__(self,key,value):self.data[key]valuedefcopy(self):returnState(**self.data.copy())defpyhop(state,tasks,methods,operators): PyHOP风格TFD实现 参数: state: 当前状态 tasks: 任务列表 [(task_name, *args), ...] methods: 方法定义 operators: 操作定义 返回: 解操作序列或 None ifnottasks:return[]tasktasks[0]task_nametask[0]task_argstask[1:]remainingtasks[1:]# 原子任务iftask_nameinoperators:opoperators[task_name]ifop[precondition](state,*task_args):new_stateop[effect](state.copy(),*task_args)resultpyhop(new_state,remaining,methods,operators)ifresultisnotNone:return[task]resultreturnNone# 复合任务eliftask_nameinmethods:methodmethods[task_name]ifmethod[precondition](state,*task_args):subtasksmethod[subtasks](*task_args)resultpyhop(state,subtasksremaining,methods,operators)ifresultisnotNone:returnresultreturnNonereturnNone# 使用示例if__name____main__:# 初始状态stateState(pointingeast,power100,has_image{})# 目标任务tasks[(observe,A)]# 规划planpyhop(state,tasks,methods,operators)print(f解:{plan})# 输出: 解: [(slew, A), (take_photo, A)]六、TFD优缺点优点优点说明状态确定精确计算资源电量、时间搜索高效全序约束使搜索空间紧凑易于实现代码逻辑清晰便于调试工程友好航天调度主流方法缺点缺点说明无状态维持约束无法表达全程保持某状态并行受限全序限制了任务并行完备性问题某些问题可能无解工程补救问题解决方案状态维持资源锁定机制并行性预定义任务模板七、总结概念要点TFD 全序 向前 分解核心思想状态始终确定最大工程优势选任务 → 尝试操作/方法 → 递归算法流程适合工程实践航天任务规划首选推荐使用场景任务有自然顺序、需要数值计算、对效率要求高相关阅读任务规划概述从经典规划到HTNHTN规划是什么——形式化定义与核心机制STN与HTN的区别从理论到工程实践