基于与或图的启发式复杂决策任务求解方法

摘 要：现代战争的快速性，要求计算机辅助决策系统能够支持指挥员快速形成有效决策计划，以实现战场指挥中任务逐级规划、执行的高效性。图搜索法是智能决策系统中问题规划的重要方法，可有效支持决策支持系统（DSS）完成有效任务分解。本文提出一种基于与或图的启发式决策求解方法，并通过扩展与、或连接符支持任务分解，所定义构造算子保障与或解图的可执行性，可有效支持复杂决策任务求解和执行，并通过一个火力打击决策任务案例验证本方法的有效性。

关键词：任务分解；复杂决策；与或图；启发式；可执行任务流

中图分类号：TP311.5 文献标识码：A

1 引言（Introduction）

现代作战的高速度、快节奏，需要实现快速的决策。传统的机械化地方作战通常是任务式指挥法，逐级赋予任务计划。通常在一个火力打击决策中，需要明确具体打击目标、区分打击任务、确定打击顺序、打击效果评估等，是一个“侦、策、打、评”的不断反复的过程，尤其要求总指挥部具有更快的组织计划反应能力和决策能力。决策时间越短，越能有效占领战场优势，而借助计算机的智能决策辅助，可快速形成有效的决策计划，使己方的决策周期始终快于敌方的决策周期，掌握战场的主动权[1]。

决策支持系统（DSS）是基于计算机的交互式系统，用以帮助决策者使用数据和模型去解决结构化较差的问题。决策科学和决策支持科学发展至今，研究者和实践家们在各自的领域提出了大量的决策模型[2]。根据不同的应用领域和任务性质，利用Decision Support System（DSS）进行复杂决策任务。目前有关任务分解方法的主要研究包括[3]：文献[4]借助项目工作分解结构技术，从任务静、动态结构两方面描述作战任务的分解概念，并举例建立了任务的分解结构和流程结构；文献[5]在文献[6—8]的研究基础上，提出一种按照基于活动约束的任务粒度设计方法，以得到最佳的任务分解模型，文中的粒度是静态的，即最优设计；另外还有利用过程网[9]和时序逻辑公式[10]等有关任务分解及描述分解所得子任务之间关系的方法。这些研究从不同角度和层面给出子任务分解和描述方法，但多数方法仅从宏观理论上给出了相关定义和说明，较难直接应用于实际计算机辅助手段中，而基于自动组合的直接搜索法可有效解决此类问题。直接搜索法是根据具体应用的需求将任务求解问题表示为特定问题状态空间，相当于是实现了一个特定用途的规划器，然后选择适合的搜索算法直接搜索目标状态，在搜索过程中生成模型组装方案[3]。目前，采用直接搜索法进行自动组合的方法有很多种，如文献[11—13]将其应用于服务自动组合中，该方法被认为是目前最为有效的自动组合方法之一。如文献[14]中所述，在传统的人工智能中，与或图搜索是处理空间搜索问题的一个重要的工具，且具有形式化表示简单、实施容易的特点。因此，本文提出一种基于与或图[15]的复杂决策任务求解方法，此方法将决策任务分解为更小的子任务、原子任务，并通过与、或等构造算子支持决策模型有效组装，并使用启发式算法搜索以找到最优、无矛盾解图，设计执行构造子等支持解图到执行工作流的转换，以及基于启发式函数的与或图搜索支持有效的任务分解以及优化选择。

本文以下内容首先讲述任务决策原则，以支持有效启发式任务分解；其次，给出相应的执行构造子定义，以支持与或图任务到可执行工作流的转换；然后给出基于与或图的启发式决策任务分解方法，并给出决策任务分集算法执行步骤；最后通过一个案例进行证明。

2 火力打击的决策原则（Decision principle of fire

against）

任务的定义具有两层含义：首先任务的本质是工作，即一组实际的行动，任务的实施者执行这些行动以完成任务；其次任务必须有特定目标，没有目标的行为不能称为任务。任务规划过程是通过任务分解和解决威胁（或冲突）来进行的。基本的规划步骤是递归地将任务网络中的复合任务分解成越来越小（即粒度越来越细）的子任务，并在分解过程中进行检查和解决，直到出现那些可以直接执行规划动作就能完成的原子任务为止[16]。

