人工智能基础：任务级行动序列问题中的定性偏好研究

第9卷第5期 智能系统学报 Vol.9 No.5 2014年10月 CAAI Transactions on Intelligent Systems 0ct.2014 D0:10.3969/j.issn.1673-4785.201306013 任务级行动序列问题中的定性偏好研究 王炎娟2，姚莉，刘斌 (1.国防科技大学信息系统工程重点实验室，湖南长沙410073：2.北京航天飞行控制中心，北京100094) 摘要：关注了一类典型行动序列，研究如何在动作集合上存在定性偏好，且偏好集合存在不一致性时开展规划。 所考虑的行动序列问题称为任务级C0A,以抽象层次的动作为基本要素，所考虑的定性偏好包括静态偏好和时序偏 好，所讨论的规划目的是获得最大满意度的COA方案。首先建立了偏好与约束的归一化形式描述，在此基础上形成 了COA方案设计算法：进一步，使用计算辩论技术排除偏好集合中的不一致性，形成用户接受度最高的COA方案。 文中建立的以定性推理为基础的规划框架，实现了偏好解耦，能够适应不同的领域问题，是以定量计算为基础的传 统规划算法的有效补充。通过快速响应卫星成像的COA案例，演示了算法的可行性。 关键词：行动序列：规划；定性偏好：时序偏好；计算辩论技术；偏好解耦 中图分类号：TP391文献标志码：A文章编号：1673-4785(2014)05-0551-09 中文引用格式：王炎娟，姚莉，刘斌.任务级行动序列问题中的定性偏好研究[J].智能系统学报，2014,9(5)：551-559. 英文引用格式：WANG Yanjuan,,YAOi,LIU Bin.Research on qualitative preference in planning of task--level Course-of-action [J].CAAI Transactions on Intelligent Systems,2014,9(5):551-559. Research on qualitative preference in planning of task-level Course-of-action WANG Yanjuan'2,YAO Li',LIU Bin' (1.Science and Technology on Information Systems Engineering Laboratory,National University of Defense Technology,Changsha 410073 China;2.Beijing Aerospace Control Center,Beijing 100094,China) Abstract:This paper focuses on a special type of course-of-action.Specifically,performing study on planning with the existence of qualitative preferences and functions on the actions and owns the inner inconsistence.The course- of-action that is taken into consideration is called 'task-level'course-of-action(COA),with abstracted action as basic element.The qualitative preferences in discussion include static preferences and temporal preference.The ob- jective of planning is a COA plan with satisfaction.Firstly,a unified formulated description is established for con- straints and preferences,based on which an algorithm for COA planning is developed.Furthermore,computational argumentation is utilized to exclude inconsistence in the set of preferences,to maximize the user's satisfaction for COA planning.The planning framework based on qualitative deduction is an effective add-in for conventional plan- ning scheme based on quantitative computation.The property of preference-decoupling makes itself adaptable to ap- plications in different domain.A case study on scheduling responsive imaging satellites is proposed to demonstrate the effectiveness of the scheme. Keywords:course-of-action;planning;qualitative preference;temporal preference;computational argumentation; preference decoupling 行动序列(C0A)问题来自军事学领域，由于其 收稿日期：2013-06-10. 基金项目：.国家自然科学基金资助项目(70971134) 关于时间、动作等基本概念和问题结构与调度、规划 通信作者：王炎娟.E-mail:.nudtwyj@gmail.com 有着众多相通之处，已经得到了人工智能领域研究

第 ９ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．９ №．５ ２０１４ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１４ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１３０６０１３ 任务级行动序列问题中的定性偏好研究 王炎娟１，２ ，姚莉１ ，刘斌１ （１．国防科技大学 信息系统工程重点实验室，湖南 长沙 ４１００７３； ２． 北京航天飞行控制中心，北京 １０００９４） 摘 要：关注了一类典型行动序列，研究如何在动作集合上存在定性偏好，且偏好集合存在不一致性时开展规划。 所考虑的行动序列问题称为任务级 ＣＯＡ，以抽象层次的动作为基本要素，所考虑的定性偏好包括静态偏好和时序偏 好，所讨论的规划目的是获得最大满意度的 ＣＯＡ 方案。 首先建立了偏好与约束的归一化形式描述，在此基础上形成 了 ＣＯＡ 方案设计算法；进一步，使用计算辩论技术排除偏好集合中的不一致性，形成用户接受度最高的 ＣＯＡ 方案。 文中建立的以定性推理为基础的规划框架，实现了偏好解耦，能够适应不同的领域问题，是以定量计算为基础的传 统规划算法的有效补充。 通过快速响应卫星成像的 ＣＯＡ 案例，演示了算法的可行性。 关键词：行动序列；规划；定性偏好；时序偏好；计算辩论技术；偏好解耦 中图分类号： ＴＰ３９１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１４）０５⁃０５５１⁃０９ 中文引用格式：王炎娟，姚莉，刘斌． 任务级行动序列问题中的定性偏好研究［Ｊ］． 智能系统学报， ２０１４， ９（５）： ５５１⁃５５９． 英文引用格式：ＷＡＮＧ Ｙａｎｊｕａｎ， ＹＡＯ Ｌｉ， ＬＩＵ Ｂｉｎ． Ｒｅｓｅａｒｃｈ ｏｎ ｑｕａｌｉｔａｔｉｖｅ ｐｒｅｆｅｒｅｎｃｅ ｉｎ ｐｌａｎｎｉｎｇ ｏｆ ｔａｓｋ⁃ｌｅｖｅｌ Ｃｏｕｒｓｅ⁃ｏｆ⁃ａｃｔｉｏｎ ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１４， ９（５）： ５５１⁃５５９． Ｒｅｓｅａｒｃｈ ｏｎ ｑｕａｌｉｔａｔｉｖｅ ｐｒｅｆｅｒｅｎｃｅ ｉｎ ｐｌａｎｎｉｎｇ ｏｆ ｔａｓｋ⁃ｌｅｖｅｌ Ｃｏｕｒｓｅ⁃ｏｆ⁃ａｃｔｉｏｎ ＷＡＮＧ Ｙａｎｊｕａｎ １ ， ２ ， ＹＡＯ Ｌｉ １ ， ＬＩＵ Ｂｉｎ １ （１． Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ Ｌａｂｏｒａｔｏｒｙ， Ｎａｔｉｏｎａｌ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｄｅｆｅｎｓｅ Ｔｅｃｈｎｏｌｏｇｙ， Ｃｈａｎｇｓｈａ ４１００７３ Ｃｈｉｎａ； ２． Ｂｅｉｊｉｎｇ Ａｅｒｏｓｐａｃｅ Ｃｏｎｔｒｏｌ Ｃｅｎｔｅｒ， Ｂｅｉｊｉｎｇ １０００９４， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｆｏｃｕｓｅｓ ｏｎ ａ ｓｐｅｃｉａｌ ｔｙｐｅ ｏｆ ｃｏｕｒｓｅ⁃ｏｆ⁃ａｃｔｉｏｎ． Ｓｐｅｃｉｆｉｃａｌｌｙ， ｐｅｒｆｏｒｍｉｎｇ ｓｔｕｄｙ ｏｎ ｐｌａｎｎｉｎｇ ｗｉｔｈ ｔｈｅ ｅｘｉｓｔｅｎｃｅ ｏｆ ｑｕａｌｉｔａｔｉｖｅ ｐｒｅｆｅｒｅｎｃｅｓ ａｎｄ ｆｕｎｃｔｉｏｎｓ ｏｎ ｔｈｅ ａｃｔｉｏｎｓ ａｎｄ ｏｗｎｓ ｔｈｅ ｉｎｎｅｒ ｉｎｃｏｎｓｉｓｔｅｎｃｅ． Ｔｈｅ ｃｏｕｒｓｅ⁃ ｏｆ⁃ａｃｔｉｏｎ ｔｈａｔ ｉｓ ｔａｋｅｎ ｉｎｔｏ ｃｏｎｓｉｄｅｒａｔｉｏｎ ｉｓ ｃａｌｌｅｄ ‘ｔａｓｋ⁃ｌｅｖｅｌ’ ｃｏｕｒｓｅ⁃ｏｆ⁃ａｃｔｉｏｎ（ＣＯＡ）， ｗｉｔｈ ａｂｓｔｒａｃｔｅｄ ａｃｔｉｏｎ ａｓ ｂａｓｉｃ ｅｌｅｍｅｎｔ． Ｔｈｅ ｑｕａｌｉｔａｔｉｖｅ ｐｒｅｆｅｒｅｎｃｅｓ ｉｎ ｄｉｓｃｕｓｓｉｏｎ ｉｎｃｌｕｄｅ ｓｔａｔｉｃ ｐｒｅｆｅｒｅｎｃｅｓ ａｎｄ ｔｅｍｐｏｒａｌ ｐｒｅｆｅｒｅｎｃｅ． Ｔｈｅ ｏｂ⁃ ｊｅｃｔｉｖｅ ｏｆ ｐｌａｎｎｉｎｇ ｉｓ ａ ＣＯＡ ｐｌａｎ ｗｉｔｈ ｓａｔｉｓｆａｃｔｉｏｎ． Ｆｉｒｓｔｌｙ， ａ ｕｎｉｆｉｅｄ ｆｏｒｍｕｌａｔｅｄ ｄｅｓｃｒｉｐｔｉｏｎ ｉｓ ｅｓｔａｂｌｉｓｈｅｄ ｆｏｒ ｃｏｎ⁃ ｓｔｒａｉｎｔｓ ａｎｄ ｐｒｅｆｅｒｅｎｃｅｓ， ｂａｓｅｄ ｏｎ ｗｈｉｃｈ ａｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ＣＯＡ ｐｌａｎｎｉｎｇ ｉｓ ｄｅｖｅｌｏｐｅｄ． Ｆｕｒｔｈｅｒｍｏｒｅ， ｃｏｍｐｕｔａｔｉｏｎａｌ ａｒｇｕｍｅｎｔａｔｉｏｎ ｉｓ ｕｔｉｌｉｚｅｄ ｔｏ ｅｘｃｌｕｄｅ ｉｎｃｏｎｓｉｓｔｅｎｃｅ ｉｎ ｔｈｅ ｓｅｔ ｏｆ ｐｒｅｆｅｒｅｎｃｅｓ， ｔｏ ｍａｘｉｍｉｚｅ ｔｈｅ ｕｓｅｒ’ｓ ｓａｔｉｓｆａｃｔｉｏｎ ｆｏｒ ＣＯＡ ｐｌａｎｎｉｎｇ． Ｔｈｅ ｐｌａｎｎｉｎｇ ｆｒａｍｅｗｏｒｋ ｂａｓｅｄ ｏｎ ｑｕａｌｉｔａｔｉｖｅ ｄｅｄｕｃｔｉｏｎ ｉｓ ａｎ ｅｆｆｅｃｔｉｖｅ ａｄｄ⁃ｉｎ ｆｏｒ ｃｏｎｖｅｎｔｉｏｎａｌ ｐｌａｎ⁃ ｎｉｎｇ ｓｃｈｅｍｅ ｂａｓｅｄ ｏｎ ｑｕａｎｔｉｔａｔｉｖｅ ｃｏｍｐｕｔａｔｉｏｎ． Ｔｈｅ ｐｒｏｐｅｒｔｙ ｏｆ ｐｒｅｆｅｒｅｎｃｅ⁃ｄｅｃｏｕｐｌｉｎｇ ｍａｋｅｓ ｉｔｓｅｌｆ ａｄａｐｔａｂｌｅ ｔｏ ａｐ⁃ ｐｌｉｃａｔｉｏｎｓ ｉｎ ｄｉｆｆｅｒｅｎｔ ｄｏｍａｉｎ． Ａ ｃａｓｅ ｓｔｕｄｙ ｏｎ ｓｃｈｅｄｕｌｉｎｇ ｒｅｓｐｏｎｓｉｖｅ ｉｍａｇｉｎｇ ｓａｔｅｌｌｉｔｅｓ ｉｓ ｐｒｏｐｏｓｅｄ ｔｏ ｄｅｍｏｎｓｔｒａｔｅ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｓｃｈｅｍｅ． Ｋｅｙｗｏｒｄｓ：ｃｏｕｒｓｅ⁃ｏｆ⁃ａｃｔｉｏｎ； ｐｌａｎｎｉｎｇ； ｑｕａｌｉｔａｔｉｖｅ ｐｒｅｆｅｒｅｎｃｅ； ｔｅｍｐｏｒａｌ ｐｒｅｆｅｒｅｎｃｅ； ｃｏｍｐｕｔａｔｉｏｎａｌ ａｒｇｕｍｅｎｔａｔｉｏｎ； ｐｒｅｆｅｒｅｎｃｅ ｄｅｃｏｕｐｌｉｎｇ 收稿日期：２０１３⁃０６⁃１０． 基金项目：．国家自然科学基金资助项目（７０９７１１３４） 通信作者：王炎娟． Ｅ⁃ｍａｉｌ：．ｎｕｄｔｗｙｊ＠ ｇｍａｉｌ．ｃｏｍ． 行动序列（ＣＯＡ）问题来自军事学领域，由于其 关于时间、动作等基本概念和问题结构与调度、规划 有着众多相通之处，已经得到了人工智能领域研究

