复杂决策任务层级分解动态控制策略与算法

黄孝鹏 周献中

(1.中船重工第七二四研究所 系统总体部，江苏 南京210003;2.南京大学 控制与系统工程系，江苏 南京210093)

1 引言

在复杂决策任务求解流程中，对决策任务进行合理、有序地分解，有助于深入理解问题，简化问题结构，降低全局计算代价，实现快速有效求解。目前，国内外文献中常见的任务分解方法主要是针对工作流意义下的任务分解，或假定任务已经分解完毕而直接进行任务匹配等［1-4］。在这些从不同角度、层面提出的任务分解方法中，有的是根据个人经验、行为偏好、知识结构、态势感知与理解等由决策者进行任务分解;有的是通过多智能体(Multi-Agent)、数学规划、模式识别等技术由计算机动态、自动地进行任务分解。但这些分解方法多为笼统地讨论某种分解方法，以求适用于所有的决策问题，实践中并不全都可行。在实际应用中，针对结构化决策问题，其求解过程可不需要人的参与，故可实现其分解过程的完全自动化、程序化;但针对半(非)结构化决策问题，其求解过程必须要有人的参与，特别是人的感知、判断、推理、综合、创造、直觉等能力的参与，故对这类决策问题的分解不能实现完全自动化、程序化。

针对决策任务分解，以任务求解为驱动，综合考虑求解主体(参与决策活动的人件和计算机软件)的求解能力和决策任务的结构特征等因素对决策任务进行层级分解，可为决策任务流程规划与设计提供理论支撑，也是对传统决策任务分解模式提出的新挑战。

2 基本思想

图1 决策任务分解

决策任务层级分解的基本思想是综合考虑决策任务的结构特征、环境约束、分解方式、求解主体的求解能力以及子任务间的联系等因素，以任务求解为驱动把总体任务细化成若干具体的、层次清晰明确的、相互独立的(同层子任务间无直接消息传递)、易执行的子任务，且上一层次的子任务对下一层次的全部或某些子任务起着支配作用，最后经综合整理得到一种递阶的树状层级结构，如图1所示。这往往也是决策者最想获得的结果。

3 相关概念

3.1 决策任务分解相关概念

定义1:决策任务(Decision Task，DT)。决策任务是指依据可实现的途径或具体的可实现方法来实现特定决策目标所需完成的工作。

为便于研究，把决策任务的主要特征形式化表示为一个七元组，即:

其中DId、DN、DG、DC分别表示决策任务的标识符、名称、目标与环境约束;DK是决策任务的知识集(包括任务的初始条件和中间结果)，其中DG也包括完成任务所必须得到的知识;DA是操作集(接收相应的输入，经过信息处理产生输出，通过操作完成任务);DT表示时间约束，DT=［Ts，Te］，Ts≤Te，以满足快速(敏捷)决策的时间要求。

定义2:子任务(Subtask，ST)。子任务是由决策任务按某种规则(时间属性、空间属性、主体属性和客体属性等)分解后得到的任务序列。所有子任务操作集的输出并集必须覆盖目标集且不同的子任务间是独立的，即:STi={STi|STi=DT，Ordi}(其中Ordi为子任务间的与、或、循环等次序)，且STi∩STj≠∅(i≠j)。可形式化描述为:

其中STId，STN，STG，STC，STK，STA，STT分别表示子任务STi的标识符、名称、目标、环境约束、知识集、操作集和时间约束。

定义3:任务分解(Task Decomposition，TD)。对于决策任务DT，若∃DT'={ST'1，ST'2，…，ST'n}，为DT在某特定规则作用下的一个覆盖;若∃DT'=ST'i}=DT，则称DT'为DT在某特定规则作用下的一个任务分解。当然，分解后得到的子任务集应具备完整性、独立性、可解性、协调性等特性。

3.2 人件相关概念

定义4:人件(Humanware，Hw)。人件是指参与决策活动的人。它可以是最终的决策者，也可以是在决策任务求解过程中提供信息支持、功能支持或算法支持的各类人员［5］。

“人件”是从决策角度出发研究参与决策活动的人，是相对于承担决策任务求解功能的软件而提出的概念，也是针对新型决策系统中人机高效协作问题所提出的概念。

定义5:人件服务(Humanware Service，HwS)。人件作为决策系统组成要素时，其特定功能(如决策功能等)的网络赋能形态就是人件服务。其形式化描述如下:

其 中，Id，Name，Category，Function，Inputs，Outputs，QoS分别为人件服务的标识、名称、类别、功能描述、输入、输出、服务质量。

同理，软件服务(Software Service，SwS)可形式化描述为:

