多Agent系统任务分配的研究
- 格式：pdf
- 大小：1.51 MB
- 文档页数：3
λ = ⎜ ∑ ∑ rij ⎟ j =1 i =1
⎛ ⎝
n m
⎞ ⎠
−3
(6)
(1)
目标函数 为实现任务分配机制，必须建立任务分配的目标函数， 指导 Agent 与任务进行组合优化，求解最优任务分配方案。 根据任务分配机制基于性能和代价之间达到平衡的设计目 标，将性能影响因子与任务分配代价模型相结合来构建目标 函数。 根据任务分配代价函数和性能影响因子，建立如式 (7)所 示的目标函数： 3.3
概述
2
传统任务分配问题可描述为：有 n 个任务需要分配给 n 个处理机去完成，系统中任意处理机都有处理任意任务的能 力，但每个任务只能分配给 1 个处理机，且每个处理机只能 处理 1 个任务；不同的分配花费不同的代价。在这种设定下， 任务与处理机之间是一对一的分配模式。任务分配问题的目 标是找到 1 种最优分配方案，使其所花费的代价最小。 MAS 任务分配问题可描述为： 有 m 个任务需要分配给 n 个 Agent 完成，每个任务可以分配给多个 Agent 处理，并对 结果进行冲突消解，得到最终结果，且每个 Agent 允许接受 在其能力范围之内的多个任务。因此，MAS 采用的是种多对 多的任务分配模式。该分配模式一方面可以综合利用多个 Agent 的求解能力，提高系统的处理性能；另一方面，多对 多的任务分配模式与传统一对一的分配模式相比，会产生一 定的重复计算，导致更大的分配代价。本文提出的任务分配 机制的设计思想综合考虑了 MAS 系统性能和分配代价两方 面的影响，以寻求性能和代价之间的一个平衡。 不失一般性，设 1 个任务可以有多个 Agent 中标，但为 避免中标 Agent 数量过多，引起不必要的资源开销，设定 1 个中标 Agent 上限阈值 u ，同时，允许每个 Agent 能同时接 受多个任务，为避免 Agent 的任务列表过大而引起任务并发 执行时产生瓶颈，设定一个任务列表上限阈值 v ，与传统任 务分配单纯考虑分配代价最小的设计思想不同，本文的设计 思想是综合考虑分配代价和 MAS 的性能，寻找代价与性能 之间的平衡点。据此，本文讨论的任务分配机制的设计目标
Research on Task Allocation in Multi-Agent System
YAN Jian-feng, LI Wei-hua, LIU Ming
(School of Computer, Northwestern Polytechnical University, Xi’an 710072) 【Abstract】 Aiming at the task allocation problem in Multi-Agent System(MAS), a novel many-to-many allocation mode between task and Agent is put forward and the corresponding mathematics model is established. The performance influence factor is defined, and the objective function is deduced to conduct optimization of task allocation. This method is proved effective through a practical case. 【Key words】Multi-Agent System(MAS); task allocation; objective function
cij = ω1 × tij + ω2 × ∑ λijk
k =1 s
任务分配问题的数学模型和目标函数
Agent 不能完成任务，那么不需要计算对应分配代价。 (5)任务分配代价函数 建立问题的分配代价矩阵后，给出任务分配代价函数如 式 (5)所示：
C ( x) = ∑ ∑ dij
j =1 i =1 n m
n m ⎛ n m ⎞ F ( x) = λ × C ( x) = ∑ ∑ dij × ⎜ ∑ ∑ rij ⎟ j =1 i =1 ⎝ j =1 i=1 ⎠ −3
其中， tij 为时间资源开销； λijk 为其他资源开销； s 为其他资 源开销的数量； ω1 , ω2 为对应权重，且 ω1 + ω2 = 1 ，专家可 以根据不同的系统应用需求来调整 ω1 , ω2 的值， 并约定若该 Agent 不能完成某类任务，则 cij = N 。 (2)局部代价矩阵 设某问题分解成 n 个任务，共有 m 个 Agent 是潜在任务 中标者，从全局代价矩阵中提取与该问题相关的元素构成局 部代价矩阵，具体方式为从全局代价矩阵的 p 行 (Agent)中抽 取 m 行， q 列 ( 任务 ) 中抽取 n 列，则 m 行与 n 列交叉的元素 构成局部代价矩阵。 (3)无约束分配矩阵和约束分配矩阵 对局部代价矩阵中的元素作一定变换即可构成无约束分 配矩阵 Rm×n ，变换方式为：若 cij = N ，则 rij = N ；若 cij 不等 于 N ，则令 rij = 1 。 在满足约束条件的前提下，对无约束分配矩阵 Rm×n 中的 每个元素进一步变换，可构建约束分配矩阵 Rm×n =( rij )。分配 问题的约束条件 u , v 可以表述为
严建峰，李伟华，刘 明
(西北工业大学计算机学院，西安 710072) 摘 要：针对多 Agent 系统中存在的任务分配问题，提出一种任务与 Agent 之间多对多的分配模式，建立相应的任务分配模型，定义任务 分配中的性能影响因子，并推导出进行任务分配优化的目标函数，通过一个实际案例，验证该方法的有效性。 关键词：多 Agent 系统；任务分配；目标函数
i =1
(7)
建立 MAS 任务分配的数学模型和目标函数以后，应用 各类方法对任务分配矩阵进行组合优化并达到性能与代价之 间的平衡的判断依据即为 F ( x) 最小。
4
设已建立某 MAS 的全局代价矩阵，某问题被分解成 5 个任务，系统中有 5 个潜在 Agent，设其对应的局部代价矩 阵如式 (8)所示：
基金项目：国家部委基金资助项目 (51315080404, 9140A1705020 6HK03) 作者简介：严建峰(1978－)，男，博士研究生，主研方向：智能故障 诊断系统；李伟华，教授、博士生导师；刘 明，硕士研究生 收稿日期：2008-12-30 E-mail：yjf@
第 35 卷 Vol.35第 11 期 No.11
计 算 机 工 程 Computer Engineering
文章编号：1000—3428(2009)11—0221—02 文献标识码：A
2009 年 6 月 June 2009
中图分类号：TP18
·人工智能及识别技术·
多 Agent 系统任务分配的研究
⎛1 ⎜2 ⎜ C5×5 = ⎜ N ⎜ ⎜1 ⎜N ⎝
5 N 6 3 3 N N N 9 4
实例分析
⎟ ⎟ N 1⎟ ⎟ 1 N⎟ ⎟ 2 N⎠
3 5
N
8⎞
(8)
对式 (8) 进行变换，则该问题的无约束分配矩阵如式 (9) 所示：
⎛1 ⎜1 ⎜ R5×5 = ⎜ N ⎜ ⎜1 ⎜N ⎝
1 N 1 1 1 N N
MAS 任务分配问题
—221—
是：在中标 Agent 数量不超出阈值 u ，并且任务列表不超出 阈值 v 的前提下，对同一任务尽可能综合利用多种 Agent 方 法来提高 MAS 的处理性能，并使任务执行的综合代价最小。
(4)分配代价矩阵 根据具体问题的约束分配矩阵和局部代价矩阵，可直接 建 立 该 问 题 对 应 的 分 配 代 价 矩 阵 Dmn=( dij ) ， 其 中 ， 元 素
dij = rij × cij ，并约定若 rij 或 cij 的值为 N ，则 dij = N ，即如果
3
根据 MAS 任务分配的定义，给出任务分配的数学模型， 设计任务分配代价函数来求解任务分配代价，引入性能影响 因子来评估多对多分配模式对 MAS 的性能提升，并结合任 务分配代价函数和性能影响因子， 给出任务分配的目标函数。 任务分配模型 不同 Agent 执行任务的代价有差异，为衡量并对比这种 差异，需要求解系统中每个 Agent 对每个任务类型的求解代 价。用矩阵的方式来表示求解代价，矩阵的行表示 Agent ， 矩阵的列表示任务类型，矩阵的元素表示 Agent 求解该任务 的代价，称为全局代价矩阵。基于全局代价矩阵，可以构建 任务分配中的 3 个数学模型：先从全局代价矩阵中提取与具 体问题相关的元素来构建问题的代价矩阵，称为局部代价矩 阵；其次根据局部代价矩阵，构建无约束分配矩阵，并进一 步构建约束分配矩阵；最后根据约束分配矩阵和局部代价矩 阵，构建该问题对应的分配代价矩阵。 (1)全局代价矩阵 设系统中共有 p 个 Agent、 q 个任务类型且 Agent i 对任 3.1 可构建代价矩阵 C p×q =( cij )， 其中，cij 务 j 的完成代价为 cij ， 包括时间、系统软硬件开销等资源。考虑到在各类代价中， 时间代价是个重要因素，在各类 MAS 中的重要性可能有所 不同，因此，将 cij 表述为
∑ rij ≤ u
∑ rij ≤ v
j =1 n
m
(2) (3)
⎟ ⎟ N N 1⎟ ⎟ 1 1 N⎟ ⎟ 1 1 N⎠
1 1
5 5 i =1 j =1
N
1⎞
(9)
设约束条件为 u ≤ 2 , v ≤ 2 ，即 ∑ rij ≤ 2 ; ∑ rij
1
任务分配问题最早出现在各类生产、计划和柔性制造系 统中，是种典型的组合优化问题。由于传统任务分配问题的 目标是充分利用分布式系统多处理机的并行性，因此将一个 问题 (problem)分解成多个子任务 (task)，通过子任务的并行执 行使得问题能在最短的时间内完成。在这类系统中的任务分 配大多基于以下的设定：系统所有处理机都能无差别地处理 所有任务，即对于同一个任务，所有处理机都应返回相同的 结果，因此，同一任务只须分配给一个执行者。任务对处理 机是独占的， 处理机在完成现在任务之前不会接受新的任务。 这种设定在很多应用环境，如车辆运输调度、指派问题、多 处理器并行处理、网格计算等应用领域是适用的。 与传统任务分配问题相比，多 Agent 系统 (Multi-Agent System, MAS)的任务分配有其特殊性， 主要体现在 2 个方面： (1)对同一问题采用不同方法设计的 Agent 的处理结果可能存 在不一致 [1] ，因此，为提高任务的处理精度，在 MAS 中将 一个任务分配给多个 Agent 进行并行求解，将不同 Agent 求 解的结果进行冲突消解 [2]是种自然的方法； (2)在 MAS 中允 许 Agent 同时接受多个任务，形成对应的任务列表，从而充 分利用 MAS 的并行求解能力。 有效的任务分配是 MAS 中任务处理的前提和基础，直 接影响 MAS 的性能，是 MAS 的热点研究领域。文献 [3]提出 基于合同网的任务列表法并以多机器人为对象进行实验与分 析，有效解决了动态环境下多机器人的实时任务分配问题。 文献 [4] 基于集覆盖理论，将任务分配问题转换成集覆盖问 题。文献 [5]提出基于信息粒化理论，分为主体、任务粒化阶 段和粒内规划阶段 2 个阶段完成任务分配。文献 [6-7]利用计 算智能方法强大的寻优能力进行任务分配机制设计。然而这 些工作主要基于传统任务分配问题的设定进行研究，未全面 考虑 MAS 任务分配的特殊性。本文给出一种 MAS 任务分配 方法，并用一个算例验证了算法的有效性。
⎛ ⎝
n m
⎞ ⎠
−3
(6)
(1)
目标函数 为实现任务分配机制，必须建立任务分配的目标函数， 指导 Agent 与任务进行组合优化，求解最优任务分配方案。 根据任务分配机制基于性能和代价之间达到平衡的设计目 标，将性能影响因子与任务分配代价模型相结合来构建目标 函数。 根据任务分配代价函数和性能影响因子，建立如式 (7)所 示的目标函数： 3.3
概述
2
传统任务分配问题可描述为：有 n 个任务需要分配给 n 个处理机去完成，系统中任意处理机都有处理任意任务的能 力，但每个任务只能分配给 1 个处理机，且每个处理机只能 处理 1 个任务；不同的分配花费不同的代价。在这种设定下， 任务与处理机之间是一对一的分配模式。任务分配问题的目 标是找到 1 种最优分配方案，使其所花费的代价最小。 MAS 任务分配问题可描述为： 有 m 个任务需要分配给 n 个 Agent 完成，每个任务可以分配给多个 Agent 处理，并对 结果进行冲突消解，得到最终结果，且每个 Agent 允许接受 在其能力范围之内的多个任务。因此，MAS 采用的是种多对 多的任务分配模式。该分配模式一方面可以综合利用多个 Agent 的求解能力，提高系统的处理性能；另一方面，多对 多的任务分配模式与传统一对一的分配模式相比，会产生一 定的重复计算，导致更大的分配代价。本文提出的任务分配 机制的设计思想综合考虑了 MAS 系统性能和分配代价两方 面的影响，以寻求性能和代价之间的一个平衡。 不失一般性，设 1 个任务可以有多个 Agent 中标，但为 避免中标 Agent 数量过多，引起不必要的资源开销，设定 1 个中标 Agent 上限阈值 u ，同时，允许每个 Agent 能同时接 受多个任务，为避免 Agent 的任务列表过大而引起任务并发 执行时产生瓶颈，设定一个任务列表上限阈值 v ，与传统任 务分配单纯考虑分配代价最小的设计思想不同，本文的设计 思想是综合考虑分配代价和 MAS 的性能，寻找代价与性能 之间的平衡点。据此，本文讨论的任务分配机制的设计目标
Research on Task Allocation in Multi-Agent System
YAN Jian-feng, LI Wei-hua, LIU Ming
(School of Computer, Northwestern Polytechnical University, Xi’an 710072) 【Abstract】 Aiming at the task allocation problem in Multi-Agent System(MAS), a novel many-to-many allocation mode between task and Agent is put forward and the corresponding mathematics model is established. The performance influence factor is defined, and the objective function is deduced to conduct optimization of task allocation. This method is proved effective through a practical case. 【Key words】Multi-Agent System(MAS); task allocation; objective function
cij = ω1 × tij + ω2 × ∑ λijk
k =1 s
任务分配问题的数学模型和目标函数
Agent 不能完成任务，那么不需要计算对应分配代价。 (5)任务分配代价函数 建立问题的分配代价矩阵后，给出任务分配代价函数如 式 (5)所示：
C ( x) = ∑ ∑ dij
j =1 i =1 n m
n m ⎛ n m ⎞ F ( x) = λ × C ( x) = ∑ ∑ dij × ⎜ ∑ ∑ rij ⎟ j =1 i =1 ⎝ j =1 i=1 ⎠ −3
其中， tij 为时间资源开销； λijk 为其他资源开销； s 为其他资 源开销的数量； ω1 , ω2 为对应权重，且 ω1 + ω2 = 1 ，专家可 以根据不同的系统应用需求来调整 ω1 , ω2 的值， 并约定若该 Agent 不能完成某类任务，则 cij = N 。 (2)局部代价矩阵 设某问题分解成 n 个任务，共有 m 个 Agent 是潜在任务 中标者，从全局代价矩阵中提取与该问题相关的元素构成局 部代价矩阵，具体方式为从全局代价矩阵的 p 行 (Agent)中抽 取 m 行， q 列 ( 任务 ) 中抽取 n 列，则 m 行与 n 列交叉的元素 构成局部代价矩阵。 (3)无约束分配矩阵和约束分配矩阵 对局部代价矩阵中的元素作一定变换即可构成无约束分 配矩阵 Rm×n ，变换方式为：若 cij = N ，则 rij = N ；若 cij 不等 于 N ，则令 rij = 1 。 在满足约束条件的前提下，对无约束分配矩阵 Rm×n 中的 每个元素进一步变换，可构建约束分配矩阵 Rm×n =( rij )。分配 问题的约束条件 u , v 可以表述为
严建峰，李伟华，刘 明
(西北工业大学计算机学院，西安 710072) 摘 要：针对多 Agent 系统中存在的任务分配问题，提出一种任务与 Agent 之间多对多的分配模式，建立相应的任务分配模型，定义任务 分配中的性能影响因子，并推导出进行任务分配优化的目标函数，通过一个实际案例，验证该方法的有效性。 关键词：多 Agent 系统；任务分配；目标函数
i =1
(7)
建立 MAS 任务分配的数学模型和目标函数以后，应用 各类方法对任务分配矩阵进行组合优化并达到性能与代价之 间的平衡的判断依据即为 F ( x) 最小。
4
设已建立某 MAS 的全局代价矩阵，某问题被分解成 5 个任务，系统中有 5 个潜在 Agent，设其对应的局部代价矩 阵如式 (8)所示：
基金项目：国家部委基金资助项目 (51315080404, 9140A1705020 6HK03) 作者简介：严建峰(1978－)，男，博士研究生，主研方向：智能故障 诊断系统；李伟华，教授、博士生导师；刘 明，硕士研究生 收稿日期：2008-12-30 E-mail：yjf@
第 35 卷 Vol.35第 11 期 No.11
计 算 机 工 程 Computer Engineering
文章编号：1000—3428(2009)11—0221—02 文献标识码：A
2009 年 6 月 June 2009
中图分类号：TP18
·人工智能及识别技术·
多 Agent 系统任务分配的研究
⎛1 ⎜2 ⎜ C5×5 = ⎜ N ⎜ ⎜1 ⎜N ⎝
5 N 6 3 3 N N N 9 4
实例分析
⎟ ⎟ N 1⎟ ⎟ 1 N⎟ ⎟ 2 N⎠
3 5
N
8⎞
(8)
对式 (8) 进行变换，则该问题的无约束分配矩阵如式 (9) 所示：
⎛1 ⎜1 ⎜ R5×5 = ⎜ N ⎜ ⎜1 ⎜N ⎝
1 N 1 1 1 N N
MAS 任务分配问题
—221—
是：在中标 Agent 数量不超出阈值 u ，并且任务列表不超出 阈值 v 的前提下，对同一任务尽可能综合利用多种 Agent 方 法来提高 MAS 的处理性能，并使任务执行的综合代价最小。
(4)分配代价矩阵 根据具体问题的约束分配矩阵和局部代价矩阵，可直接 建 立 该 问 题 对 应 的 分 配 代 价 矩 阵 Dmn=( dij ) ， 其 中 ， 元 素
dij = rij × cij ，并约定若 rij 或 cij 的值为 N ，则 dij = N ，即如果
3
根据 MAS 任务分配的定义，给出任务分配的数学模型， 设计任务分配代价函数来求解任务分配代价，引入性能影响 因子来评估多对多分配模式对 MAS 的性能提升，并结合任 务分配代价函数和性能影响因子， 给出任务分配的目标函数。 任务分配模型 不同 Agent 执行任务的代价有差异，为衡量并对比这种 差异，需要求解系统中每个 Agent 对每个任务类型的求解代 价。用矩阵的方式来表示求解代价，矩阵的行表示 Agent ， 矩阵的列表示任务类型，矩阵的元素表示 Agent 求解该任务 的代价，称为全局代价矩阵。基于全局代价矩阵，可以构建 任务分配中的 3 个数学模型：先从全局代价矩阵中提取与具 体问题相关的元素来构建问题的代价矩阵，称为局部代价矩 阵；其次根据局部代价矩阵，构建无约束分配矩阵，并进一 步构建约束分配矩阵；最后根据约束分配矩阵和局部代价矩 阵，构建该问题对应的分配代价矩阵。 (1)全局代价矩阵 设系统中共有 p 个 Agent、 q 个任务类型且 Agent i 对任 3.1 可构建代价矩阵 C p×q =( cij )， 其中，cij 务 j 的完成代价为 cij ， 包括时间、系统软硬件开销等资源。考虑到在各类代价中， 时间代价是个重要因素，在各类 MAS 中的重要性可能有所 不同，因此，将 cij 表述为
∑ rij ≤ u
∑ rij ≤ v
j =1 n
m
(2) (3)
⎟ ⎟ N N 1⎟ ⎟ 1 1 N⎟ ⎟ 1 1 N⎠
1 1
5 5 i =1 j =1
N
1⎞
(9)
设约束条件为 u ≤ 2 , v ≤ 2 ，即 ∑ rij ≤ 2 ; ∑ rij
1
任务分配问题最早出现在各类生产、计划和柔性制造系 统中，是种典型的组合优化问题。由于传统任务分配问题的 目标是充分利用分布式系统多处理机的并行性，因此将一个 问题 (problem)分解成多个子任务 (task)，通过子任务的并行执 行使得问题能在最短的时间内完成。在这类系统中的任务分 配大多基于以下的设定：系统所有处理机都能无差别地处理 所有任务，即对于同一个任务，所有处理机都应返回相同的 结果，因此，同一任务只须分配给一个执行者。任务对处理 机是独占的， 处理机在完成现在任务之前不会接受新的任务。 这种设定在很多应用环境，如车辆运输调度、指派问题、多 处理器并行处理、网格计算等应用领域是适用的。 与传统任务分配问题相比，多 Agent 系统 (Multi-Agent System, MAS)的任务分配有其特殊性， 主要体现在 2 个方面： (1)对同一问题采用不同方法设计的 Agent 的处理结果可能存 在不一致 [1] ，因此，为提高任务的处理精度，在 MAS 中将 一个任务分配给多个 Agent 进行并行求解，将不同 Agent 求 解的结果进行冲突消解 [2]是种自然的方法； (2)在 MAS 中允 许 Agent 同时接受多个任务，形成对应的任务列表，从而充 分利用 MAS 的并行求解能力。 有效的任务分配是 MAS 中任务处理的前提和基础，直 接影响 MAS 的性能，是 MAS 的热点研究领域。文献 [3]提出 基于合同网的任务列表法并以多机器人为对象进行实验与分 析，有效解决了动态环境下多机器人的实时任务分配问题。 文献 [4] 基于集覆盖理论，将任务分配问题转换成集覆盖问 题。文献 [5]提出基于信息粒化理论，分为主体、任务粒化阶 段和粒内规划阶段 2 个阶段完成任务分配。文献 [6-7]利用计 算智能方法强大的寻优能力进行任务分配机制设计。然而这 些工作主要基于传统任务分配问题的设定进行研究，未全面 考虑 MAS 任务分配的特殊性。本文给出一种 MAS 任务分配 方法，并用一个算例验证了算法的有效性。
