多编组协同任务分配模型及DLS-QGA算法求解_多智能体任务分配求解资源-CSDN文库

179 浏览量 2021-01-14 13:40:29 上传评论收藏 249KB PDF 举报

资源推荐

资源详情

资源评论

第 29 卷第 9 期

Vol. 29 No. 9

控制与决策

Control and Decision

2014 年 9 月

Sep. 2014

多编组协同任务分配模型及 DLS-QGA 算法求解

文章编号: 1001-0920 (2014) 09-1562-07 DOI: 10.13195/j.kzyjc.2013.0876

万路军

1a,1b

, 姚佩阳

, 周翔翔

, 税冬东

(1. 空军工程大学 a. 信息与导航学院，b. 空管领航学院，西安 710077；2. 95616 部队，成都 611531)

摘要: 为解决多智能体编组协同任务分配问题, 定义任务、智能体编组和相关的分配过程变量, 建立以最高任务执

行效率为目标的数学模型. 在问题模型中设计考虑资源损耗的编组资源能力更新机制, 提出用于求解该模型的动态

列表规划和量子遗传算法的混合任务分配算法, 使用动态列表规划选择处理的任务, 利用量子遗传算法为选定任务

分配最合适编组. 最后通过算例表明, 所提出的方法在解决时序逻辑任务分配时能够得到更优更稳定的方案.

关键词: 智能体编组；任务分配；动态列表规划；量子遗传算法

中图分类号: TP391；TP237.5 文献标志码: A

Cooperative task allocation methods in multiple groups using DLS-QGA

WAN Lu-jun

1a,1b

, YAO Pei-yang

, ZHOU Xiang-xiang

, SHUI Dong-dong

(1a. College of Information and Navigation，1b. College of Air Control and Navigation，Air Force Engineering

University，Xi’an 710077，China；2. Unit 95616 of PLA，Chengdu 611531，China．Correspondent：WAN Lu-jun,

E-mail：pandawlj@126.com)

Abstract: To solve the cooperative task allocation of multiple agent groups, the task, agents group and process variables

are deﬁned. The mathematical model in pursuit of maximal task execute efﬁciency is established. The wastage of group

resource capability is introduced in the process of problem modeling. A hybrid approach to the problem based on dynamic

list scheduling(DLS) and the quantum genetic algorithm(QGA) is proposed. In the DLS-QGA algorithm, DLS is used to

select the task needed to dispose, then QGA is used to select the best group for the selected task. Finally, the superiority and

applicability of this approach are illuminated by the simulation of campaign assumption, and the scheme can be better and

more steadily in task allocation with time-logic.

Key words: agent groups；task allocation；dynamic list scheduling；quantum genetic algorithm

0 引引引言言言

现代战场上具有信息系统的空中作战智能体

(ACA) 应用得越来越广泛, 但单个 ACA 所能发挥的

作战功能有限, 需要多个 ACA 形成混合集群执行任

务, 以发挥更佳的综合作战效能

[1-3]

. 混合集群执行作

战任务时, 通常根据任务属性特征形成多个编组, 将

编组视为一个整体, 各编组分别执行属性不相一致的

一项或多项任务. 所要执行的复杂序列任务间具有一

定的时序关系, 多编组协同任务分配便是将编组合理

地配置到存在时序逻辑关系的任务中, 这属于时间

扩展型的任务分配

[4-5]

, 是 NP 完全问题. 对于该类型

问题, 若直接使用智能优化算法求解则无法保证满足

任务时序关系约束; 精确方法面向较大规模的任务

集和编组集时, 无法在有效时间内实现优化求解; 启

发式方法可以避免上述不足, 是解决该类问题的有

效途径, 动态列表规划 (DLS)

[6]

作为一种最常用的启

发式策略, 具有求解效率高、可以获得最优解或满意

解的优点. 在基于 DLS 的扩展启发式算法中, 多维动

态列表规划 (MDLS) 算法

[7]

和多优先级列表动态规划

(MPLDS) 算法