火力分配是在军事指挥中常见的决策任务之一，指用弹炮结合系统抗击多个敌方目标时，合理进行火力分配以有效打击目标，消除敌方威胁。目标分配原则使火力单元对目标的毁伤效能达到最大（或者某种目标效果，如干扰），并且已方人员和装备发挥诸火力单元的整体协调优势，寻求对敌方最大的打击效果并最大限度地降低已方部队消耗。在此原则下，目标的最优分配应该考虑以下几点：（1）武器单位特点，包括武器系统类别（如防空导弹）、型号、数量、位置、对各种目标的毁伤效能以及弹药用量等。（2）目标特点，主要有目标的类型、数量、运动特征、价值、威胁程度、易损性以及目标的集合特性等。（3）最优准则，对目标的毁伤程度要大、所用的武器单元数目和弹药的消耗要小等[17]。

3 基于与或图的启发式任务决策（Heuristic task

decision based on And/Or graph）

任务规划可以很方便地使用一个与或图结构来表示，主要包含两类节点类型：（1）与节点，将单个问题变为多个子问题组成的结合，这是所有当所有子问题都有解时，则该父辈节点有解。（2）或节点，几个方法同时适用于同一问题，从而产生不同的后继问题节点，此时当其中任意子问题节点有解时，其父辈节点问题可解。

任务规划问题可规约描述为一个与或图的分解过程，原始任务目标对应于起始节点（根节点），任务分解方案所对应的节点成为叶节点（已存在的可解子任务集）。在与或图上执行搜索过程，相当于完成任务由复杂任务逐级细化到子任务、原子任务的过程。值得注意的是，此过程的目标在于表示起始节点是有解的，即搜索的过程是寻找一个解图。

在搜索解图的过程中，需要进行节点耗散值的计算。设节点连接符的耗散值规定为：k-连接符的耗散值=k，则解图的耗散值记为k（n，N），则可以递归计算如下[18]：

a：若n是N的一个元素，则k（n，N）=0；

b：若n有一个外向连接符指向后继节点（n1，n2，...，nk），并设该连接符的耗散值为Cn，则：

K（n，N）=Cn+k（n1，N1）+......+k（ni，Ni）

具有最小耗散值的解图为最佳解图。本文讨论使用评价函数支持与或图的启发式搜索，实现复杂决策任务的有效解获取。

搜索过程中需要标记能解节点（SOLVED），为此需要给出如下定义[18]：

（1）能解节点（SOLVED）

a：终结点是能解节点。

b：若非终结点，有“或”子节点时，当且仅当其子节点中至少一个能解，该非终结点才能解。

c：若非终节点有“与”子节点时，当且仅当其子节点均能解，该非终结点才能解。

（2）不能解节点（UNSOLVED）

a：没有后裔的非终结点是不能解节点。

b：若非终结点有“或”子节点时，当且仅当所有子节点均不能解时，该非终结点才不能解。

c：若非终结点有“与”子节点时，当至少有一子节点不能解时，该非终结点才不能解。

4 使用与或图的决策任务分解（Task decomposition

by And/Or graph）

规划过程是通过任务分解和解决威胁（或冲突）来进行的。本章将扩展与或图连接符类型以支持所形成任务分解图的可执行性，并解释如何采用基于与或图的启发式函数进行高效的任务规划。

4.1 执行构造子

经典与或图中仅包含与、或节点两种类型，对于与或图的可执行力描述不足。因此，本文参照当前规划组合的执行集合：Sequence，Unordered，Choice，Switch，If-Then，Split and Split+Join[19]，扩展定义了四种类型的可执行节点：AND节点，OR节点，SEQUENCE-AND节点，SWITCH-OR节点。其中，AND节点和OR节点的定义与前面与或图中的定义一样。SEQUENCE-AND节点是AND节点的一种，使用 表示。SWITCH-OR节点是OR节点的一种，使用 表示。每一个执行节点代表一种执行步骤，其具体的含义如下[20]：

（1）AND节点表示Split执行，即从左到右顺序执行。边表示满足所需的输入集是其它任务输出集的子集。

（2）SEQUENCE-AND节点表示Split+Join执行。

（3）OR节点表示Choice执行。OR节点的子节点从左到右是同等的[21]。

（4）SWITCH-OR节点表示Switch执行，表示只能选择一个子节点。

（5）路径表示自下而上序列Sequence执行。

（6）不同的路径默认表示无序，除非遇到SEQUENCE-AND节点。

（7）图的边表示If-Then条件执行，即所需的输入集是其它任务的输出集的子集。当输出为空时为空（NULL）时，执行器将停止。

执行节点与对应的执行集合组合的执行结构如图1所示。

图1 执行结构

Fig.1 Execute structure

4.2 基于与或图的启发式任务规划

定义由原子任务和组合任务构成的状态空间，包括开始状态、目标状态和推理规则（组合操作）。决策任务分解图搜索过程如下[20]：

开始状态：

a.一系列具有不同状态空间的决策任务作为本地可用节点。