·552. 智能系统学报 第9卷 者的广泛关注网。C0A的基本要素是动作(ac 文献[14]对时序软约束下的规划展开研究，根据软 tion),动作可以由子动作组合得到，由此构成了动 约束内容判定两个动作之间的可能关系：紧随、超前 作的分层结构。如军事领域的“完成阵地转移”，医 或不相关，为软约束设置偏好程度参数，根据以上因 学领域的“完成一个阶段的化疗”，日常生活领域的 素在每个时间点上搜索选择可用动作，随着时间点 “吃晚饭”，所描述的动作都对应了一种状态的转 的推移完成规划。这两种研究存在共同点，即依赖 换，而其中不涉及动作的组织方式、实施流程、具体 偏好或软约束的强度值作为判定依据，在动态搜索 的资源分配和管理。与动作的分层结构对应的， 过程中获得满意度或排除过约束。与本文最相关的 COA问题也可以具有分层结构。很多情况下，为了 是Blom6]的研究。在存在多种偏好，且偏好之间 完成一定层次的战略规划，COA不需要在最底层的 有冲突时，Blom首先使用非单调推理技术排除其中 动作上展开。本文关注一类典型的“任务级COA问 的冲突，获得最大一致性集合，在该集合基础上再进 题”，即任务级的动作随时间安排实现预定目标的 行决策或规划，决策或规划的搜索都是传统方式，通 问题，重点是在多种偏好并存时如何获得高质量的 过这种设计实现了“偏好解耦”，即规划过程与偏好 COA方案。决策理论中，偏好一般是指每个决策者 的表示方式或偏好内容无关，这对于规划算法在不 在面对几个事件或结果时选择其中一个事件或结果 同问题领域的通用性意义重大。遗憾的是，Blom并 的倾向性[3]COA的偏好问题也已经得到了研究者 没有关注时序偏好。Blom使用的逻辑工具为计算 的很多关注[4]。偏好来自C0A的参与者或者发 辩论。计算辩论技术是自1990年以来逐渐发展成 起者，虽然不构成强制约束力，但对于C0A生成方 熟并得到众多关注的逻辑工具，其在人工智能中的 案的质量至关重要。有研究者指出，规划方案的质 应用见于文献[15]。 量最优，除了要满足所有的约束条件之外，一定也是 针对带有定性偏好的任务级COA规划问题，本 对各种软约束（包括用户的偏好）有了最大程度的 文首先将使用比较格式给出任务级COA中的约束 满足【)。如何描述规划方案的质量，或者说，如何 和偏好定义，基于比较格式的形式化，给出COA方 定义对用户满意度的最大化，因偏好表示方法不同 案的生成算法：然后使用计算辩论技术消除约束/偏 而变化。可以知道，在使用定量偏好描述时，可以使 好集合中的不一致性，给出偏好集合上的最大满意 用定量的效能函数作为衡量。除常见的权重表示偏 度定义，在此基础上完成COA方案的生成。最大化 好，研究者后来发展出了区间数8]、模糊数[9]等定 任务的收益也不是任务级COA的主要目的，它只需 量表示方式。关于偏好的研究指出]，定性偏好 要保证高质量地完成预设目标，不需要定量优化的 比定量偏好更具有普遍性，很多时候用户使用自然 能力，因此获得的是一个可行解集合，而非确定的单 语言描述的复杂偏好关系，定量偏好是不能胜任表 个解。本文的研究是传统任务调度问题和约束问题 达的：随之而来的，定性偏好的使用使得定量的效能 研究的有效补充，同时也探讨了定性偏好关系的形 函数不再有效。 式化表达方式和推理方式。 任务级别COA问题与任务调度有相似之处，都 1 涉及到多方面的约束，如资源约束、能量约束 定性偏好表示与任务级C0A规划 等。偏好关系也是软约束之一。从满足尽可能 以任务级动作为基本元素的C0A问题称为任 多的限制条件、尽可能好地完成任务的角度来考虑， 务级COA。下面首先给出任务级动作的定义及其 任务级C0A与任务调度问题类似，同样具有约束满 形式化表示。 足问题(CSP)[2]的特征。但是任务级C0A对时间 定义1（任务级动作）给定COA问题P,满足 资源的调度具有突出的需求，如何时开始一个动作， 以下条件的动作称为任务级动作： 何时结束一个动作，如何合理安排动作之间的时序 1)动作的结果是一种确定的状态。 和因果关系。任务级COA的约束满足不能通过一 2)动作可以拆分为多个子动作或者元动作实 个单一的效能函数来表述和分析。 现，子动作集合及其排序方式可能有多种 已经有研究者对定性偏好相关的规划开展了研 3)动作之间没有目标的重叠，即：动作A引起 究。文献[13]从满意度的角度设计规划策略，对每 的状态变化，没有可能是可以由动作B实现的。 一个偏好设置偏好强度值，对一个规划序列中的所 定义2（任务级动作的形式化表示）动作由一 有偏好进行运算生成衡量值，通过该衡量值选择最 个三元组(s,g,t)表示。其中，s是动作主体，g是 优序列。这里探讨的偏好不包括时序相关的偏好。 动作受体，t是某种时间标记的集合，可以是一个时

者的广泛关注［１⁃２］ 。 ＣＯＡ 的基本要素是动作（ ａｃ⁃ ｔｉｏｎ），动作可以由子动作组合得到，由此构成了动 作的分层结构。 如军事领域的“完成阵地转移”，医 学领域的“完成一个阶段的化疗”，日常生活领域的 “吃晚饭”，所描述的动作都对应了一种状态的转 换，而其中不涉及动作的组织方式、实施流程、具体 的资源分配和管理。 与动作的分层结构对应的， ＣＯＡ 问题也可以具有分层结构。 很多情况下，为了 完成一定层次的战略规划，ＣＯＡ 不需要在最底层的 动作上展开。 本文关注一类典型的“任务级 ＣＯＡ 问 题”，即任务级的动作随时间安排实现预定目标的 问题，重点是在多种偏好并存时如何获得高质量的 ＣＯＡ 方案。 决策理论中，偏好一般是指每个决策者 在面对几个事件或结果时选择其中一个事件或结果 的倾向性［ ３ ］ＣＯＡ 的偏好问题也已经得到了研究者 的很多关注［ ４⁃６ ］ 。 偏好来自 ＣＯＡ 的参与者或者发 起者，虽然不构成强制约束力，但对于 ＣＯＡ 生成方 案的质量至关重要。 有研究者指出，规划方案的质 量最优，除了要满足所有的约束条件之外，一定也是 对各种软约束（包括用户的偏好）有了最大程度的 满足［ ７ ］ 。 如何描述规划方案的质量，或者说，如何 定义对用户满意度的最大化，因偏好表示方法不同 而变化。 可以知道，在使用定量偏好描述时，可以使 用定量的效能函数作为衡量。 除常见的权重表示偏 好，研究者后来发展出了区间数［ ８ ］ 、模糊数［ ９ ］ 等定 量表示方式。 关于偏好的研究指出［ １０ ］ ，定性偏好 比定量偏好更具有普遍性，很多时候用户使用自然 语言描述的复杂偏好关系，定量偏好是不能胜任表 达的；随之而来的，定性偏好的使用使得定量的效能 函数不再有效。 任务级别 ＣＯＡ 问题与任务调度有相似之处，都 涉及 到 多 方 面 的 约 束， 如 资 源 约 束、 能 量 约 束 等［ １１ ］ 。 偏好关系也是软约束之一。 从满足尽可能 多的限制条件、尽可能好地完成任务的角度来考虑， 任务级 ＣＯＡ 与任务调度问题类似，同样具有约束满 足问题（ＣＳＰ） ［ １２ ］的特征。 但是任务级 ＣＯＡ 对时间 资源的调度具有突出的需求，如何时开始一个动作， 何时结束一个动作，如何合理安排动作之间的时序 和因果关系。 任务级 ＣＯＡ 的约束满足不能通过一 个单一的效能函数来表述和分析。 已经有研究者对定性偏好相关的规划开展了研 究。 文献［１３］从满意度的角度设计规划策略，对每 一个偏好设置偏好强度值，对一个规划序列中的所 有偏好进行运算生成衡量值，通过该衡量值选择最 优序列。 这里探讨的偏好不包括时序相关的偏好。 文献［１４］对时序软约束下的规划展开研究，根据软 约束内容判定两个动作之间的可能关系：紧随、超前 或不相关，为软约束设置偏好程度参数，根据以上因 素在每个时间点上搜索选择可用动作，随着时间点 的推移完成规划。 这两种研究存在共同点，即依赖 偏好或软约束的强度值作为判定依据，在动态搜索 过程中获得满意度或排除过约束。 与本文最相关的 是 Ｂｌｏｍ ［ ６ ］的研究。 在存在多种偏好，且偏好之间 有冲突时，Ｂｌｏｍ 首先使用非单调推理技术排除其中 的冲突，获得最大一致性集合，在该集合基础上再进 行决策或规划，决策或规划的搜索都是传统方式，通 过这种设计实现了“偏好解耦”，即规划过程与偏好 的表示方式或偏好内容无关，这对于规划算法在不 同问题领域的通用性意义重大。 遗憾的是，Ｂｌｏｍ 并 没有关注时序偏好。 Ｂｌｏｍ 使用的逻辑工具为计算 辩论。 计算辩论技术是自 １９９０ 年以来逐渐发展成 熟并得到众多关注的逻辑工具，其在人工智能中的 应用见于文献［１５］。 针对带有定性偏好的任务级 ＣＯＡ 规划问题，本 文首先将使用比较格式给出任务级 ＣＯＡ 中的约束 和偏好定义，基于比较格式的形式化，给出 ＣＯＡ 方 案的生成算法；然后使用计算辩论技术消除约束／ 偏 好集合中的不一致性，给出偏好集合上的最大满意 度定义，在此基础上完成 ＣＯＡ 方案的生成。 最大化 任务的收益也不是任务级 ＣＯＡ 的主要目的，它只需 要保证高质量地完成预设目标，不需要定量优化的 能力，因此获得的是一个可行解集合，而非确定的单 个解。 本文的研究是传统任务调度问题和约束问题 研究的有效补充，同时也探讨了定性偏好关系的形 式化表达方式和推理方式。 １ 定性偏好表示与任务级 ＣＯＡ 规划 以任务级动作为基本元素的 ＣＯＡ 问题称为任 务级 ＣＯＡ。 下面首先给出任务级动作的定义及其 形式化表示。 定义 １ （任务级动作）给定 ＣＯＡ 问题 Ｐ ，满足 以下条件的动作称为任务级动作： １）动作的结果是一种确定的状态。 ２）动作可以拆分为多个子动作或者元动作实 现，子动作集合及其排序方式可能有多种 ３）动作之间没有目标的重叠，即：动作 Ａ 引起 的状态变化，没有可能是可以由动作 Ｂ 实现的。 定义 ２ （任务级动作的形式化表示）动作由一 个三元组 （ｓ，ｇ，ｔ） 表示。 其中， ｓ 是动作主体， ｇ 是 动作受体， ｔ 是某种时间标记的集合，可以是一个时 ·５５２· 智 能 系 统 学 报 第 ９ 卷