[8]

最为常用. 前者存在优先权函数设定

不够合理的问题, 两种算法的局部搜索策略都是基

于贪心策略的, 无法保证以稳定的高概率寻到最优

任务分配方案. 针对 MDLS 算法和 MPLDS 算法存在

的不足, 文献 [9] 设计了 DLS 和遗传算法 (GA) 的分配

策略, 使用全局搜索 GA 为选定的任务分配最佳的平

台 (编组), 提高了任务分配搜索结果趋近于最优的概

率, 但传统 GA 寻优时收敛速度慢, 使得该方法每次局

部任务编组匹配耗时较长. 量子遗传算法 (QGA)

[10]

收稿日期: 2013-07-01；修回日期: 2013-09-17.

基金项目: 国家自然科学基金项目(61273048).

作者简介: 万路军(1986−), 男, 博士, 讲师, 从事指挥控制理论与方法的研究；姚佩阳(1960−), 男, 教授, 博士生导师, 从

事指挥控制理论与技术等研究.

第 9 期

万路军等: 多编组协同任务分配模型及 DLS-QGA 算法求解

1563

是在遗传算法中引入量子计算的概念, 当应用于 0/1

背包问题时, QGA 相比于 GA 在收敛速度和全局搜索

能力上具有明显的优势

[11-12]

. 因此, 围绕多编组任务

分配问题, 需要寻找一种新的满足任务时序关系的全

局优化机制, 既能寻到最优分配结果, 又可以相对减

少任务与编组匹配时耗费的时间.

基于以上分析, 本文首先建立空中多作战智能体

编组协同任务分配数学模型, 然后针对所建模型具有

时间扩展的特点, 设计以 DLS 算法为主的基本求解框

架, 嵌套 QGA 为选定任务选择最优编组的多编组协

同任务分配策略.

1 多多多编编编组组组协协协同同同任任任务务务分分分配配配的的的问问问题题题描描描述述述

1.1 问问问题题题背背背景景景和和和基基基本本本概概概念念念

由多个属性基本一致的 ACA 形成编组, 考虑编

组差异即为不同 ACA 的位置、距离、移动速度、功

能和执行能力水平等差异, 多编组协同任务分配

(MGCTA) 便是对多个序列任务进行快速任务 ACA

编组匹配. 首先对任务和智能体编组进行描述, 给出

任务和 ACA 编组有效匹配为目的的属性.

任务 (𝑇 ): 由使命任务分解得到所需要执行的任

务序列. 记包含 𝑁 个任务的任务集为 𝑇 = {𝑇

𝑖

}(𝑖 = 1,

2, ⋅ ⋅ ⋅ , 𝑁), 每个任务 𝑇

𝑖

有如下属性: 任务处理时间 dt

𝑖

= ft

𝑖

− st

𝑖

, 其中 ft

𝑖

为任务 𝑇

𝑖

的结束时间, st

𝑖

为任务 𝑇

𝑖

的开始时间; 任务 𝑇

𝑖

的地理坐标位置 TP

𝑖

= (𝑥

𝑖

, 𝑦

𝑖

);

任务的资源需求向量 𝑅

𝑖

= {𝑅

𝑖𝑙

} (𝑙 = 1, 2, ⋅ ⋅ ⋅ , 𝐿), 𝑅

𝑖𝑙

为成功处理任务 𝑇

𝑖

所需的第 𝑙 种类型的资源能力值,

𝐿 为资源能力类型的数量.

ACA 编组 (AG): 有人和无人作战智能体组成的

编组, 是资源能力的载体. 记包含 𝑀 个编组的 ACA 编

组集为 AG = {AG

𝑚

} (𝑚 = 1, 2, ⋅ ⋅ ⋅ , 𝑀 ), 每个编组

𝑚

具有如下属性: 编组 AG

𝑚

的平均移动速率为

𝑣

𝑚

; AG

𝑚

具备的初始资源能力矢量 GR

𝑚