b.一个单一的START节点，包含任务的输出，代表用户需求。

c.一系列有限TERMINAL节点，包含任务的输入，代表目前可用的用户输入。

结果：一个优化的组合任务图作为解。

任务分解：

决策任务分解算法执行以下步骤，完成启发式搜索与转换为可执行工作流：

（1）本文给出的任务分解算法如下：

a.自上而下的扩展操作以寻找潜在解图，此过程可包括基于有向边的可连接性和相似性进行权重评价，直到任务的输入是一个存在TERMINAL节点的子集。如果权重值低于某特定值或节点是NONTERMINAL节点，则此节点应不被扩展。

b.自下而上的成本（路径权重）修改操作，从而更新节点的权重值，以找到具有低成本的最优解图。

（2）转换可执行工作流：一个搜索状态代表了一系列可执行步骤，此步骤从TERMINAL节点开始到START节点并满足决策模型组装要求。从解图转换到可执行工作流的执行主要依据上节给出的构造子的执行定义。

启发式任务规划利用所处理问题的启发信息引导规划，因此需给出相应的评价函数。利用启发信息定义一个评价函数f对待扩展的节点计算，可表述为f（n）=g（n）+h（n），表示即考虑起始节点到节点n的消耗，也考虑从节点n到达目标的消耗，利用此评价函数可完成节点优先扩展的选择。启发式函数的启发能力越强，规划效果越好，规划效率也越高。在火力决策等任务规划过程中，启发式函数可通过第一章中考虑的目标分配影响因素进行评价，如武器系统数量、目标易损程度、目标的毁伤程度和弹药消耗等，以决定扩展节点的消耗值。

参照启发式函数给出的消耗值，基于本文给出的启发式搜索算法进行任务规划的步骤截图，图2给出一个具体的例子。A表示了当前任务分解的START节点，它可由（B与E）组合任务，或F、或H三个子任务完成。可解任务集为当前可用任务，包括D1、D2、G2、H等以一些列原子任务。通过对三个子任务的计算，发现第一个子任务的耗散值最小，因此优先扩展B节点至C、D1、D2子节点，并同步依据子节点的耗散值反向修改父节点的耗散值，以判定下一步扩展指针的方向。最终将形成由（D1，D2，E，G1，G2）组成的TERMINAL节点。此过程反复进行，通过不断的自上到下的评价函数计算以及自下到上的消耗值计算，判定优先扩展节点，以进一步执行节点搜索分解。在分解过程中，参照解节点（SOLVED）和不解节点（UNSOLVED）的定义进行节点标记，当某节点被标记为不能解节点时，则将其从与或图中删除。

图2 启发式任务决策

Fig.2 A heuristic task decision

5 火力打击决策任务分解（Task decomposition of

fire fighting）

我们以一个战术级联合火力打击的情景作为例子。具体情景表现为：一个连执行战备任务时发现不明入侵物体并快速启动火力打击任务决策规划程序，要求在明确具体打击目标的基础上，进行区分打击任务、确定打击顺序、打击效果评估等过程规划。由于连级任务规划需要将任务具体下发到营级打击任务，因此必须满足：首先，明确目标类型，获取目标轨迹信息；其次，将任务分解到具体营级任务；然后，由于营级火力打击任务由各武器系统（近、远程）联合执行打击任务，因此需要将其分解到具体武器系统打击子任务，如近程防御系统准备；而后，武器系统打击任务将由具体的计算弹道条件等原子任务组成；最后，通过调用弹药消耗量等进行综合评价。同时，还存在用户交互需求，如指挥员依据战斗经验进行武器系统选择。本节将通过以上联合火力打击任务为例对任务分解的自动构建和可执行任务工作流转换进行实验，如图3所示。

开始状态：

（1）连级火力打击所需输出，即武器系统打击结果，成功或失败。

（2）连级火力打击的已知输入，即某不明飞行物体位置信息。

（3）一个USER PREFERENCE任务节点，输入为武器列表，输出为一个武器系统编号。

搜索结果：一个解图，如图3所示。

图3 连级联合火力打击任务工作流

Fig.3 The task workflow of company joint

firepower strike

规划执行：

（1）首先，规划器发现为不存在可直接使用的连火力打击的任务，因此进行任务分解。

（2）规划器扩展START节点到一营武器系统打击节点和二营武器系统打击节点，并标记START节点为OR节点。

（3）规划器扩展一营武器系统打击节点到远程打击系统A和近程打击系统A节点，并标记一营武器系统打击节点为Sequence-And节点，其中近程打击系统启动条件为远程打击系统的执行结果。