当然，软件服务SwSi和人件服务HwSj之间是可组态的，其服务组合CSk的基本控制结构有串行、并行、选择及循环等四种。针对某子任务求解，在服务调用选择时先调用SwS，经判断，如不能达到使命任务求解的目标，再调用高级服务HwS。若针对某粗粒度的子任务，也可能会将HwS和SwS两者进行组合封装，然后调用。

4 原则与目标

4.1 原则

根据决策任务的自身结构与特征、环境、人件服务与软件服务的求解能力，提出以下任务分解原则:①层次性，指决策任务先可划分为若干子任务，子任务按其结构与特征决定是否进行再划分，形成层级结构，使复杂决策任务分解为多个相对简单的、易于处理的子任务。②弱耦合，分解后的子任务间关联度要尽可能小。③组合性，子任务的适当组合能构成一个较粗粒度的任务。④均衡性，指同层次上的任务粒度、规模、求解难易程度要尽量均衡，以避免某一任务求解开销过大，导致求解主体任务负载量不均衡，影响整体求解效率。

4.2 目标

任务分解的目标是按照某种规则，设计一种为实现决策任务快速、高效求解且能符合决策者认知特征的最佳分解。设DT按照某种规则P分解的最终结果为(ST'1，ST'2，…，ST'n)，若最终子任务ST'i的分解开销(时间、成本等)函数为C(ST'i)(i=1，2，…，n)，则任务分解的目标为在规则P作用下的总体代价函数值最优且不超过限定值C，即:

4.3 相关定理及规则

定理1:决策任务分解后子任务的解空间也是原决策任务的解空间。

规则1:任务一致化规则。主要解决在任务分解过程中产生的上下级任务的不一致和冲突等问题，主要包括任务剪枝规则、继承规则和冲突规则等。这些规则都存放在任务分解库中，供创建任务分解树时提取和使用。

(1)任务剪枝规则。主要针对子任务间的“或”关系，根据公式(1)计算出每个分支的开销，保留最小开销分支，去除其他分支并删除该“或”分支的根节点以得到最优分解，此时上级任务也需添加其没有的下级任务属性来保证一致性。

针对任务分解树的某个存在“或”关系的分支，依据剪枝规则，设计剪枝算法J如下:

Step1:如子任务间是“或”关系;

Step2:计算各子任务的求解开销，选出最小求解开销节点;

Step3:删除其他子任务节点，将分支根节点的标号改为最小求解开销节点标号，结束。

(2)任务冲突规则。如果下级任务和上级任务存在属性冲突，为保持一致性，可以下级任务属性为基础，约减上级冲突的任务属性(向上冲突消解策略);或以上级任务属性为基础，约减下级冲突的任务属性(向下冲突消解策略)。

(3)任务继承规则。在构造任务分解树的过程中，新分解的下级子任务继承上级子任务的权限。

4.4 特殊约束

在某特定领域(如军队作战指挥决策领域等)，针对某些特定的使命任务，由于不同参战单元的作战业务能力是不同的，在进行任务分解时存在以下两个约束，需予以考虑。

规则2:肯定约束。如:Must_Do(HSi，STj)表示子任务STj必须由HSi来执行。

规则3:否定约束。如:Cannot_Do(HSi，STj)表示子任务STj不能由HSi来执行。

5 策 略

根据任务分解的基本思想、概念体系、原则和目标、定理及所设定的相关规则等，综合考虑决策任务的结构特征、环境、人件服务和软件服务的求解能力等因素，研究基于人件服务的复杂决策任务层级分解策略，需有一套充分利用软件服务和人件服务各自优势的协同策略，达到人与计算机之间的求解均衡，既不增加人的负担，又可以让人充分相信整个决策任务求解流程的合理性和正确性。

设定任务分解需满足以下条件和约束:①对任一决策任务，至少存在一个对应的任务分解结果。②每次只有一个子任务参与服务库的匹配。③每个服务(包括人件服务和软件服务的服务组合CSk)每次只参与一个子任务的匹配。④服务库里供给的服务不小于子任务的服务需求。为研究方便，设置任务分解计数器以统计任务最终分解结果的规模，它包括层数计数器M和最终子任务个数计数器N，初始值令M=1，N=1。

5.1 任务分割点寻求算法

设决策任务共有k个操作，从k个操作中选出可把任务初始信息作为输入信息的操作，组成操作集DA，DA包含的操作数即任务分解的可能路径的个数。输入信息是指初始任务A、任务的初始条件和目标;输出结果是指分解的子任务集、各子任务的输入信息和输出信息。

任务分割点寻求的启发式算法F表示如下:

Step1:设定初始任务节点A，进行赋值，转Step2。

Step2:若操作i的输入信息等于任务初始信息，k++，转Step3;否则转Step4。

Step3:令Actions等于操作i，若当前所有信息等于任务DG的所需全部信息时，在Actions中寻找一组操作覆盖任务目标集DG的操作集，得到可行操作集，运用剪枝算法J求最优，break，转Step4。

Step4:算法停止。

5.2 任务分解算法

针对需由软件服务、人件服务、人件服务与软件服务的组合来完成的复杂决策任务，其任务分解算法A如下:

Step1:设DT为一个决策任务。

Step2:根据算法F得到DT的初始分解，DT={ST1，ST2，…，STn}，M++。

Step3:从i=1开始，判断STi与软件服务库中服务能否匹配，如匹配，则将其存储到缓冲库中，记录每次匹配成功的子任务个数Ai，N1=ΣAi，1≤i＜n，转Step4;否则转Step5。

Step4:判断i=n是否成立，如成立，则转Step8;否则i++，转Step3。

Step5:判断与人件服务库能否相匹配，如匹配，则将其存储到缓冲库中，记录每次匹配成功的子任务个数Aj，N2=ΣAj，1≤j＜m，转Step4;否则转Step6。

Step6:判断与人件服务和软件服务的组合服务能否相匹配，如匹配，则将其存储到缓冲库中，记录每次匹配成功的子任务个数Ak，N3=ΣAk，1≤k＜q，转Step4;否则转Step7。

Step7:将不能匹配的子任务，根据算法F进行再分解。令STi={ST'ij}，M++，调用自身算法A，判断是否完全匹配成功，如果能完全匹配，转Step4;否则继续Step7。当某子任务被执行次数超过Z(Z为正整数，可根据问题规模大小设定)次时，需调整分解策略，继续Step7，判断是否完全匹配成功，如果能完全匹配，转Step4，以避免算法中可能会出现的“死循环”。

Step8:任务分解结束，将结果进行综合整理，输出任务分解树M及N=N1+N2+N3的值。

任务分解算法流程如图2所示。

在算法执行过程中，最好的情况是一次分解就能完全匹配，算法复杂性为O(N);最坏的情况是每个子任务均不能和软件服务、人件服务匹配，算法复杂性为O(M×N)。

图2 任务分解算法流程

6 应用

以时敏目标(Time Sensitive Target，TST)打击为背景构建应用想定，运用本文的研究结果给出某TST打击的任务分解，为设计TST快速打击流程提供一种科学依据。TST打击是一项复杂任务，可划分为发现目标、识别目标、跟踪目标、快速制定决策方案、交战和效果评估等六个子任务，同时每个子任务也是一个复合任务，需要对其做进一步的分解以设计TST快速打击流程。运用研究结果，得到某TST快速打击的最终任务分解如图3所示，其中M=4，N=18，目标识别、确定有效打击时间、态势评估、武器选择、打击方案生成、打击方案预评估、确定打击方案等任务可由人来完成。

1 KAIVAN KAMALI，DAN VENTURA，AMULYA GARGA，etc.Geometric task decomposition in a multi-agent environment［J］.Applied Artificial Intelligence，2006，20(5):437-456.

2 DYLAN ALEXANDER SIMON，NATHANIEL DDAW.Neural correlates of forward planning in a spatial decision task in humans［J］.The Journal of Neuroscience，2011，31(14):5526-5539.

3 JIANG CHUNFENG，ZHAO YULAN.Task decomposition and allocation in tactical team based on layered agent［C］//International Conference on Electronic＆Mechanical Engineering and Information Technology(EMEIT)，2011:1942-1944.

4 CHEN JIANPING，YANG YIMIN，WEI LIANG.Research on the approach of task decomposition in soccer robot system［C］//2010 International Conference on Digital Manufacturing＆Automation(ICDMA)，2010:284-289.

5 黄孝鹏，周献中，杨洁，等.人机协同决策系统中人件及人件服务的概念体系研究［C］//中国系统工程学会第十七届学术年会，2012.

6 石纯一，张伟.基于Agent的计算［M］.北京:清华大学出版社，2007.

7 KIM YE HOON，CHO SE HYOUNG，CHOI SEUNG HWAN，etc.Software robot in a PDA for human interaction and seamless service［C］//The 16th IEEE International Conference on Robot＆Human Interactive Communication，2007:968-973.

8 AGRAWAL A，AMEND M，DAS M，etc.W S-BPEL extension for people version 1.0［EB/OL］.(2007)［2010-04-10］.http://www.ibm.com/developer works/web services/library/specification/ws-bpel4people.

9 黄孝鹏，周献中，田卫萍.基于人件服务的人机协同决策系统有关问题研究［C］//第三届C4ISR技术论坛，2011.

10 黄孝鹏，周献中，陆晓明，等.从“以人为本”角度理解和认识决策系统演化趋势——兼谈人机协同决策系统的构建［J］.系统科学学报，2013(1):35-39.

11 曾广平，涂序彦，王洪泊.“软件人”研究及应用［M］.北京:科学出版社，2007.