第5期 王炎娟，等：任务级行动序列问题中的定性偏好研究 ·553· 间点、时间间隔或某种时间标记。所有的动作集合 性偏好。 构成三元组集合(s,g,t)。 定量表示的偏好值，一般用某属性的被偏好程 为了表达逻辑的完备性，元素sg、t设置通配 度表示，为0~1的某个正数，数字越大表示偏好程 符~，表示对应的sg、1位置可以任意取值。形如 度越强。举例来说，p(A)=0.3表示动作A的偏好 (~,g,t)的表达式包含了多个元动作：(s1,g,t), 值为0.3，如果有p(B)=0.6,那么显然B比A更受 (s2g,t),(s3,g,t)等。(s,~,t),(s,g,~)与此 偏好。在进行选择时，只要知道p(B)>p(A)这一 类似。任务级C0A问题的定性偏好可以划分为两 事实即可，至于B的受偏好程度是0.6还是0.7，都 类。第1种是与时序无关的静态偏好，或者称为动 可以得到B>A这一结论，不影响决策者的判断。 作间的属性偏好，即：因为动作某种属性被偏好，即： 定性偏好恰好具有这种相对偏好的表达能力。特殊 用户倾向于选择动作A还是动作B。第2种是动作 地，如果没有能够与动作A进行比较的动作，那么 间的时序或因果顺序偏好，即：用户偏好于动作A在 可以知道：A>⊙。 动作B之前，还是动作B在动作A之前，本文从另一 当然，定性偏好能够表达的并不局限于这种数 个角度表述为：倾向于先执行使用动作A,还是先执 值基础上的相对关系，比如时序偏好。从语义覆盖 行动作B.下面给出了定性偏好的归一化表示。 性的角度，定性偏好的表达是涵盖定量偏好的。 定义3（定性偏好的归一化表示）定性偏好由 断言2定性偏好表达不能替代定量表达。 三元组(S,G,T)中的两个元素和一个二元操作符 定性表达的优势在于复杂语义的阐述，不能像 (>或>)组成，形式化表达如下： 传统的定量优化算法那样得到具有优化指标的唯一 (s,8,4)>g（8） 最优解，一般只能得到可行解集合。本文的思路是， (s,g,l)Dg)(,84） 定性偏好的推理过程服务于定量偏好。比如，给定 式中：>为连接两个三元组的支配关系，给出了两 一组偏好集合，首先使用定性表达确定它们内部是 个选项的静态比较；>为连接两个三元组的一个 不是有冲突，即：这个偏好集合是不是能够共存的， “在前面”的语义关系，给出了一种因果关系或者时 如果可以，那么就继续进行数值规划，给出优化指 间的比较。每个表达式只对三元组中的一个元素进 标：否则就继续寻找下一组偏好，不在没有可能的偏 行比较，>或>都可以配备有下标s,g或t,表示 好集合上浪费定量优化的计算资源。 引起比较关系的有效元素。 断言3任务级层次的偏好与软约束具有相同 为了表达逻辑的完备性，为三元组定义一个 的结构。 “空”状态Θ，用以表征一个“不被偏好”的虚拟动 软约束是指不具有强制力的约束关系，自然语 作，意为任意一个非空动作均可以对它构成二元关 言理解为“建议满足”而非“必需满足”，这与偏好的 系。如自然语言的偏好表述：“用户偏好于动作 语义有相通之处。更进一步，在把偏好和约束并列 (s1,g1,1)”,没有特定的比较对象，可以表示为 考察时，约束也应该具有与偏好对等的表达方式，因 (s1,81,41)>日。 此后文将对偏好和约束进行归一化表示。软约束与 偏好的表示方式多种多样。除了经典的定量表 偏好的区别仅在于：偏好具有人的主观特性，而软约 示之外，定性表示可以划分为C-P网络[、时序逻 束可能来自事物本身的客观特征，文中不明确区分 辑4)、比较格式1]等。定义3给出的是一种比较 软约束和偏好，统称为偏好：而约束则是指有强制约 格式的表达方式，秉承了Blom的理念：偏好本质上 束力的硬约束。 是一种二元关系，因而本文选择的是一种相对偏好 定义4（约束和偏好的归一化表示）约束和偏 表示。这是实现偏好解耦设计的关键。 好可以统一为四元组表示：〈R,,山，k〉。其中，R 通过引入>符号，时序或因果偏好的形式化表 为二元关系>或>，4：、山为前述定义的三元组， 述可以与静态偏好统一到一个框架内：而空状态⊙ k为0表示硬约束，k为正数表示偏好，数字越大，偏 和任意状态(~，~，~)的存在，可以把非典型的 好程度越弱。 二元关系也赋予一个二元比较关系方式。如，动作 假设偏好之间，以及偏好和约束之间没有相互 （~,~,~)D(S1,81,4)表示用户偏好于最后 矛盾，那么可以执行算法1获得COA方案。 执行动作(s1,81,1）。 算法1由约束/偏好集合生成C0A方案的两 在展开后续推导之前，给出3个断言。 阶段算法2DOF-SLCOA。 断言1任务级层次的定量偏好可以转换到定 输入：静态约束/偏好集合Ex,,时序约束/偏

间点、时间间隔或某种时间标记。 所有的动作集合 构成三元组集合 （ｓ，ｇ，ｔ） 。 为了表达逻辑的完备性，元素 ｓ、ｇ、ｔ 设置通配 符～ ，表示对应的 ｓ、ｇ、ｔ 位置可以任意取值。 形如 （ ～ ，ｇ，ｔ） 的表达式包含了多个元动作： （ｓ１ ，ｇ，ｔ）， （ｓ２ ，ｇ，ｔ），（ｓ３ ，ｇ，ｔ） 等。 （ｓ， ～ ，ｔ） ， （ｓ，ｇ， ～ ） 与此 类似。 任务级 ＣＯＡ 问题的定性偏好可以划分为两 类。 第 １ 种是与时序无关的静态偏好，或者称为动 作间的属性偏好，即：因为动作某种属性被偏好，即： 用户倾向于选择动 作 Ａ 还是动作 Ｂ。 第 ２ 种是动作 间的时序或因果顺序偏好，即：用户偏好于动作 Ａ 在 动作 Ｂ 之前，还是动作 Ｂ 在动作 Ａ 之前，本文从另一 个角度表述为：倾向于先执行使用动作 Ａ ，还是先执 行动作 Ｂ． 下面给出了定性偏好的归一化表示。 定义 ３ （定性偏好的归一化表示）定性偏好由 三元组（ Ｓ，Ｇ，Ｔ ）中的两个元素和一个二元操作符 （ ≻ 或 ▷ ）组成，形式化表达如下： （ｓｉ，ｇｉ，ｔ ｉ） ≻ｓ（ｇ，ｔ）（ｓｊ，ｇｊ，ｔ ｊ） （ｓｉ，ｇｉ，ｔ ｉ）▷ｓ（ｇ，ｔ）（ｓｊ，ｇｊ，ｔ ｊ） 式中： ≻ 为连接两个三元组的支配关系，给出了两 个选项的静态比较； ▷ 为连接两个三元组的一个 “在前面”的语义关系，给出了一种因果关系或者时 间的比较。 每个表达式只对三元组中的一个元素进 行比较， ≻ 或 ▷ 都可以配备有下标 ｓ，ｇ 或 ｔ， 表示 引起比较关系的有效元素。 为了表达逻辑的完备性，为三元组定义一个 “空”状态 Θ ，用以表征一个“不被偏好” 的虚拟动 作，意为任意一个非空动作均可以对它构成二元关 系。 如自然语言的偏好表述： “ 用户偏好于动作 （ｓ１ ，ｇ１ ，ｔ １ ） ”，没有特定的比较对象， 可以表示为 （ｓ１ ，ｇ１ ，ｔ １ ） ≻ｓΘ 。 偏好的表示方式多种多样。 除了经典的定量表 示之外，定性表示可以划分为 Ｃ⁃Ｐ 网络［１６］ 、时序逻 辑［４］ 、比较格式［１７⁃１８］等。 定义 ３ 给出的是一种比较 格式的表达方式，秉承了 Ｂｌｏｍ 的理念：偏好本质上 是一种二元关系，因而本文选择的是一种相对偏好 表示。 这是实现偏好解耦设计的关键。 通过引入 ▷ 符号，时序或因果偏好的形式化表 述可以与静态偏好统一到一个框架内；而空状态 Θ 和任意状态 （ ～ ， ～ ， ～ ） 的存在，可以把非典型的 二元关系也赋予一个二元比较关系方式。 如，动作 （ ～ ， ～ ， ～ ）▷ｓ（ｇ，ｔ）（ｓ１ ，ｇ１ ，ｔ １ ） 表示用户偏好于最后 执行动作 （ｓ１ ，ｇ１ ，ｔ １ ） 。 在展开后续推导之前，给出 ３ 个断言。 断言 １ 任务级层次的定量偏好可以转换到定 性偏好。 定量表示的偏好值，一般用某属性的被偏好程 度表示，为 ０～ １ 的某个正数，数字越大表示偏好程 度越强。 举例来说， ｐ（Ａ） ＝ ０．３ 表示动作 Ａ 的偏好 值为 ０．３，如果有 ｐ（Ｂ） ＝ ０．６，那么显然 Ｂ 比 Ａ 更 受 偏好。 在进行选择时，只要知道 ｐ（Ｂ） ＞ ｐ（Ａ） 这一 事实即可，至 于 Ｂ 的 受偏好程度是 ０．６ 还是 ０．７，都 可以得到 Ｂ ≻ Ａ 这一结论，不影响决策者的判断。 定性偏好恰好具有这种相对偏好的表达能力。 特殊 地，如果没有能够与动作 Ａ 进 行比较的动作，那么 可以知道： Ａ ≻ Θ 。 当然，定性偏好能够表达的并不局限于这种数 值基础上的相对关系，比如时序偏好。 从语义覆盖 性的角度，定性偏好的表达是涵盖定量偏好的。 断言 ２ 定性偏好表达不能替代定量表达。 定性表达的优势在于复杂语义的阐述，不能像 传统的定量优化算法那样得到具有优化指标的唯一 最优解，一般只能得到可行解集合。 本文的思路是， 定性偏好的推理过程服务于定量偏好。 比如，给定 一组偏好集合，首先使用定性表达确定它们内部是 不是有冲突，即：这个偏好集合是不是能够共存的， 如果可以，那么就继续进行数值规划，给出优化指 标；否则就继续寻找下一组偏好，不在没有可能的偏 好集合上浪费定量优化的计算资源。 断言 ３ 任务级层次的偏好与软约束具有相同 的结构。 软约束是指不具有强制力的约束关系，自然语 言理解为“建议满足”而非“必需满足”，这与偏好的 语义有相通之处。 更进一步，在把偏好和约束并列 考察时，约束也应该具有与偏好对等的表达方式，因 此后文将对偏好和约束进行归一化表示。 软约束与 偏好的区别仅在于：偏好具有人的主观特性，而软约 束可能来自事物本身的客观特征，文中不明确区分 软约束和偏好，统称为偏好；而约束则是指有强制约 束力的硬约束。 定义 ４ （约束和偏好的归一化表示）约束和偏 好可以统一为四元组表示： 〈Ｒ，ｕｉ，ｕｊ，ｋ〉 。 其中， Ｒ 为二元关系 ≻ 或 ▷ ， ｕｉ 、 ｕｊ 为前述定义的三元组， ｋ 为 ０ 表示硬约束， ｋ 为正数表示偏好，数字越大，偏 好程度越弱。 假设偏好之间，以及偏好和约束之间没有相互 矛盾，那么可以执行算法 １ 获得 ＣＯＡ 方案。 算法 １ 由约束／ 偏好集合生成 ＣＯＡ 方案的两 阶段算法 ２ＤＯＦ⁃ＳＬＣＯＡ。 输入： 静态约束／ 偏好集合 Ｅｘ≻ ，时序约束／ 偏 第 ５ 期 王炎娟，等：任务级行动序列问题中的定性偏好研究 ·５５３·

·554. 智能系统学报 第9卷 好集合ExP 击)关系，即有R二A×A。 输出：动作序列(COA规划方案) 在AF=(A,R)中，若A是有限集，称AF有限 步骤1从静态约束集合Ex,中选择可用动作 的，否则称为无限的。对于Ha,b∈A,aRb或(a, 集合。 b)∈R表示a攻击b;a、b间不存在攻击关系，表 1)基于Ex,中的元素构建有向图H、。对于 示为aRb或(a,b)R,亦称a、b是无冲突的。R Ex,中每个约束/偏好关系，连接两个三元组的> (a)={b∈AI aRb}表示被a攻击的论据集，R 关系对应导向图中的一个边，相关的两个三元组则 (a)={b∈A1bRa}表示攻击a的论据集：对于论据 是图中的节点.从不同约束/偏好关系中提出的同 集SCA和论据b∈A,若3a∈S,使得aRb,则称 一个三元组对应同一个节点，因此，某一个节点可能 S攻击a。同理，有Rw(S)=U.esRw(a)（w∈ 会有边界指向多个节点，也可能有多个节点的边界 {+,-})。 指向它。 论据集S(S二A),若Ha,b∈S,(a,b)R, 2)选择有向图H,中的优势节点，即：每个支链 称S是无冲突的(conflict-free)。论据集S是无冲突 的起始节点，置于一个集合U,中。 的，满足Ha∈R-(S)→(3b∈S).bRa,称S为 步骤2结合时序约束，得到调度方案。 可容许集(admissible set)。 1)U,中的每一个元素u都被替换为一个时序 AF=(A,R)可以表示为有向图，称为攻击图 约束关系>O,构成时序约束/偏好关系集合 如图1所示的攻击图中A={a,b,c,d},R={(a U。。 c),(b,a),(c,b),(c,a),(d,c)}。由此可知， 2)基于U。和Ex。生成有向图H。.U。或ExD R,(c)={a,b}及R_(c)={a,d}。 中的>优势关系被翻译成有向图的边，而与之相关 联的三元组被放置在节点位置。对等的三元组只作 为一个节点出现。 3)寻找H。中的可用序列。从一个根节点出 发，追踪连续的链接关系形成一个节点序列。 图1辩论框架 4)节点序列经解释或翻译得到动作序列。 Fig.1 Argumentation framework 2非单调偏好的处理和最大满意度 根据Dung的扩展语义，该实例中的首选扩展 对于一个进行COA规划的智能体来说，只要约 集合为Sd={d,b}.该集合满足以下条件，也就是 束和偏好之间没有任何的冲突，偏好的作用与约束 首选扩展语义的定义： 是相同的。然而，经常出现的情况是，约束/偏好集 1)Sd中的论据相互之间不冲突： 合中会出现一个以上的冲突，此时就需要首先排除 2)S中的论据不会被其他论据工具；或者， 不一致性，获得具有最大一致性的约束/偏好集合， 3)如果论据x∈Spm被另一个论据y生S攻 才能继续推理得到规划方案。冲突关系数目较多 击，那么必然有第3个论据：∈S满足Ry. 时，约束或偏好之间相互的优势关系错综复杂，简单 概括来讲，辩论就是一个信念萃取的过程，排除 的逻辑判断不能确定最大一致性。本文使用计算辩 那些内含不一致性的选项，达成一个最大一致性。 论[9]这一非单调推理工具来执行逻辑推理。 在后续章节里，将其直接用于逻辑推理，不再涉及背 2.1辩论基础 后的逻辑过程。 2.2论据定义 这里简要介绍了Dung的辩论框架与相关的 定义，读者可以参考文献[町以获取更多关于辩论 为了进行辩论，首先是构造论据。每一个约束 的内容。 或偏好自然地形成一个论据。 定义5任务级C0A中的论据定义。一个约 辩论框架为辩论提供了形式化建模方法，建立 束或偏好相关的论据被定义一个4元结构： 一种处理不确定、不一致信息的基础。下面简要介 (kpeuu'krank) 绍Dung辩论框架及其相关性质。 式中：、分别为约束定义中的三元组.k表征 辩论框架通常定义为二元组AF=(A,R),其中 了关系类型，即>或>。km对应了>或>的上 A表示论据集，R是定义在论据集A上的二元（攻 标，即0或者一个表征软约束强度的正整数

好集合 Ｅｘ▷ 输出： 动作序列（ＣＯＡ 规划方案） 步骤 １ 从静态约束集合 Ｅｘ≻ 中选择可用动作 集合 。 １）基于 Ｅｘ≻ 中的元素构建有向图 Ｈ≻ 。 对于 Ｅｘ≻ 中每个约束／ 偏好关系，连接两个三元组的 ≻ 关系对应导向图中的一个边，相关的两个三元组则 是图中的节点． 从不同约束／ 偏好关系中提出的同 一个三元组对应同一个节点，因此，某一个节点可能 会有边界指向多个节点，也可能有多个节点的边界 指向它。 ２）选择有向图 Ｈ≻ 中的优势节点，即：每个支链 的起始节点，置于一个集合 Ｕ≻ 中。 步骤 ２ 结合时序约束，得到调度方案。 １） Ｕ≻ 中的每一个元素 ｕ 都被替换为一个时序 约束关 系 ｕ▷Θ ， 构 成 时 序 约 束／ 偏 好 关 系 集 合 Ｕ▷ 。 ２）基于 Ｕ▷ 和 Ｅｘ▷ 生成有向图 Ｈ▷ ． Ｕ▷ 或 Ｅｘ▷ 中的 ▷ 优势关系被翻译成有向图的边，而与之相关 联的三元组被放置在节点位置。 对等的三元组只作 为一个节点出现。 ３）寻找 Ｈ▷ 中的可用序列。 从一个根节点出 发， 追踪连续的链接关系形成一个节点序列。 ４）节点序列经解释或翻译得到动作序列。 ２ 非单调偏好的处理和最大满意度 对于一个进行 ＣＯＡ 规划的智能体来说，只要约 束和偏好之间没有任何的冲突，偏好的作用与约束 是相同的。 然而，经常出现的情况是，约束／ 偏好集 合中会出现一个以上的冲突，此时就需要首先排除 不一致性，获得具有最大一致性的约束／ 偏好集合， 才能继续推理得到规划方案。 冲突关系数目较多 时，约束或偏好之间相互的优势关系错综复杂，简单 的逻辑判断不能确定最大一致性。 本文使用计算辩 论［１９］这一非单调推理工具来执行逻辑推理。 ２．１ 辩论基础 这里简要介绍了 Ｄｕｎｇ 的辩论框架与相关的 定义，读者可以参考文献［１９］ 以获取更多关于辩论 的内容。 辩论框架为辩论提供了形式化建模方法，建立 一种处理不确定、不一致信息的基础。 下面简要介 绍 Ｄｕｎｇ 辩论框架及其相关性质。 辩论框架通常定义为二元组 ＡＦ ＝ （Ａ，Ｒ） ，其中 Ａ 表示论据集， Ｒ 是定义在论据集 Ａ 上的二元（攻 击）关系，即有 Ｒ ⊆ Ａ × Ａ 。 在 ＡＦ ＝ （Ａ，Ｒ） 中，若 Ａ 是有限集，称 ＡＦ 有限 的，否则称为无限的。 对于 ∀ａ，ｂ ∈ Ａ ， ａＲｂ 或 （ａ， ｂ） ∈ Ｒ 表示 ａ 攻击 ｂ ； ａ 、 ｂ 间不存在攻击关系，表 示为 ａＲｂ 或 （ａ，ｂ） ∉ Ｒ ，亦称 ａ 、 ｂ 是无冲突的。 Ｒ＋ （ａ） ＝ ｛ｂ ∈ Ａ ｜ ａＲｂ｝ 表示被 ａ 攻击的论据集， Ｒ－ （ａ） ＝ ｛ｂ ∈Ａ ｜ ｂＲａ｝ 表示攻击 ａ 的论据集；对于论据 集 Ｓ ⊆ Ａ 和论据 ｂ ∈ Ａ ，若 ∃ａ ∈ Ｓ ，使得 ａＲｂ ，则称 Ｓ 攻击 ａ 。 同理， 有 Ｒω（Ｓ） ＝∪ａ∈ＳＲω（ａ） （ ω ∈ ｛ ＋， －｝ ）。 论据集 Ｓ （ Ｓ ⊆Ａ ），若 ∀ａ，ｂ ∈Ｓ ， （ａ，ｂ） ∉Ｒ， 称 Ｓ 是无冲突的（ｃｏｎｆｌｉｃｔ⁃ｆｒｅｅ）。 论据集 Ｓ 是无冲突 的，满足 ∀ａ ∈ Ｒ － （Ｓ） → （∃ｂ ∈ Ｓ）．ｂＲａ ，称 Ｓ 为 可容许集（ａｄｍｉｓｓｉｂｌｅ ｓｅｔ）。 ＡＦ ＝ （Ａ，Ｒ） 可以表示为有向图，称为攻击图。 如图 １ 所示的攻击图中 Ａ ＝ ｛ａ，ｂ，ｃ，ｄ｝ ， Ｒ ＝ ｛（ａ， ｃ）， （ｂ，ａ）， （ｃ，ｂ）， （ｃ，ａ）， （ｄ，ｃ）｝ 。 由 此 可 知， Ｒ＋ （ｃ） ＝｛ａ，ｂ｝ 及 Ｒ－ （ｃ） ＝ ｛ａ，ｄ｝ 。 图 １ 辩论框架 Ｆｉｇ．１ Ａｒｇｕｍｅｎｔａｔｉｏｎ ｆｒａｍｅｗｏｒｋ 根据 Ｄｕｎｇ 的扩展语义，该实例中的首选扩展 集合为 Ｓｐｒｅｆ ＝ ｛ｄ，ｂ｝ ． 该集合满足以下条件，也就是 首选扩展语义的定义： １） Ｓｐｒｅｆ 中的论据相互之间不冲突； ２） Ｓｐｒｅｆ 中的论据不会被其他论据工具； 或者， ３） 如果论据 ｘ ∈ Ｓｐｒｅｆ 被另一个论据 ｙ ∉ Ｓｐｒｅｆ 攻 击 ， 那么必然有第 ３ 个论据 ｚ ∈ Ｓｐｒｅｆ 满足 ｚＲｙ ． 概括来讲，辩论就是一个信念萃取的过程，排除 那些内含不一致性的选项，达成一个最大一致性。 在后续章节里，将其直接用于逻辑推理，不再涉及背 后的逻辑过程。 ２．２ 论据定义 为了进行辩论，首先是构造论据。 每一个约束 或偏好自然地形成一个论据。 定义 ５ 任务级 ＣＯＡ 中的论据定义。 一个约 束或偏好相关的论据被定义一个 ４ 元结构： ｋ ｔｙｐｅ ，ｕ ｆ ，ｕ ｒ ，ｋ ｒａｎｋ ( ) 式中： ｕ ｆ 、ｕ ｒ 分别为约束定义中的三元组． ｋ ｔｙｐｅ 表征 了关系类型，即 ≻ 或 ▷ 。 ｋ ｒａｎｋ 对应了 ≻ 或 ▷ 的上 标，即 ０ 或者一个表征软约束强度的正整数。 ·５５４· 智 能 系 统 学 报 第 ９ 卷

第5期 王炎娟，等：任务级行动序列问题中的定性偏好研究 ·555. 不包含通配符~的论据称为元论据。与此相对 中，一些偏好会被约束或其他一些更高优先级的偏 的，含有通配符~的论据可以通过把~对应的元素 好关系击败，因而被剔除，留在集合Ex,和Ex。中 进行枚举，分解为多个元论据。两个元论据之间的 的就是最大兼容性的约束子集。 攻击关系定义如下。 断言5论据的首选扩展集合给出的用户最大 定义6（论据间的攻击关系）给定两个元论据 满意度集合。 a:=(,,,km),西=(，，叫，写) 2.4主要结果 它们之间的关系定义如下。 本节的主要结果总结在算法2和算法3中。 1)两论据a:和g是可比的，当且仅当=。 算法2基于辩论解决偏好不一致性。 2)冲突关系：两论据被称为是冲突的，当且仅 输入：一个任务级COA问题，已建立约束/偏好 当它们是可比的，而且=4，=。 集合。 3)攻击关系：论据a:攻击a,记为a,Ra,当 输出：首选扩展集Ex,与ExD。 且仅当a:与a冲突，并且km≤。 1)构造论据集合，包含通配符的论据拆分为元 2.3任务级C0A的辩论框架 论据。 接下来建立任务级COA问题的辩论框架。 2)在论据间进行搜索，构造攻击关系。 定义7任务级C0A辩论框架TCOA-ARG。对 3)执行DUNG的首选辩论语义，获得首选扩展 于一个TCOA-ARG问题，其辩论框架为一个三元 集合Ex,和ExD。 组,其中A为来自约束集合和偏好集 如果Ex,或Ex。是空集，那就意味着静态或时 合的论据，R为论据间的攻击关系，SL为获得辩论 序约束中存在一些不能解决的冲突。因而不能获得 结果的辩论语义。 调度方案。否则，就可以进行下一阶段的工作，引用 该框架与Blom的偏好解耦框架是一致的[6]」 算法1构造COA可行解。 区别仅在于，针对静态和时序约束存在两种二元关 算法3带定性约束/偏好的任务级COA规划 系，因此构造攻击关系时每种论据都是局限在自己 ARG-COA。 的二元关系归类中。结果自然是每种攻击关系操作 输入：一个任务级COA问题。 符都有一个独立的辩论结果。本文使用的辩论语义 输出：COA规划方案。 SL与Blom!6]相同，即SL为Dung]首选扩展语义。 1)建立定性约束/偏好集合。 断言4TC0A-ARG的辩论结果是一个静态 2)执行算法2获取一致性约束/偏好集合Ex, (时序)约束的首选扩展集，也就是说，没有内部冲 与Exp。 突的静态（时序）约束的最大集，记为 3)执行算法1得到规划结果。 A=A>UAp 3 案例研究 sL,Ex A 文中以一种卫星的突发性任务观测为背景展开 Ap SL Exe 案例研究。卫星设计如目前正在运行的LAPAN- 式中：A,和A。分别为基于>或>的论据子集， TUBSAT0]。卫星装有视频摄像机，提供实时目标 E:x,和E。分别为从A,和A。推导出来的首选扩 监控，无板载存储。 展集合。 研究次日有2颗卫星过境，兴趣目标有3个，每 需要指出的是，每一个论据均对应了一个约束 个卫星均有2个可操作时间窗口。表1给出了卫星 或偏好，表达了2个动作之间的优势关系。在辩论 的技术状态描述，表2给出了卫星的可见窗口描述。 表1卫星技术状态描述 Table 1 Description of satellites'technical status 卫星编号可见孤段/min 分辨力 成像波段 与测控站距离 s 15 2048×2048 红外/可见光 2000 S2 8 762x576 可见光 1000