= {GR

𝑚𝑙

为 AG

𝑚

所具备的第 𝑙 种类型的资源能力值;

ACA 编组地理位置变量 (𝑥

(𝑚)

, 𝑦

(𝑚)

) 为在战场各作

战任务区域进行迁移并执行任务的编组, 在整个任务

过程中不断变化的地理位置.

1.2 任任任务务务分分分配配配过过过程程程的的的变变变量量量定定定义义义

任务分配过程的变量定义如下:

1) 编组-任务的分配变量 𝜑

𝑖𝑚

. 若 AG

𝑚

分配给 𝑇

𝑖

则 𝜙

𝑖𝑚

= 1 , 否则 𝜙

𝑖𝑚

= 0.

2) 编组在任务间的迁移变量 𝑥

𝑖𝑗𝑚

. 若 AG

𝑚

在执

行 𝑇

𝑖

后分配给 𝑇

𝑗

, 则 𝑥

𝑖𝑗𝑚

= 1, 否则 𝑥

𝑖𝑗𝑚

= 0 . 编组在

同一任务间不存在迁移关系, 当 𝑖 = 𝑗 时, 𝑥

𝑖𝑗𝑚

= 0 .

3) 任务执行序列变量 𝑒

𝑖𝑗

. 若 𝑇

𝑖

必须在 𝑇

𝑗

开始执

行前完成, 则 𝑒

𝑖𝑗

= 1, 否则 𝑒

𝑖𝑗

= 0 .

4) 任务集 𝑇 的持续时间是从第 1 个执行任务的

起始时间到最后 1 个任务的结束时间. 若 𝑇 中第 1 个

任务的起始时间为 min

𝑇

𝑖

∈𝑇

𝑖

, 最后 1 个任务的结束时间

为 max

𝑇

𝑖

∈𝑇

𝑖

, 则所有任务处理结束时间 Tft(𝑇, 𝐺

) 为

Tft(𝑇, 𝐺

) = max

𝑇

𝑖

∈𝑇

𝑖

− min

𝑇

𝑖

∈𝑇

𝑖

实际计算时, 通常假设 min

𝑇

𝑖

∈𝑇

𝑖

从时间轴 0 时刻开始,

这样 Tft(𝑇, 𝐺

) = max

𝑇

𝑖

∈𝑇

𝑖

5) 任务 𝑇

𝑖

对 𝑙 种类型的资源需求满足度 Ta(𝑖, 𝑙)

可以利用其获得的资源能力

𝑅

𝑖𝑙

与资源需求 𝑅

𝑖𝑙

的比

值表示, 即

Ta(𝑖, 𝑙) =

⎧

⎨

⎩

𝑅

𝑖𝑙

⩾ 𝑅

𝑖𝑙

;

𝑅

𝑖𝑙

/𝑅

𝑖𝑙

𝑅

𝑖𝑙

< 𝑅

𝑖𝑙

;

𝑅

𝑖𝑙

𝑀

∑

𝑚=1

𝜑

𝑖𝑚

. (1)

当 𝑇

𝑖

获取的资源能力不小于其需求时, 资源需求满足

度为 1; 当 𝑇

𝑖

获取的资源能力小于其需求时, 资源需

求满足度线性减小. 记 𝐴(𝑖) = {𝑘∣𝑅

𝑖𝑙

> 0} 为 𝑇

𝑖

所需

资源类型的集合, ∣𝐴(𝑖)∣ 为 𝑇

𝑖

所需资源类型的能力值,

则任务 𝑇

𝑖

的任务资源满足度 Ta

𝑖

为 𝑇

𝑖

对于所有类型

资源需求满足度的均值, 即

𝑖

∑

𝑘∈𝐴(𝑖)

Ta(𝑖, 𝑘)

∣𝐴(𝑖)∣. (2)

6) 任务执行质量 Tq

𝑖

与 Ta

𝑖

有直接函数关系, Tq

𝑖

是对任务 𝑇

𝑖

完成概率的度量. Tq

𝑖

∈ (0, 1), Tq

