第3期 张万鹏，等：一种利用工作流模型的分层任务网络规划领域建模方法 .245· 了最大时间.由实验结果可以看出，在随着问题规模 2→→1→…)移动 的增加，利用工作流模型进行领域建模，引入领域知 4)前提2：上次移动的是最小的圆盘 识后对规划器求解效率的提高越大.在n=40时， 5)子任务2：移动其他的圆盘 效率提高了近100倍。 该方法进一步细化可以表示为如图7所示的 3.2汉诺伊塔 流程结构.该流程包含了1个基础的行动move和2 汉诺伊塔问题是一个经典的规划问题，它要求 层递归结构，第1层的selectDirection递归用于确定 将一组从大到小叠放的圆盘从一个立柱通过一个中 圆盘初始的移动方向，当圆盘个数为奇数时，最小的 间立柱的中转移动到另外一个立柱，移动时要求圆 圆盘从立柱1移动到3，当圆盘个数为偶数时，最 盘只能放置在比它大的圆盘上.当圆盘数较多时，由 小的圆盘从立柱t,移动到t2;第2层rotateTower递 于其状态的组合爆炸，使得很多经典规划器对其求 归用于表达上述方法，movel为移动最小圆盘的行 解比较困难.可以引入如下的领域知识，避免规划器 动，move2为移动其他圆盘的行动，exchange的作用 在搜索过程中进行不必要的回溯。 是保证最小的圆盘按顺时针方向移动，exchange- 1)方法：移动圆盘. Clear是对目标状态的判断，当t1和t2上都没有圆盘 2)前提1：上次移动的不是最小的圆盘， 时，表明所有圆盘已经移动到3上，递归终止 3)子任务1：将最小的圆盘按顺时针方向(t1→ ® shiftTower EselectDirection 案可 branch_Set Branch Find 回 ▣sequenceActivity I 分 中move1 4 Bexchange 3 中NIL exchangeClear exchangRL exchangLR 回 4 中done 中move2 中move2 向 图7移动圆盘过程的工作流表达 Fig.7 Workflow of moving towers 实验生成n=3,4,…,14的n-ring问题，进行了 出，当问题规模较大时(n=12,13,14),F℉-WF的 50次实验，对每个n值的求解时间取50次实验的 效率明显高于FP-Plain. 平均值，实验结果如图8所示.由实验结果可以看