不包含通配符～的论据称为元论据。 与此相对 的，含有通配符 ～ 的论据可以通过把 ～ 对应的元素 进行枚举，分解为多个元论据。 两个元论据之间的 攻击关系定义如下。 定义 ６ （论据间的攻击关系）给定两个元论据 ａｉ ＝ ｋ ｔｙｐｅ ｉ ，ｕ ｆ ｉ，ｕ ｒ ｉ，ｋ ｒａｎｋ ｉ ( ) ，ａｊ ＝ ｋ ｔｙｐｅ ｊ ，ｕ ｆ ｊ ，ｕ ｒ ｊ ，ｋ ｒａｎｋ ｊ ( ) 它们之间的关系定义如下。 １）两论据 ａｉ 和 ａｊ 是可比的，当且仅当 ｋ ｔｙｐｅ ｉ ＝ ｋ ｔｙｐｅ ｊ 。 ２）冲突关系 ： 两论据被称为是冲突的， 当且仅 当它们是可比的，而且 ｕ ｆ ｉ ＝ ｕ ｒ ｊ ， ｕ ｒ ｉ ＝ ｕ ｆ ｊ 。 ３）攻击关系： 论据 ａｉ 攻击 ａｊ ， 记为 ａｉＲ ＿ ａｊ ， 当 且仅当 ａｉ 与 ａｊ 冲突， 并且 ｋ ｒａｎｋ ｉ ≤ ｋ ｒａｎｋ ｊ 。 ２．３ 任务级 ＣＯＡ 的辩论框架 接下来建立任务级 ＣＯＡ 问题的辩论框架。 定义 ７ 任务级 ＣＯＡ 辩论框架 ＴＣＯＡ⁃ＡＲＧ。 对 于一个 ＴＣＯＡ⁃ＡＲＧ 问题， 其辩论框架为一个 三元 组 ＜ Ａ，Ｒ，ＳＬ ＞ ， 其中 Ａ 为来自约束集合和偏好集 合的论据，Ｒ 为论据间的攻击关系，ＳＬ 为 获得辩论 结果的辩论语义。 该框架与 Ｂｌｏｍ 的偏好解耦框架是一致的［ ６ ］ ， 区别仅在于，针对静态和时序约束存在两种二元关 系，因此构造攻击关系时每种论据都是局限在自己 的二元关系归类中。 结果自然是每种攻击关系操作 符都有一个独立的辩论结果。 本文使用的辩论语义 ＳＬ 与 Ｂｌｏｍ ［ ６ ］相同，即 ＳＬ 为 Ｄｕｎｇ ［ １９ ］首选扩展语义。 断言 ４ ＴＣＯＡ⁃ＡＲＧ 的辩论结果是一个静态 （时序）约束的首选扩展集，也就是说，没有内部冲 突的静态（时序）约束的最大集， 记为 Ａ ＝ Ａ≻∪ Ａ▷ Ａ≻ ＳＬ→ Ｅｘ≻ Ａ▷ ＳＬ→ Ｅｘ▷ 式中： Ａ≻ 和 Ａ▷ 分别为基于 ≻ 或 ▷ 的论据子集， Ｅｘ≻ 和 Ｅｘ▷ 分别为从 Ａ≻ 和 Ａ▷ 推导出来的首选扩 展集合。 需要指出的是，每一个论据均对应了一个约束 或偏好，表达了 ２ 个动作之间的优势关系。 在辩论 中，一些偏好会被约束或其他一些更高优先级的偏 好关系击败，因而被剔除，留在集合 Ｅｘ≻ 和 Ｅｘ▷ 中 的就是最大兼容性的约束子集。 断言 ５ 论据的首选扩展集合给出的用户最大 满意度集合。 ２．４ 主要结果 本节的主要结果总结在算法 ２ 和算法 ３ 中。 算法 ２ 基于辩论解决偏好不一致性。 输入：一个任务级 ＣＯＡ 问题，已建立约束／ 偏好 集合 。 输出：首选扩展集 Ｅｘ≻ 与 Ｅｘ▷ 。 １ ）构造论据集合，包含通配符的论据拆分为元 论据。 ２ ）在论据间进行搜索，构造攻击关系。 ３ ）执行 ＤＵＮＧ 的首选辩论语义，获得首选扩展 集合 Ｅｘ≻ 和 Ｅｘ▷ 。 如果 Ｅｘ≻ 或 Ｅｘ▷ 是空集，那就意味着静态或时 序约束中存在一些不能解决的冲突。 因而不能获得 调度方案。 否则，就可以进行下一阶段的工作，引用 算法 １ 构造 ＣＯＡ 可行解。 算法 ３ 带定性约束／ 偏好的任务级 ＣＯＡ 规划 ＡＲＧ⁃ＣＯＡ。 输入：一个任务级 ＣＯＡ 问题。 输出：ＣＯＡ 规划方案。 １）建立定性约束／ 偏好集合。 ２ ）执行算法 ２ 获取一致性约束／ 偏好集合 Ｅｘ≻ 与 Ｅｘ▷ 。 ３） 执行算法 １ 得到规划结果。 ３ 案例研究 文中以一种卫星的突发性任务观测为背景展开 案例研究。 卫星设计如目前正在运行的 ＬＡＰＡＮ⁃ ＴＵＢＳＡＴ ［ ２０ ］ 。 卫星装有视频摄像机，提供实时目标 监控，无板载存储。 研究次日有 ２ 颗卫星过境，兴趣目标有 ３ 个，每 个卫星均有 ２ 个可操作时间窗口。 表 １ 给出了卫星 的技术状态描述，表 ２ 给出了卫星的可见窗口描述。 表 １ 卫星技术状态描述 Ｔａｂｌｅ １ Ｄｅｓｃｒｉｐｔｉｏｎ ｏｆ ｓａｔｅｌｌｉｔｅｓ’ ｔｅｃｈｎｉｃａｌ ｓｔａｔｕｓ 卫星编号 可见弧段／ ｍｉｎ 分辨力 成像波段 与测控站距离 Ｓ１ １５ ２ ０４８×２ ０４８ 红外／ 可见光 ２ ０００ Ｓ２ ８ ７６２×５７６ 可见光 １ ０００ 第 ５ 期 王炎娟，等：任务级行动序列问题中的定性偏好研究 ·５５５·