𝑖

越大表

明任务 𝑇

𝑖

的完成概率越大, Tq

𝑖

大小由 Ta

𝑖

决定, 变化

趋势由中间阈值 𝜗 控制, 并呈现如下函数变化特点:

① 当 Ta

𝑖

较小时, Ta

𝑖

< 𝜗, Tq

𝑖

随着 Ta

𝑖

的提升而

提高的速度较慢, 当 Ta

𝑖

→ 0 时, Tq

𝑖

→ 0;

② 当 Ta

𝑖

较大时, Ta

𝑖

> 𝜗, Tq

𝑖

随着 Ta

𝑖

的提升而

缓慢提高, 当 Ta

𝑖

→ 1 时, Tq

𝑖

→ 1;

③ 当 Ta

𝑖

处于中间阈值 𝜗 附近时, Tq

𝑖

随着 Ta

𝑖

的

提升而快速提高.

综上 Tq

𝑖

随 Ta

𝑖

的变化特点, 设定 𝜗 = 0.5, 采用

下式近似表示 Tq

𝑖

与 Ta

𝑖

之间的函数关系

[13]

𝑖

= [1 − exp(8 ⋅ (1 − 2 ⋅ Ta

𝑖

))]

−1

. (3)

1.3 编编编组组组资资资源源源能能能力力力的的的更更更新新新模模模型型型

记 AG

𝑚

执行任务前具有资源能力矢量 𝑃

𝑚

{𝑅

𝑚𝑙

}, 在实际的空中任务执行中, 随着任务的依次进

行, 编组的资源能力随执行任务数量和强度的增加逐

渐递减. 因此, 在编组执行完某一任务后, 应对其资源

能力进行更新

[9]

如下:

renewed

𝑚𝑙

= GR

𝑚𝑙

(

1 − 𝜔

𝑙

real

𝑚𝑙

)

, 𝑙 ∈ [1, 𝐿]. (4)

其中: 𝜔

𝑙

为第 𝑙 种资源能力的损耗系数, 设定 𝜔

𝑙

为第

剩余6页未读，继续阅读

评论收藏

内容反馈

weixin_38618540

粉丝: 3
资源: 943

多编组协同任务分配模型及DLS-QGA 算法求解

最新资源

多编组协同任务分配模型及DLS-QGA 算法求解

多UCAV协同任务分配模型及粒子群算法求解

传感技术中的Dimetix Ag推出激光测距传感器、激光传感器DLS-A

A Bare Bones Particle Swarm Optimization Algorithm with Dynamic Local Search.pdf

Python库 | azure_cli_dls-0.0.8-py2.py3-none-any.whl

dmec-dls-sketch-library：数字营销电子商务-设计语言系统库，用于D2C和D2B平台

DLS-base-2021:DLS家庭作业基础课程（2021）

异构多处理器系统任务调度的最早完成时间算法.pdf

DLS-ContentCreator：Winforms桌面应用程序，用于为DLS平台编写电子学习和评估内容

华为云深度学习服务DLS

论文研究-最大团问题研究进展及算法测试标准.pdf

NST for DLS-PD

DLS-de-MilkUndPanis:用于放置学习深度学习入门（从头开始进行深度学习）产生的文件。必须在导入此书的配套资源（https

面向WTAs的VHR双臂避碰操控算法.pdf

DLS_FLS_C_TechnicalManual_V501_en测距传感器

基于云模型的量子混合粒子群算法及其应用.pdf

inspire_dls-rome:用于 INSPIRE 预定义 Atom Feed 的 ROME 模块

论文研究-双论域信息系统上的优势关系与知识发现.pdf

DLS-Mandatory2-Backend

基于风险估计模型的网格任务动态级调度算法 (2008年)

一种基于遗传算法的网格任务调度算法 (2007年)

THUSC2017-dls.pdf

DLS-Card-Creator:由First Touch Games制作的适用于iOS和Android的热门足球游戏的卡片创建者

DLS500说明书

最新资源