第三章 任务分解与调度.pptVIP

史忠植 智能科学的研究 第三章 任务分解与调度 本章内容 3.1 任务分解 3.1.1任务分解的形式化描述 3.1.1任务分解的形式化描述 3.1.1任务分解的形式化描述 3.1.1任务分解的形式化描述 3.1.1任务分解的形式化描述 3.1.1任务分解的形式化描述 3.1.1任务分解的形式化描述 3.1.2任务分解的启发式算法 3.1.2任务分解的启发式算法 3.2 任务分配 3.3 并行调度 3.3.1 基于环结构的并行调度算法 3.3.1 基于环结构的并行调度算法 3.3.2 环结构的并行调度算法示例 3.3.2 环结构的并行调度算法示例 3.3.2 环结构的并行调度算法示例 3.4 子任务的协调及结果集成 1.任务分解 2.任务分配 3.并行调度 4.子任务执行时的协调及结果集成 任务分解的主要功能是将提交的任务分解成多个具有尽可能高并行度的子任务，并决定由哪些Agent在何时执行它们。经典的算法有： McCornock的基于聚簇的方法； Niizuna和Kitahachi的基于状态和等价关系的方法。 任务分解问题定义为如下五元组: K,A,E,I,G 其中： K为问题的知识集； A为操作集； E为执行单元集 I为初始条件集； G为目标集。 于是，可定义任务的可行最优分解为下列条件的实现： ①所有的操作在执行前都行到了其必要的输入信息； ②G中所有知识都将得到； ③所耗费的通信和执行开销最小。 另外，定义一个执行开销函数ExecFun与通信开销函数CommFun: ExecFun: A,E?R CommFun: E,E ?R 其中R为实数集。 并定义如下二进制向量： Mjq=1若操作j的输入信息中包含知识q; Djq=1 若操作j的输入信息中包含知识q; Zik=1 若由执行单元k来完成操作i; Xi=1 若在完成任务的过程中执行了操作i; Vi=1 若信息i是完成所必需的; Yij=1 若操作j的输入信息可由操作i的输出信息提供; Wik=1 若执行单元i与执行单元k通信。 根据以上的定义可知： ①每个操作最多可被执行一次，即： ?i(∑Zik≤1) ....(1) k ?i(∑Zik=Xi) ....(2) k ②所有操作的输出信息必须覆盖目标集，即： ?i(∑DjiXj≥Vi) ....(3) j ③每个操作仅当其输入信息存在时才能执行，即： ?q ?j(∑DiqYij≥MjqXj) ....(4) i ④所执行的操作序列必须是可行的，即： ?i ?j(Rij≥Yij) ....(5a) ?i ?j ?k(Rik+ Rkj ≤ Rij +1) ....(5b) ?i (Rii= 0) ....(5c) ⑤仅当需要传递信息时，才进行通信，即： ?i ?j ?k ?l(Zik+ Zjl + Yij ≤ Wkl +2) ....(6) ⑥完成任务的开销为： ∑∑ZijExecFun(Ei,Ej)+ ∑∑WijCommFun(Ei,Ej) i j i j ....(7) 结论：任务分解问题就是在满足(1)-(6)的同时使(7)之值最小的问题。 ①定义Ti为操作，INP(Ti)为操作Ti所需要的输入信息，OUT(Ti)为操作Ti的输出信息，INP0为初始输入信息。OUT为完成任务所获得的输出信息。令Beginners={Ti:INP(Ti)≤INP0}，Actions[1..N]为操作集数组。 ②如果Beginners为空集，同不存在可行的操作集，算法结束。否则从Beginners中选择一操作T0，置Beginners= Beginners- {T0}，定义输入信息集INP=INP0∪OUT(T0),INP’=INP0，令Actions[1]={T0},M=1。 ③置M=M+1,Actions[M]={Ti:INP(Ti)INP∩INP(Ti) ≮INP’},INP’=INP，INP=INP ∪ ∪OUT(Ti)(Ti∈Actions[M]。 ④如果INP≥OUT,则执行第⑤步；否则，如果（ ∪ Actions[i] A，则执行第3步，否则执行第2步。 ⑤定义操作集Result为空集，临时工作集Wanted=OUT。 ⑥重复执行如下操作： 取Wanted的第一个元素K0， 按顺序搜寻Actions,找出操作Ti:OUT(Ti) ≥{K0} 置Wanted=Wanted-{K0},Result=Result∪{Ti}。