.556. 智能系统学报 第9卷 表2卫星可操控时间列表 Table 2 List of satellite's time widow for operation 卫星 操作时间窗口 S [15:4015:55]am [17:1017:30]am S2 [9:409:55]am [11:0011:10]am 把观测任务视为COA问题，考察以下类型偏好。 进入阴影区，在下一个任务之前不能充分充电。 1)目标的价值有优先级，用户在白天要首先观 (C2)(s1,g3,#)D8(s1,g3,45.o0pm) 察到优先级高的目标。 现在可以综合(P1)~(P10)和(C1)~(C2), 2)根据地面测控站的要求，对同一个目标执行 执行辩论并完成任务级COA方案。 观测动作时，希望使用能提供较长可见弧段的卫星。 从偏好构建论据时，还需要确定偏好自身的优 3)考虑到卫星的能量储备，在进行观测时，优先 先级。在本案例中，根据偏好的提出者来确定Arank 考虑姿态机动小、耗费能量少的卫星。 这个值。卫星运营商、卫星设计方和用户提出的偏 4)对同一目标成像，用户喜欢高分辨率的图像。 好关系将分别有3、2和1的优先级。当然，从约束 5)对某目标成像时，用户希望首先得到低分辨 构造的论据都具有0的优先级。 率图像，再获得高分辨率图像，方便图像判读。 1)论据构建 6)从用户角度，监视运动目标具有更高优先级。 (P1):a1=[D,(~,g1,~）,(~,#,~),1] 7)从传输信道的稳定性来讲，希望使用距离测 (P2):a2=[D,（~,#~),(~,82,~）,1] 控站距离近的卫星进行观测。 (P3):a3=[>,(s2,~,~）,($2,~,~),3] 8)进行森林火灾目标的检测时，更希望使用配 (P4):a4=[>,(s1,8,~),(s181,~),2] 备红外相机的卫星。 (P5):a5=[>,(s1,~,~),（1,~,）,1] 下面根据以上规则给出各偏好的形式化表达。 (P6):a6=[>,(s2,#,~),(s1,#,~),1] 目标优先级偏好：目标g,的优先级最高，而目 (P7):a,=[>,(~g1,~),（~,g1,~),1] 标g,的优先级最低，因而有 (P8):ag=[>,Θ，(s1,g1,~）,1] (P1)（~81,)D(~,#,~) (P9):ag=[>,(s2,81,~),(52g1,~）,1] (P2)(~,#,~)D(~,82,~) (P10):a2=【>,(s2,82,#),(32,82,#),0] 可用测控弧段偏好： (C1):a0=[D,（~,~,0mw),（~g3,7t0mm),0] (P3)(s2,~,~)>（72,~,~) (C2):a4=[D,(s1,g3,#),(s1,g3,5.o0rw),0] 姿态机动能量偏好： 2)攻击关系构建 (P4)(s1,83,~）>(s1,81,~) 记 成像分辨率偏好： A>={a3,a4,a5,a7,ag,ag,a12} (P5)(s1,~,~)>(51,~,~) Ac={a1,a2,a6,a10,a14} 低、高分辨率切换顺序偏好： A。内部没有冲突，因此，Ex。=A。·而对于A,则 (P6)(s2,,~)D(s1,~,~) 需要执行一个辩论过程以获得Ex,。 移动目标监视偏好： 论据a,拆分为 (P7)(~,g1,~）>（,7g1,~) 信道传输质量偏好： a5=[>,(s1,7g2,~),(s1,g2,~),1] a=[>,(s1g2,~),(5182,~),1] (P8)Θ>(51,81，~） 输出帧率偏好： a3=[>,(s1,(g11g2）,~), (P9)(s281,~）>(5281,~) （51,(g1g2),~),1] 成像谱段偏好：目标g2处于森林火险等级较 论据a,拆分为 高的区域，优先考虑使用红外相机观测，即 a=[>,(s1,81,~),(s1,7g1,~),1] (P10)(52,g2,-)>(2,~,~) a7=[>,(s2,g1,~）,(s2,g1,~）,1] 下面给出3个约束关系。据气象预报，上午10 得到攻击关系如下： 时前目标g,被云层覆盖，不能被观测到。 asRa3,aRas,anRas,agRas,agRa (C1)(~,83,410.0aw)D(~,g3,~) 3)辩论结果 由于卫星自身的限制，次日下午5：00后卫星s1 依据攻击关系构成的导向图如图2所示。 不应该被用于目标g,的观测，因为那时卫星会马上

表 ２ 卫星可操控时间列表 Ｔａｂｌｅ ２ Ｌｉｓｔ ｏｆ ｓａｔｅｌｌｉｔｅ’ｓ ｔｉｍｅ ｗｉｄｏｗ ｆｏｒ ｏｐｅｒａｔｉｏｎ 卫星 操作时间窗口 Ｓ １ ［１５：４０ １５：５５］ａｍ ［１７：１０ １７：３０］ ａｍ Ｓ ２ ［９：４０ ９：５５］ａｍ ［１１：００ １１：１０］ ａｍ 把观测任务视为 ＣＯＡ 问题，考察以下类型偏好。 １）目标的价值有优先级，用户在白天要首先观 察到优先级高的目标。 ２）根据地面测控站的要求，对同一个目标执行 观测动作时，希望使用能提供较长可见弧段的卫星。 ３）考虑到卫星的能量储备，在进行观测时，优先 考虑姿态机动小、耗费能量少的卫星。 ４）对同一目标成像，用户喜欢高分辨率的图像。 ５）对某目标成像时，用户希望首先得到低分辨 率图像，再获得高分辨率图像，方便图像判读。 ６）从用户角度，监视运动目标具有更高优先级。 ７）从传输信道的稳定性来讲，希望使用距离测 控站距离近的卫星进行观测。 ８）进行森林火灾目标的检测时，更希望使用配 备红外相机的卫星。 下面根据以上规则给出各偏好的形式化表达。 目标优先级偏好：目标 ｇ １的优先级最高，而目 标 ｇ ２的优先级最低，因而有 （Ｐ１） （ ～ ，ｇ１ ， ～ ）▷ｇ（ ～ ，＃， ～ ） （Ｐ２） （ ～ ，＃， ～ ）▷ｇ（ ～ ，ｇ２ ， ～ ） 可用测控弧段偏好： （Ｐ３） （ｓ２ ， ～ ， ～ ） ≻ｓ（¬ ｓ２ ， ～ ， ～ ） 姿态机动能量偏好： （Ｐ４） （ｓ１ ，ｇ３ ， ～ ） ≻ｇ（ｓ１ ，ｇ１ ， ～ ） 成像分辨率偏好： （Ｐ５） （ｓ１ ， ～ ， ～ ） ≻ｓ（¬ ｓ１ ， ～ ， ～ ） 低、高分辨率切换顺序偏好： （Ｐ６） （ｓ２ ， ～ ， ～ ）▷ｓ（ｓ１ ， ～ ， ～ ） 移动目标监视偏好： （Ｐ７） （ ～ ，ｇ１ ， ～ ） ≻ｇ（ ～ ，¬ ｇ１ ， ～ ） 信道传输质量偏好： （Ｐ８） Θ ≻ｓ（ｓ１ ，ｇ１ ， ～ ） 输出帧率偏好： （Ｐ９） （ｓ２ ，ｇ１ ， ～ ） ≻ｓ（¬ ｓ２ ，ｇ１ ， ～ ） 成像谱段偏好：目标 ｇ ２ 处于森林火险等级较 高的区域，优先考虑使用红外相机观测，即 （Ｐ１０） （ｓ２ ，ｇ２ ， ～ ） ≻０ ｓ（¬ ｓ２ ， ～ ， ～ ） 下面给出 ３ 个约束关系。 据气象预报，上午 １０ 时前目标 ｇ ３被云层覆盖，不能被观测到。 （Ｃ１） （ ～ ，ｇ３ ，ｔ １０：００ＡＭ ）▷０ ｔ （ ～ ，ｇ３ ， ～ ） 由于卫星自身的限制，次日下午 ５：００ 后卫星 ｓ １ 不应该被用于目 标 ｇ ３的观测，因为那时卫星会马上 进入阴影区，在下一个任务之前不能充分充电。 （Ｃ２） （ｓ１ ，ｇ３ ，＃）▷０ ｔ （ｓ１ ，ｇ３ ，ｔ ５：００ＰＭ ） 现在可以综合 （Ｐ１） ～ （Ｐ１０） 和 （Ｃ１） ～ （Ｃ２） ， 执行辩论并完成任务级 ＣＯＡ 方案。 从偏好构建论据时，还需要确定偏好自身的优 先级。 在本案例中，根据偏好的提出者来确定 Ａｒａｎｋ 这个值。 卫星运营商、卫星设计方和用户提出的偏 好关系将分别有 ３、２ 和 １ 的优先级。 当然，从约束 构造的论据都具有 ０ 的优先级。 １）论据构建 （Ｐ１）： ａ１ ＝ [▷，（ ～ ，ｇ１ ， ～ ），（ ～ ，＃， ～ ），１] （Ｐ２） ： ａ２ ＝ [▷，（ ～ ，＃ ～ ），（ ～ ，ｇ２ ， ～ ），１] （Ｐ３） ： ａ３ ＝ ≻，（ｓ２ ， ～ ， ～ ），（¬ ｓ [ ２ ， ～ ， ～ ），３] （Ｐ４） ： ａ４ ＝ ≻，（ｓ１ ，ｇ３ ， ～ ），（ｓ [ １ ，ｇ１ ， ～ ），２] （Ｐ５） ： ａ５ ＝ ≻，（ｓ１ ， ～ ， ～ ），（¬ ｓ [ １ ， ～ ， ～ ），１] （Ｐ６） ： ａ６ ＝ ▷，（ｓ２ ，＃， ～ ），（ｓ [ １ ，＃， ～ ），１] （Ｐ７） ： ａ７ ＝ [≻，（ ～ ，ｇ１ ， ～ ），（ ～ ，¬ ｇ１ ， ～ ），１] （Ｐ８） ： ａ８ ＝ ≻，Θ，（ｓ [ １ ，ｇ１ ， ～ ），１] （Ｐ９） ： ａ９ ＝ ≻，（ｓ２ ，ｇ１ ， ～ ），（¬ ｓ [ ２ ，ｇ１ ， ～ ），１] （Ｐ１０） ： ａ１２ ＝ ≻，（ｓ２ ，ｇ２ ，＃），（¬ ｓ [ ２ ，ｇ２ ，＃），０] （Ｃ１） ： ａ１０ ＝ ▷，（ ～， ～，ｔ １０：００ＡＭ），（ ～，ｇ３，¬ ｔ [ １０：００ＡＭ），０] （Ｃ２） ： ａ１４ ＝ ▷，（ｓ１ ，ｇ３ ，＃），（ｓ１ ，ｇ３ ，ｔ [ ５：００ＰＭ ），０] ２）攻击关系构建 记 Ａ≻ ＝ ａ３ ，ａ４ ，ａ５ ，ａ７ ，ａ８ ，ａ９ ，ａ１２ { } Ａ▷ ＝ ａ１ ，ａ２ ，ａ６ ，ａ１０ ，ａ１４ { } Ａ▷ 内部没有冲突， 因此， Ｅｘ▷ ＝ Ａ▷ ． 而对于 Ａ≻ 则 需要执行一个辩论过程以获得 Ｅｘ≻ 。 论据 ａ５ 拆分为 ａ １ ５ ＝ ≻，（ｓ１ ，¬ ｇ２ ， ～ ），（¬ ｓ [ １ ，¬ ｇ２ ， ～ ），１] ａ ２ ５ ＝ ≻，（ｓ１ ，ｇ２ ， ～ ），（¬ ｓ [ １ ，ｇ２ ， ～ ），１] ａ ３ ５ ＝ ［≻，（ｓ１ ，¬ （ｇ１ ｜ ｇ２ ）， ～ ）， （¬ ｓ１ ，¬ （ｇ１ ｜ ｇ２ ）， ～ ），１］ 论据 ａ７ 拆分为 ａ １ ７ ＝ ≻，（ｓ１ ，ｇ１ ， ～ ），（ｓ [ １ ，¬ ｇ１ ， ～ ），１] ａ ２ ７ ＝ ≻，（ｓ２ ，ｇ１ ， ～ ），（ｓ [ ２ ，¬ ｇ１ ， ～ ），１] 得到攻击关系如下： ａ５Ｒａ３ ， ａ７Ｒａ４ ， ａ１２Ｒａ ２ ５ ， ａ９Ｒａ １ ５ ， ａ８Ｒａ １ ７ ３）辩论结果 依据攻击关系构成的导向图如图 ２ 所示。 ·５５６· 智 能 系 统 学 报 第 ９ 卷

