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