HTN规划中面向多计划生成的顺序任务分解算法

顺序任务分解算法（OTD）是层次任务网规划（HTN）中的一种高效求解算法．由于算法中的计划生成采用一次性回溯机制，每次求解过程只能产生一个可行计划．文中提出了一种能够快速生成多个可行计划的回溯算法．该算法采用分段回溯的计划生成机制，充分利用了求解过程中生成的局部解序列，从而能够一次性地快速生成多个可行计划，为寻求优化的计划和进行计划的评估提供更为有效、灵活的支持．

Multiple Plans Oriented OTD Algorithm for HTN Planning

Ordered task decomposition （OTD） algorithm is an efficient algorithm for hierarchical task network （HTN） planning. However, since the backtracking process for plan generation is a standalone computing process, the problem solving process can only produce at most one final plan. In this paper, an improved OTD algorithm is proposed to produce multiple plans efficiently. This algorithm adopts segmented backtracking method, which can utilize pieces of action-sequence produced during search process, and can build a number of plans quickly. This algorithm can provide powerful support to optimized plan generation and plan evaluation in OTD-based HTN planning.