第5期 王炎娟，等：任务级行动序列问题中的定性偏好研究 ·557. 选择H、中的优势节点（攻击其他节点，而自己 不被攻击的节点)构造集合U, a 4, U3 图2攻击关系导向图 （52,~,~Xs2,g1,~）(51,g3,~)(~,82,#) Fig.2 Directed graph on attack relation 山1，山2，山3，山4等元素实际上均对应了多个三元组，相 A,的首选扩展容易从图中获得： 互之间有交叉重合的部分，这些三元组被认为是真 Ex>=(a3,as,a,as,ao,an 4)构造有向图H 正能够起作用的部分，定义为U,: H,绘制如图3。 (62）(g） u2 u3 (1g） (g,#) (s2,81,#)(51,83,#)（52,82,#) (#,,） (⑤，g）(52g）（S18Sg1-）(S1g） 5)构造有向图H。 图3有向图H、 基于EX。和U,构造H。如图4所示。 Fig.3 Directed graph H (g一） (5n#,）（,ta0d (g,#) (51g, G1g)）(g制6g判 (8） (③，#） (omm) ⊙ ⊙ ⊙ 图4有向图Hp Fig.4 Directed graph H 6)构造C0A方案 这意味着，操作员应该使用卫星$2在观测g2之 接下来的求解步骤是通过合并节点获得动作序 前观测g1:同时，应使用卫星s1观测目标g3,时间在 列片段。对于虚线左侧的节点，尝试从虚线右侧找 上午10时至下午5时之间。 到匹配的节点，使得一个攻击链上相同位置的通配 结合操控时间窗口分布，得到了调度方案如下 符可以由相同的确定元素替代。例如， 所示： (~,81,~),(~,g2,~)处于同一个攻击链中，而 (s2,81,[9:40,9:50]am）→ 在右侧，(52，g1,~),(52,g2,~)能够与他们匹 (s2,g2,[11:00,11:10]am）→ 配；而下一个攻击链(s2,#,~),(s1,#,~)则不能 (s1,83,15:40,15:55]) 从右侧找到一组元素来匹配与之匹配。最后得到匹 在解决过程中可以看到从模糊语义经过标定和 配结果如图5所示。 校正逐步细化的过程。 下面将本文的ARG-C0A算法与文献[21]中的 (Sigifiomam) WS数值优化算法进行对比。 (S2g1,#) 基于本文的背景案例生成3个测试集，分别包 (518,#) 含不同数目的约束和偏好，如表3所示。由于WSI 算法不支持时序关系求解，因此偏好只设定静态偏 (⑤2-8，#) 好。使用W$算法时，把偏好也作为约束统一求 (S:8lsmm 解，以无冲突约束和偏好的强度值之和为指标函数 图5动作序列匹配结果图 值，指标大于0的约束/偏好集合均为可行解。在同 Fig.5 Matched directed graph 样的处理平台上进行对比计算，结果如表3所示

图 ２ 攻击关系导向图 Ｆｉｇ．２ Ｄｉｒｅｃｔｅｄ ｇｒａｐｈ ｏｎ ａｔｔａｃｋ ｒｅｌａｔｉｏｎ Ａ≻ 的首选扩展容易从图中获得： Ｅｘ≻ ＝ ａ３ ，ａ４ ，ａ ２ ７ ，ａ８ ，ａ９ ，ａ１２ { } ４）构造有向图 Ｈ≻ Ｈ≻ 绘制如图 ３。 图 ３ 有向图 Ｈ≻ Ｆｉｇ．３ Ｄｉｒｅｃｔｅｄ ｇｒａｐｈ Ｈ≻ 选择 Ｈ≻ 中的优势节点（攻击其他节点，而自己 不被攻击的节点）构造集合 Ｕ≻ ｕ１ ｕ２ ｕ３ ｕ４ （ｓ２ ， ～ ， ～ ）（ｓ２ ，ｇ１ ， ～ ）（ｓ１ ，ｇ３ ， ～ ） （ ～ ，ｇ２ ，＃） ｕ１ ，ｕ２ ，ｕ３ ，ｕ４ 等元素实际上均对应了多个三元组，相 互之间有交叉重合的部分，这些三元组被认为是真 正能够起作用的部分，定义为 Ｕ ～ ≻ ： ｕ ～ ２ ｕ ～ ３ ｕ ～ ４ （ｓ２ ，ｇ１ ，＃） （ｓ１ ，ｇ３ ，＃） （ｓ２ ，ｇ２ ，＃） ５）构造有向图 Ｈ▷ 基于 ＥＸ▷ 和 Ｕ ～ ≻ 构造 Ｈ▷ 如图 ４ 所示。 图 ４ 有向图 Ｈ▷ Ｆｉｇ．４ Ｄｉｒｅｃｔｅｄ ｇｒａｐｈ Ｈ▷ ６）构造 ＣＯＡ 方案 接下来的求解步骤是通过合并节点获得动作序 列片段。 对于虚线左侧的节点，尝试从虚线右侧找 到匹配的节点，使得一个攻击链上相同位置的通配 符 可 以 由 相 同 的 确 定 元 素 替 代。 例 如， ( ～ ，ｇ１ ， ～ ) ，( ～ ，ｇ２ ， ～ ) 处于同一个攻击链中，而 在右侧， ｓ( ２ ，ｇ１ ， ～ ) ， ｓ( ２ ，ｇ２ ， ～ ) 能够与他们匹 配；而下一个攻击链 ｓ( ２ ，＃， ～ ) ， ｓ( １ ，＃， ～ ) 则不能 从右侧找到一组元素来匹配与之匹配。 最后得到匹 配结果如图 ５ 所示。 图 ５ 动作序列匹配结果图 Ｆｉｇ．５ Ｍａｔｃｈｅｄ ｄｉｒｅｃｔｅｄ ｇｒａｐｈ 这意味着，操作员应该使用卫星 ｓ２ 在观测 ｇ２ 之 前观测 ｇ１ ；同时，应使用卫星 ｓ１ 观测目标 ｇ３ ，时间在 上午 １０ 时至下午 ５ 时之间。 结合操控时间窗口分布，得到了调度方案如下 所示： （ｓ２ ，ｇ１ ，［９：４０，９：５０］ａｍ） → （ｓ２ ，ｇ２ ，［１１：００，１１：１０］ａｍ） → （ｓ１ ，ｇ３ ，［１５：４０，１５：５５］） 在解决过程中可以看到从模糊语义经过标定和 校正逐步细化的过程。 下面将本文的 ＡＲＧ⁃ＣＯＡ 算法与文献［ ２１ ］ 中的 ＷＳＩ 数值优化算法进行对比。 基于本文的背景案例生成 ３ 个测试集，分别包 含不同数目的约束和偏好，如表 ３ 所示。 由于 ＷＳＩ 算法不支持时序关系求解，因此偏好只设定静态偏 好。 使用 ＷＳＩ 算法时，把偏好也作为约束统一求 解，以无冲突约束和偏好的强度值之和为指标函数 值，指标大于 ０ 的约束／ 偏好集合均为可行解。 在同 样的处理平台上进行对比计算，结果如表 ３ 所示。 第 ５ 期 王炎娟，等：任务级行动序列问题中的定性偏好研究 ·５５７·

.558. 智能系统学报 第9卷 表3ARG-COA和WSI算法时的数值仿真对比 Table 3 Comparing the simulating results of ARG-COA and WSI 测试集1 测试集2 测试集3 约束数目 3 5 9 偏好数目 10 12 16 冲突数目 6 9 2 可行解数目 4 2 1 WSI获得可行解的时间/s 0.9.1.4 1.6.1.8 3.1 ARG-COA获得可行解的时间/s 1.1 1.2 1.3 WSI对约束/偏好的遍历次数 149 403 1413 ARG-COA对约束/偏好的遍历次数 91 153 325 仿真计算结果表明： 4 结束语 1)随着约束/偏好数目的增加，获得可行解的时 间越来越长，但是WSI算法的时间增量更大。 本文对任务级的COA问题开展研究，针对其中 2)WSI算法比ARG-COA算法对约束/偏好进 的定性偏好进行了建模，闭关完成了COA方案生成 行遍历次数要多，而且随着冲突数目的增加，两者的 算法设计，以及在偏好与约束关系存在不一致性时 差距越来越大。 如何通过非单调推理获得最大一致性，最后形成了 3)WSI算法能够更早获得可行解，但是所有的 任务级COA问题求解的两阶段算法。辩论工具的 可行解是要依次获得的，这是由搜索过程决定的：而 使用，一方面实现了偏好解耦，算法的设计具有了领 ARG-COA算法则是同步获得全部可行解的，花费较 域无关的推广能力：另一个潜在好处是能够提供用 少时间。 户交互参与规划过程的可能性。本文的研究结果是 前文指出，定性偏好也并不能替代定量偏好，同 以定量优化为主的传统任务规划研究的有效补充。 理，基于辩论的算法并不能替代定量优化算法。 将来的研究将着力于与传统定量规划算法的结合， ARG-COA算法所获得的可行解，都是用户满意度意 并逐步把任务级COA向动作级COA扩展，形成用 义下的最优解。在算法1步骤2的3)子步骤，可能 户满意度和资源约束满足均达到最优、具有用户交 会在一些节点处出现分支，此时任何一个分支都对 互能力的COA规划方法。 应一个可行解，ARG-COA算法并不能从中选出惟一 参考文献： 的最优解，而这种“优中选优”是W$I优化算法可以 胜任的。因此，两种算法的相互结合可达到互补的 [1]FERGUSON R W,RASCH R A,TURMEL W,et al.Quali- 效果：首先使用辩论算法排除确实不可能有解的偏 tative spatial interpretation of course-of-action diagrams [C] 好集合，然后再应用定量优化算法完成COA规划。 //Proceedings of the National Conference on Artificial Intel- ligence.AAAI Press,2000:1119-1120. 这将是后续研究关注的重点。 [2]FORBUS K D,USHER J,CHAPMAN V.Sketching for mil- 计算辩论工具不但能够给出推理结论，还能够 itary courses of action diagrams [C]//Proceedings of the 把推理过程展现给用户，因而进行COA的软件智能 8th International Conference on Intelligent user Interfaces. 体可以向用户表明，哪一个偏好被排除了，或者由于 ACM.2003:61-68. 用户过分强调哪一个偏好导致COA无法求解。由 [3]SLOVIC P.The construction of preference[J].American 于用户往往不是专业人员，对领域COA认识存在不 Psychologist.1995.50(5):364-371. 足，提出的偏好很可能不尽合理。当辩论过程给出 [4]BIENVENU M,MCILRAITH S.Qualitative dynamical pref- 反馈意见时，用户可以对自己的需求进行调整。如 erences in the situation calculus[C]//Multidisciplinary IJ- 案例中用户提出的某种偏好优先级默认为1，在发 CAl-05 Workshop on Advances in Preference Handling. 2005:30-35. 生冲突时可能会排除掉一些优先级为2，或3的关 [5]BIENVENU M,FRITZ C,MCILRAITH S A.Planning with 系，这可能是用户意料之外的，用户可以把自己偏好 qualitative temporal preferences [C]//Proceedings of the 的优先级更改为2或3，重新进行推理，从而允许某 10th International Conference on Principles of Knowledge 些动作。这种人机交互式的推理将是未来研究方向 Representation and Reasoning (KR).Lake District,UK, 之一。 2006:134-144