（4）规划器扩展二营武器系统打击节点到近程打击系统B节点，由于近程打击系统启动条件为远程打击系统的执行结果，因此修改START节点为Sequence-And节点。

（5）规划器扩展所有系统节点到初始条件，即输入飞行物位置。

联合火力打击任务是一个满足决策任务要求的任务集的工作流。执行程序由具体的输入值激活。执行步骤如下：远程打击系统A得到打击目标-不明飞行物位置并输出打击结果。同时近程打击系统A获得飞行物位置并以SEQUENCE-AND节点模式等待远程打击系统A执行结果的唤醒，并返回结果到一营武器系统打击任务节点。同时，执行器收集各任务的输出，包括远程打击结果并激活了近程打击系统B节点。最终给出相应的打击结果，执行完毕。

6 结论（Conclusion）

与或图搜索技术可以用于处理复杂决策任务分解问题，它支持将任务分解成较小的与、或子任务直到所有的任务是

可解的，对应任务由下一层子任务或原子任务组成。执行此操作过程的空间搜索得到一个使初始状态满足的解图，并根据其生成一个可执行线性工作流。本文给出一个决策任务求解方法，解决了决策方案自动产生问题，可有效降低决策计划制定时间，但有关多个决策方案综合比较、决策者个人偏好、影响、决策经验等对于整个决策过程也有很大的影响，需要进一步加强研究。此外，有关将决策任务与领域本体结合，以实现更智能的决策推理过程等体系，有待进一步研究。

参考文献（References）

[1] 李策.陆军合同作战指挥决策过程建模[J].计算机仿真，2009， 24（7）：163-169.

[2] 吴昕晟，萧毅鸿.基于方案本体的决策模型组装[J].计算机与 现代化，2009，12：249-253.

[3] 萧毅鸿.基于本体的复杂决策任务表示方法与求解技术研究 [D].南京大学，2007.

[4] 曹裕华，冯书兴，徐雪峰.作战任务分解的概念表示方法研究 [J].计算机仿真，2007，24（8）：1-4.

[5] 庞辉，方宗德.网络化协作任务分解策略和粒度设计[J].计算 机集成制造系统，2008，14（3）：425-430.

[6] VANDE，SALOMONM.Production plaxining and inventory control with remanufacturing and disposal[J].European Journal of Operational Research，1997，102（2）：264-278.

[7] 邓家提.产品设计的基本理论与技术[J].中国机械工程，2000， 11（1/2）：139-143.

[8] CHENSJ，LINL.Decoma position of inter dependent task group for eon current engineering[J].Computer & Industrial engineering.2003， 44（3）：435-459.

[9] 刘秀罗.建模相关技术及其在指挥控制建模中的应用研究 [D].国防科技大学，2001.

[10] 曹裕华.面向实体的作战建模方法[D].军事科学院，200

[11] Lecue F，Leger A.A Formal Model for Semantic Web Service Composition[C].In：Proceedings of the 5th International Semantic Web Conference.Springer，LNCS 4273，2006：385-398.

[12] 邓水光，等.基于回溯树的web服务自动组合[J].软件学报， 2007，18（8）：189-1910.

[13] 温嘉佳，陈俊亮，彭泳.基于目标距离评估的启发式WebServiees 组合算法[J].软件学报，2007，18（l）：85-93.

[14] Xining Li，Wei Fan.An object-oriented And/Or graph inference engine Electrical and Computer Engineering. Canadian Conference on 14-17 Sept.1993.

[15] Ching-Fang Liaw，etc.Multiobjective Heuristic Search in AND/OR Grapes. Proceeding of IEEE transactions on systems，man，and cybernetics，vol.25， November 1995.

[16] 萧毅鸿，周献中，张铁.扩展层级任务网络规划的变粒度作战 任务分解策略[J].火力与指挥控制，2011，7（4）：119-122.

[17] 王小艺，等.防空武器多目标优化分配建模与决策[J].兵工学 报，2007，28（2）：228-231.

[18] 林尧瑞，马少平.人工智能导论[M].北京：清华大学出版社， 2002：158-160.

[19] Evren Sirin，ect. HTN planning for web service composition using SHOP2 [J].Journal of Web Semantics， 2004， 1（4）：377-396.

[20] 贾慧彤.面向偏差问题的语义Web服务 [D].北京工业大学计 算机系，2009.

[21] Milanovic N，Malek M.Architectural support for automatic service composition[C].In：Proceeding of the IEEE International Conference.On Service computing （SCC 2005）.

Orlando：IEEE，2005，133-140.

作者简介：

贾慧彤（1982-），女，硕士，工程师.研究领域：人工智能，

决策分析.