表 ３ ＡＲＧ⁃ＣＯＡ 和 ＷＳＩ 算法时的数值仿真对比 Ｔａｂｌｅ ３ Ｃｏｍｐａｒｉｎｇ ｔｈｅ ｓｉｍｕｌａｔｉｎｇ ｒｅｓｕｌｔｓ ｏｆ ＡＲＧ⁃ＣＯＡ ａｎｄ ＷＳＩ 测试集 １ 测试集 ２ 测试集 ３ 约束数目 ３ ５ ９ 偏好数目 １０ １２ １６ 冲突数目 ６ ９ １２ 可行解数目 ４ ２ １ ＷＳＩ 获得可行解的时间／ ｓ ０．９，１．４ １．６，１．８ ３．１ ＡＲＧ⁃ＣＯＡ 获得可行解的时间／ ｓ １．１ １．２ １．３ ＷＳＩ 对约束／ 偏好的遍历次数 １４９ ４０３ １ ４１３ ＡＲＧ⁃ＣＯＡ 对约束／ 偏好的遍历次数 ９１ １５３ ３２５ 仿真计算结果表明： １）随着约束／ 偏好数目的增加，获得可行解的时 间越来越长，但是 ＷＳＩ 算法的时间增量更大。 ２） ＷＳＩ 算法比 ＡＲＧ⁃ＣＯＡ 算法对约束／ 偏好进 行遍历次数要多，而且随着冲突数目的增加，两者的 差距越来越大。 ３）ＷＳＩ 算法能够更早获得可行解，但是所有的 可行解是要依次获得的，这是由搜索过程决定的；而 ＡＲＧ⁃ＣＯＡ 算法则是同步获得全部可行解的，花费较 少时间。 前文指出，定性偏好也并不能替代定量偏好，同 理，基于辩论的算法并不能替代定量优化算法。 ＡＲＧ⁃ＣＯＡ 算法所获得的可行解，都是用户满意度意 义下的最优解。 在算法 １ 步骤 ２ 的 ３）子步骤，可能 会在一些节点处出现分支，此时任何一个分支都对 应一个可行解，ＡＲＧ⁃ＣＯＡ 算法并不能从中选出惟一 的最优解，而这种“优中选优”是 ＷＳＩ 优化算法可以 胜任的。 因此，两种算法的相互结合可达到互补的 效果：首先使用辩论算法排除确实不可能有解的偏 好集合，然后再应用定量优化算法完成 ＣＯＡ 规划。 这将是后续研究关注的重点。 计算辩论工具不但能够给出推理结论，还能够 把推理过程展现给用户，因而进行 ＣＯＡ 的软件智能 体可以向用户表明，哪一个偏好被排除了，或者由于 用户过分强调哪一个偏好导致 ＣＯＡ 无法求解。 由 于用户往往不是专业人员，对领域 ＣＯＡ 认识存在不 足，提出的偏好很可能不尽合理。 当辩论过程给出 反馈意见时，用户可以对自己的需求进行调整。 如 案例中用户提出的某种偏好优先级默认为 １，在发 生冲突时可能会排除掉一些优先级为 ２，或 ３ 的关 系，这可能是用户意料之外的，用户可以把自己偏好 的优先级更改为 ２ 或 ３，重新进行推理，从而允许某 些动作。 这种人机交互式的推理将是未来研究方向 之一。 ４ 结束语 本文对任务级的 ＣＯＡ 问题开展研究，针对其中 的定性偏好进行了建模，闭关完成了 ＣＯＡ 方案生成 算法设计，以及在偏好与约束关系存在不一致性时 如何通过非单调推理获得最大一致性，最后形成了 任务级 ＣＯＡ 问题求解的两阶段算法。 辩论工具的 使用，一方面实现了偏好解耦，算法的设计具有了领 域无关的推广能力；另一个潜在好处是能够提供用 户交互参与规划过程的可能性。 本文的研究结果是 以定量优化为主的传统任务规划研究的有效补充。 将来的研究将着力于与传统定量规划算法的结合， 并逐步把任务级 ＣＯＡ 向动作级 ＣＯＡ 扩展，形成用 户满意度和资源约束满足均达到最优、具有用户交 互能力的 ＣＯＡ 规划方法。 参考文献： ［１］ＦＥＲＧＵＳＯＮ Ｒ Ｗ， ＲＡＳＣＨ Ｒ Ａ， ＴＵＲＭＥＬ Ｗ， ｅｔ ａｌ． Ｑｕａｌｉ⁃ ｔａｔｉｖｅ ｓｐａｔｉａｌ ｉｎｔｅｒｐｒｅｔａｔｉｏｎ ｏｆ ｃｏｕｒｓｅ⁃ｏｆ⁃ａｃｔｉｏｎ ｄｉａｇｒａｍｓ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌ⁃ ｌｉｇｅｎｃｅ． ＡＡＡＩ Ｐｒｅｓｓ， ２０００： １１１９⁃１１２０． ［２］ＦＯＲＢＵＳ Ｋ Ｄ， ＵＳＨＥＲ Ｊ， ＣＨＡＰＭＡＮ Ｖ． Ｓｋｅｔｃｈｉｎｇ ｆｏｒ ｍｉｌ⁃ ｉｔａｒｙ ｃｏｕｒｓｅｓ ｏｆ ａｃｔｉｏｎ ｄｉａｇｒａｍｓ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ８ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ ｕｓｅｒ Ｉｎｔｅｒｆａｃｅｓ． ＡＣＭ， ２００３： ６１⁃６８． ［３］ ＳＬＯＶＩＣ Ｐ． Ｔｈｅ ｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ ｐｒｅｆｅｒｅｎｃｅ ［ Ｊ］． Ａｍｅｒｉｃａｎ Ｐｓｙｃｈｏｌｏｇｉｓｔ， １９９５， ５０（５）： ３６４⁃３７１． ［４］ＢＩＥＮＶＥＮＵ Ｍ， ＭＣＩＬＲＡＩＴＨ Ｓ．Ｑｕａｌｉｔａｔｉｖｅ ｄｙｎａｍｉｃａｌ ｐｒｅｆ⁃ ｅｒｅｎｃｅｓ ｉｎ ｔｈｅ ｓｉｔｕａｔｉｏｎ ｃａｌｃｕｌｕｓ［Ｃ］ ／ ／ Ｍｕｌｔｉｄｉｓｃｉｐｌｉｎａｒｙ ＩＪ⁃ ＣＡＩ⁃０５ Ｗｏｒｋｓｈｏｐ ｏｎ Ａｄｖａｎｃｅｓ ｉｎ Ｐｒｅｆｅｒｅｎｃｅ Ｈａｎｄｌｉｎｇ． ２００５： ３０⁃３５ ． ［５］ＢＩＥＮＶＥＮＵ Ｍ， ＦＲＩＴＺ Ｃ， ＭＣＩＬＲＡＩＴＨ Ｓ Ａ． Ｐｌａｎｎｉｎｇ ｗｉｔｈ ｑｕａｌｉｔａｔｉｖｅ ｔｅｍｐｏｒａｌ ｐｒｅｆｅｒｅｎｃｅｓ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １０ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐｒｉｎｃｉｐｌｅｓ ｏｆ Ｋｎｏｗｌｅｄｇｅ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ａｎｄ Ｒｅａｓｏｎｉｎｇ （ ＫＲ）． Ｌａｋｅ Ｄｉｓｔｒｉｃｔ， ＵＫ， ２００６： １３４⁃１４４． ·５５８· 智 能 系 统 学 报 第 ９ 卷

第5期 王炎娟，等：任务级行动序列问题中的定性偏好研究 ·559. [6]BLOM M.Arguments and actions:decoupling preference [17]DELGRANDE J P,SCHAUB T,TOMPITS H.Domain- and planning through argumentation [D].Melbourne:Uni- specific preferences for causal reasoning and planning versity of Melbourne,2011:15-60. [C]//Proceedings of the Ninth Intemational Conference [7]ROSSI F,VENABLE K B.Uncertainty in soft temporal con- on Principles of Knowledge Representation and Reasoning straint problems:a general framework and controllability al- (KR.2004).AAAI Press,2004:673-682. gorithms for the fuzzy case[]].Journal of Artificial Intelli- [18]DELGRANDE J P,SCHAUB T,TOMPITS H.A general gence Research,2006,27(1):617-674. framework for expressing preferences in causal reasoning [8]吴江，黄登仕.多属性决策中区间数偏好信息的一致化 and planning[J].Journal of Logic and Computation,2007, 方法[J].系统工程理论方法应用，2003,12(4)：359- 17(5):871-907. 362. [19]DUNG P M.On the acceptability of arguments and its fun- The uniform methods for interval number preference informa- damental role in nonmonotonic reasoning,logic program- tion in multi-attribute decision making[].Systems Engi- ming and n-person games J].Artificial Intelligence, neering-Theory Methodology Applications,2003,12 (4): 1995,77(2):321-357. 359-.362 [20]TRIHARJANTO R H,HASBI W,WIDIPAMINTO A,et [9]张凤华.模糊决策中决策偏好的情景依赖性[D].重庆： al.LAPAN-TUBSAT:micro-satellite platform for surveil- 西南大学，2010：30-55. lance remote sensing [C]//Proceedings of the 4S Sym- Zhang Fenghua.The scenario-dependent of decision prefer- posium:Small Satellites,Systems and Services.La Ro- ence in fuzzy decision[D].Chongqing:Southwest University. chelle,France:2004:66-70. 2010:30-55. [21]贺川，朱晓敏，邱涤珊.面向应急成像观测任务的多星 [10]BRAFMAN R,DOMSHLAK C.Preference handling-an 协同调度方法[J].系统工程与电子技术，2012,34(4)： introductory tutorial[J].AI Magazine,2009,30(1):58- 726-731. 95. HE Chuan,ZHU Xiaomin,QIU Dishan.Cooperative [11]MARINELLIA F,NOCELLAB S,ROSSIB F,et al.A La- scheduling method of multi-satellites for imaging reconnais- grangian heuristic for satellite range scheduling with re. sance in emergency condition[J].Systems Engineering and source constraints[J].Computers Operations Research, Electronics,2012,34(4):726-731. 2011,38(11):1572-1583. 作者简介： [12]KNIGHT R,SMITH B.Optimally solving nadir observation 王炎娟，女，1984年生，博士研究生， scheduling problems[C]//Proceedings of the 8th Interna- 主要研究方向为人工智能、信息系统与智 tional Symposium on Artifical Intelligence,Robotics and 能决策。 Automation in Space(i-SAIRAS2005).Munich,Germany: 2005:33-41. [13]GIUNCHIGLIA E,MARATEA M.Planning as satisfiability with preferences [C]//National Conference on Artificial 姚莉，女，1965年生，教授，博士生导 Intelligence.Boston:MIT Press,2007,22(2):987-992. 师，主要研究方向为人工智能、知识管理、 [14]BADALONI S,FALDA M,GIACOMIN M.Solving tempo- 信息系统与智能决策、计算辩论技术。 ral over-constrained problems using fuzzy techniques [J]. Journal of Intelligent and Fuzzy Systems,2007,18(2): 255-265. 刘斌，男，1989年生，博士研究生，主 [15]BENCH-CAPON T J M,DUNNE P E.Argumentation in 要研究方向为人工智能、信息系统与智 artificial intelligence[J].Artificial Intelligence,2007,171 能决策。 (10-15):619-641. [16]BOUTILIER C,BRAFMAN R I,DOMSHLAK C,et al. CP-nets:a tool for representing and reasoning with condi- tional ceteris paribus preference statements[].Journal of Artificial Intelligence Research,2004,21:135-191

［６］ ＢＬＯＭ Ｍ． Ａｒｇｕｍｅｎｔｓ ａｎｄ ａｃｔｉｏｎｓ： ｄｅｃｏｕｐｌｉｎｇ ｐｒｅｆｅｒｅｎｃｅ ａｎｄ ｐｌａｎｎｉｎｇ ｔｈｒｏｕｇｈ ａｒｇｕｍｅｎｔａｔｉｏｎ ［Ｄ］． Ｍｅｌｂｏｕｒｎｅ： Ｕｎｉ⁃ ｖｅｒｓｉｔｙ ｏｆ Ｍｅｌｂｏｕｒｎｅ， ２０１１： １５⁃６０． ［７］ＲＯＳＳＩ Ｆ， ＶＥＮＡＢＬＥ Ｋ Ｂ． Ｕｎｃｅｒｔａｉｎｔｙ ｉｎ ｓｏｆｔ ｔｅｍｐｏｒａｌ ｃｏｎ⁃ ｓｔｒａｉｎｔ ｐｒｏｂｌｅｍｓ： ａ ｇｅｎｅｒａｌ ｆｒａｍｅｗｏｒｋ ａｎｄ ｃｏｎｔｒｏｌｌａｂｉｌｉｔｙ ａｌ⁃ ｇｏｒｉｔｈｍｓ ｆｏｒ ｔｈｅ ｆｕｚｚｙ ｃａｓｅ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉ⁃ ｇｅｎｃｅ Ｒｅｓｅａｒｃｈ， ２００６， ２７（１）： ６１７⁃６７４． ［８］吴江， 黄登仕． 多属性决策中区间数偏好信息的一致化 方法［Ｊ］．系统工程理论方法应用， ２００３， １２ （ ４）： ３５９⁃ ３６２． Ｔｈｅ ｕｎｉｆｏｒｍ ｍｅｔｈｏｄｓ ｆｏｒ ｉｎｔｅｒｖａｌ ｎｕｍｂｅｒ ｐｒｅｆｅｒｅｎｃｅ ｉｎｆｏｒｍａ⁃ ｔｉｏｎ ｉｎ ｍｕｌｔｉ⁃ａｔｔｒｉｂｕｔｅ ｄｅｃｉｓｉｏｎ ｍａｋｉｎｇ ［ Ｊ］． Ｓｙｓｔｅｍｓ Ｅｎｇｉ⁃ ｎｅｅｒｉｎｇ⁃ Ｔｈｅｏｒｙ Ｍｅｔｈｏｄｏｌｏｇｙ Ａｐｐｌｉｃａｔｉｏｎｓ， ２００３， １２ （ ４）： ３５９⁃３６２ ［９］张凤华． 模糊决策中决策偏好的情景依赖性［Ｄ］． 重庆： 西南大学，２０１０：３０⁃５５． Ｚｈａｎｇ Ｆｅｎｇｈｕａ． Ｔｈｅ ｓｃｅｎａｒｉｏ⁃ｄｅｐｅｎｄｅｎｔ ｏｆ ｄｅｃｉｓｉｏｎ ｐｒｅｆｅｒ⁃ ｅｎｃｅ ｉｎ ｆｕｚｚｙ ｄｅｃｉｓｉｏｎ［Ｄ］． Ｃｈｏｎｇｑｉｎｇ：Ｓｏｕｔｈｗｅｓｔ Ｕｎｉｖｅｒｓｉｔｙ． ２０１０： ３０⁃５５． ［１０］ ＢＲＡＦＭＡＮ Ｒ， ＤＯＭＳＨＬＡＫ Ｃ． Ｐｒｅｆｅｒｅｎｃｅ ｈａｎｄｌｉｎｇ—ａｎ ｉｎｔｒｏｄｕｃｔｏｒｙ ｔｕｔｏｒｉａｌ［Ｊ］． ＡＩ Ｍａｇａｚｉｎｅ， ２００９， ３０（１）： ５８⁃ ９５． ［１１］ＭＡＲＩＮＥＬＬＩＡ Ｆ， ＮＯＣＥＬＬＡＢ Ｓ， ＲＯＳＳＩＢ Ｆ， ｅｔ ａｌ． Ａ Ｌａ⁃ ｇｒａｎｇｉａｎ ｈｅｕｒｉｓｔｉｃ ｆｏｒ ｓａｔｅｌｌｉｔｅ ｒａｎｇｅ ｓｃｈｅｄｕｌｉｎｇ ｗｉｔｈ ｒｅ⁃ ｓｏｕｒｃｅ ｃｏｎｓｔｒａｉｎｔｓ［ Ｊ］． Ｃｏｍｐｕｔｅｒｓ ＆ Ｏｐｅｒａｔｉｏｎｓ Ｒｅｓｅａｒｃｈ， ２０１１， ３８ （１１）： １５７２⁃１５８３． ［１２］ＫＮＩＧＨＴ Ｒ， ＳＭＩＴＨ Ｂ． Ｏｐｔｉｍａｌｌｙ ｓｏｌｖｉｎｇ ｎａｄｉｒ ｏｂｓｅｒｖａｔｉｏｎ ｓｃｈｅｄｕｌｉｎｇ ｐｒｏｂｌｅｍｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ８ｔｈ Ｉｎｔｅｒｎａ⁃ ｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ａｒｔｉｆｉｃａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ， Ｒｏｂｏｔｉｃｓ ａｎｄ Ａｕｔｏｍａｔｉｏｎ ｉｎ Ｓｐａｃｅ（ｉ⁃ＳＡＩＲＡＳ２００５）． Ｍｕｎｉｃｈ， Ｇｅｒｍａｎｙ： ２００５： ３３⁃４１． ［１３］ＧＩＵＮＣＨＩＧＬＩＡ Ｅ， ＭＡＲＡＴＥＡ Ｍ． Ｐｌａｎｎｉｎｇ ａｓ ｓａｔｉｓｆｉａｂｉｌｉｔｙ ｗｉｔｈ ｐｒｅｆｅｒｅｎｃｅｓ ［ Ｃ］ ／ ／ Ｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ． Ｂｏｓｔｏｎ： ＭＩＴ Ｐｒｅｓｓ， ２００７， ２２（２）： ９８７⁃９９２． ［１４］ＢＡＤＡＬＯＮＩ Ｓ， ＦＡＬＤＡ Ｍ， ＧＩＡＣＯＭＩＮ Ｍ． Ｓｏｌｖｉｎｇ ｔｅｍｐｏ⁃ ｒａｌ ｏｖｅｒ⁃ｃｏｎｓｔｒａｉｎｅｄ ｐｒｏｂｌｅｍｓ ｕｓｉｎｇ ｆｕｚｚｙ ｔｅｃｈｎｉｑｕｅｓ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｔ ａｎｄ Ｆｕｚｚｙ Ｓｙｓｔｅｍｓ， ２００７， １８ （ ２）： ２５５⁃２６５． ［１５］ ＢＥＮＣＨ⁃ＣＡＰＯＮ Ｔ Ｊ Ｍ， ＤＵＮＮＥ Ｐ Ｅ． Ａｒｇｕｍｅｎｔａｔｉｏｎ ｉｎ ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ［ Ｊ］．Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００７， １７１ （１０⁃１５）： ６１９⁃６４１． ［１６］ ＢＯＵＴＩＬＩＥＲ Ｃ， ＢＲＡＦＭＡＮ Ｒ Ｉ， ＤＯＭＳＨＬＡＫ Ｃ， ｅｔ ａｌ． ＣＰ⁃ｎｅｔｓ： ａ ｔｏｏｌ ｆｏｒ ｒｅｐｒｅｓｅｎｔｉｎｇ ａｎｄ ｒｅａｓｏｎｉｎｇ ｗｉｔｈ ｃｏｎｄｉ⁃ ｔｉｏｎａｌ ｃｅｔｅｒｉｓ ｐａｒｉｂｕｓ ｐｒｅｆｅｒｅｎｃｅ ｓｔａｔｅｍｅｎｔｓ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ Ｒｅｓｅａｒｃｈ， ２００４， ２１： １３５⁃１９１． ［１７］ ＤＥＬＧＲＡＮＤＥ Ｊ Ｐ， ＳＣＨＡＵＢ Ｔ， ＴＯＭＰＩＴＳ Ｈ． Ｄｏｍａｉｎ⁃ ｓｐｅｃｉｆｉｃ ｐｒｅｆｅｒｅｎｃｅｓ ｆｏｒ ｃａｕｓａｌ ｒｅａｓｏｎｉｎｇ ａｎｄ ｐｌａｎｎｉｎｇ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｎｉｎｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐｒｉｎｃｉｐｌｅｓ ｏｆ Ｋｎｏｗｌｅｄｇｅ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ａｎｄ Ｒｅａｓｏｎｉｎｇ （ＫＲ．２００４）．ＡＡＡＩ Ｐｒｅｓｓ， ２００４： ６７３⁃６８２． ［１８］ＤＥＬＧＲＡＮＤＥ Ｊ Ｐ， ＳＣＨＡＵＢ Ｔ， ＴＯＭＰＩＴＳ Ｈ． Ａ ｇｅｎｅｒａｌ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｅｘｐｒｅｓｓｉｎｇ ｐｒｅｆｅｒｅｎｃｅｓ ｉｎ ｃａｕｓａｌ ｒｅａｓｏｎｉｎｇ ａｎｄ ｐｌａｎｎｉｎｇ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｌｏｇｉｃ ａｎｄ Ｃｏｍｐｕｔａｔｉｏｎ， ２００７， １７（５）： ８７１⁃９０７． ［１９］ＤＵＮＧ Ｐ Ｍ． Ｏｎ ｔｈｅ ａｃｃｅｐｔａｂｉｌｉｔｙ ｏｆ ａｒｇｕｍｅｎｔｓ ａｎｄ ｉｔｓ ｆｕｎ⁃ ｄａｍｅｎｔａｌ ｒｏｌｅ ｉｎ ｎｏｎｍｏｎｏｔｏｎｉｃ ｒｅａｓｏｎｉｎｇ， ｌｏｇｉｃ ｐｒｏｇｒａｍ⁃ ｍｉｎｇ ａｎｄ ｎ⁃ｐｅｒｓｏｎ ｇａｍｅｓ ［ Ｊ ］． Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ， １９９５， ７７ （２）： ３２１⁃３５７． ［２０］ＴＲＩＨＡＲＪＡＮＴＯ Ｒ Ｈ， ＨＡＳＢＩ Ｗ， ＷＩＤＩＰＡＭＩＮＴＯ Ａ， ｅｔ ａｌ． ＬＡＰＡＮ⁃ＴＵＢＳＡＴ： ｍｉｃｒｏ⁃ｓａｔｅｌｌｉｔｅ ｐｌａｔｆｏｒｍ ｆｏｒ ｓｕｒｖｅｉｌ⁃ ｌａｎｃｅ ＆ ｒｅｍｏｔｅ ｓｅｎｓｉｎｇ ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ４Ｓ Ｓｙｍ⁃ ｐｏｓｉｕｍ： Ｓｍａｌｌ Ｓａｔｅｌｌｉｔｅｓ， Ｓｙｓｔｅｍｓ ａｎｄ Ｓｅｒｖｉｃｅｓ． Ｌａ Ｒｏ⁃ ｃｈｅｌｌｅ， Ｆｒａｎｃｅ： ２００４： ６６⁃７０． ［２１］贺川， 朱晓敏， 邱涤珊． 面向应急成像观测任务的多星 协同调度方法［Ｊ］．系统工程与电子技术， ２０１２， ３４（４）： ７２６⁃７３１． ＨＥ Ｃｈｕａｎ， ＺＨＵ Ｘｉａｏｍｉｎ， ＱＩＵ Ｄｉｓｈａｎ． Ｃｏｏｐｅｒａｔｉｖｅ ｓｃｈｅｄｕｌｉｎｇ ｍｅｔｈｏｄ ｏｆ ｍｕｌｔｉ⁃ｓａｔｅｌｌｉｔｅｓ ｆｏｒ ｉｍａｇｉｎｇ ｒｅｃｏｎｎａｉｓ⁃ ｓａｎｃｅ ｉｎ ｅｍｅｒｇｅｎｃｙ ｃｏｎｄｉｔｉｏｎ［ Ｊ］．Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｅｌｅｃｔｒｏｎｉｃｓ， ２０１２， ３４ （４）： ７２６⁃７３１． 作者简介： 王炎娟，女，１９８４ 年生，博士研究生， 主要研究方向为人工智能、信息系统与智 能决策。 姚莉，女，１９６５ 年生，教授，博士生导 师，主要研究方向为人工智能、知识管理、 信息系统与智能决策、计算辩论技术。 刘斌，男，１９８９ 年生，博士研究生，主 要研究方向为人工智能、信息系统与智 能决策。 第 ５ 期 王炎娟，等：任务级行动序列问题中的定性偏好研究 ·５５９·