【任务分配】共识的捆绑算法CBBA多无人机多任务调度【含Matlab源码 3609期】-Toy模板网

这篇具有很好参考价值的文章主要介绍了【任务分配】共识的捆绑算法CBBA多无人机多任务调度【含Matlab源码 3609期】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【任务分配】共识的捆绑算法CBBA多无人机多任务调度【含Matlab源码 3609期】,Matlab路径规划（高阶版）,matlab

⛄一、带时间窗的多UAV航迹规划问题的两阶段启发式算法

本文采用一种两阶段启发式算法用于问题求解, 算法的第一阶段利用“最迟完成服务节点优先” (Latest-Service-Finished-First, 简称LSFF) 算法求得问题的初始解, 第二阶段利用模拟退火算法 (SA算法) 改善初始解, 获得“满意解”。

1 LSFF算法
LSFF算法是一种逆向计算的迭代算法, 其基本思想是:从返回机场开始, 逆向迭代计算从待服务节点飞往后继节点的最迟动身 (完成物资投放) 时间, 并选择最晚可服务节点优先服务, 重复上述过程直至全部节点均被服务为止;这里只接受可行解。

假设当前后续节点为succ, 其最迟抵达时间为maxatsucc, 待服务节点i的最迟动身时间为maxdepti, 则LSFF算法的流程可描述如下:

步骤1:创建空航行线路为当前航迹, 令succ=0, maxatsucc=l0;

步骤2:计算所有的maxdepti=max{maxatsucc-ti, succ, lsucc+stsucc}, 并进行约束条件校验, 从可行节点中选择满足maxdeptk=max{maxdepti}的节点k作为优先服务节点;

步骤3:将节点k插入至航段间<0, succ>, 令succ=k, maxatsucc=maxdeptk-stk, 更新节点k的服务标志;

步骤4:重复步骤2、步骤3, 直至无节点可服务为止。若仍有节点未服务, 创建新路径, 令succ=0, maxatsucc=l0, 转步骤2;否则转步骤5;

步骤5输出初始解sinit。

从上述描述显见, LSFF算法是一种“头插式”算法, 新节点的插入位置必定是航迹的第一条航段之间。由此可将时间窗约束的处理方法修正如下:计算UAV从机场出发抵达新节点i的最早时间minati=e0+t0i, 若maxdepti同时满足式 (14) 、式 (15) , 则时间窗约束满足, 否则不满足。

2 SA算法
利用LSFF算法产生初始解后, 进一步利用SA算法改进初始解, 下面分别对SA算法的邻域结构和算法流程进行描述。

(1) 邻域结构

本文采用两种邻域变换:remove操作和insert操作来构造邻域, 如图1所示。
(2) 算法流程

步骤1:设置起始温度btemp和etemp, 设置温度迭代步长tstep, 令当前温度temp=btemp, 令当前解x=sinit, 当前最优解s=sinit, 初始化内循环次数maxcnt;

步骤2:如果temp>etemp, 重复执行步骤3~步骤5;

步骤3:令内循环次数cnt=1, 重复步骤4, 直至cnt=maxcnt为止;

步骤4:随机选择交换节点node, 利用remove和insert操作, 将其插入任一条可行路径, 产生邻域解x’;令f (·) 表示解·对应的目标函数值, rand_max为随机数的上限, 比较f (x’) 和f (x) , 如果f (x’) <f (x) , 则令x=x’, 如果f (x’) <f (s) , 则令s=x’;如果f (x’) ≥f (x) , 则计算接受概率Pos=exp (- (f (x’) -f (x) ) /temp) , 并产生[0, rand_max]间的随机数rand, 如果满足Pos≥rand/rand_max, 则令x=x’;cnt=cnt+1;

步骤5:令temp=temp*tstep;

步骤6:输出满意解s。

⛄二、部分源代码

% Clear environment
close all; clear all;
addpath(genpath(cd));

% profile on

SEED = 24377;
rand(‘seed’, SEED);

%---------------------------------------------------------------------%
% Initialize global variables
%---------------------------------------------------------------------%

WORLD.CLR = rand(100,3);

WORLD.XMIN = -2.0;
WORLD.XMAX = 2.5;
WORLD.YMIN = -1.5;
WORLD.YMAX = 5.5;
WORLD.ZMIN = 0.0;
WORLD.ZMAX = 2.0;
WORLD.MAX_DISTANCE = sqrt((WORLD.XMAX - WORLD.XMIN)^2 + …
(WORLD.YMAX - WORLD.YMIN)^2 + …
(WORLD.ZMAX - WORLD.ZMIN)^2);

%---------------------------------------------------------------------%
% Define agents and tasks
%---------------------------------------------------------------------%
% Grab agent and task types from CBBA Parameter definitions
CBBA_Params = CBBA_Init(0,0);

% Initialize possible agent fields
agent_default.id = 0; % agent id
agent_default.type = 0; % agent type
agent_default.avail = 0; % agent availability (expected time in sec)
agent_default.clr = []; % for plotting

agent_default.x = 0; % agent position (meters)
agent_default.y = 0; % agent position (meters)
agent_default.z = 0; % agent position (meters)
agent_default.nom_vel = 0; % agent cruise velocity (m/s)
agent_default.fuel = 0; % agent fuel penalty (per meter)

% FOR USER TO DO: Set agent fields for specialized agents, for example:
% agent_default.util = 0;

% Initialize possible task fields
task_default.id = 0; % task id
task_default.type = 0; % task type
task_default.value = 0; % task reward
task_default.start = 0; % task start time (sec)
task_default.end = 0; % task expiry time (sec)
task_default.duration = 0; % task default duration (sec)
task_default.lambda = 0.1; % task exponential discount

task_default.x = 0; % task position (meters)
task_default.y = 0; % task position (meters)
task_default.z = 0; % task position (meters)

% FOR USER TO DO: Set task fields for specialized tasks

%---------------------------%

% Create some default agents

% QUAD
agent_quad = agent_default;
agent_quad.type = CBBA_Params.AGENT_TYPES.QUAD; % agent type
agent_quad.nom_vel = 2; % agent cruise velocity (m/s)
agent_quad.fuel = 1; % agent fuel penalty (per meter)

% CAR
agent_car = agent_default;
agent_car.type = CBBA_Params.AGENT_TYPES.CAR; % agent type
agent_car.nom_vel = 2; % agent cruise velocity (m/s)
agent_car.fuel = 1; % agent fuel penalty (per meter)

% Create some default tasks

% Track
task_track = task_default;
task_track.type = CBBA_Params.TASK_TYPES.TRACK; % task type
task_track.value = 100; % task reward
task_track.start = 0; % task start time (sec)
task_track.end = 100; % task expiry time (sec)
task_track.duration = 5; % task default duration (sec)

% Rescue
task_rescue = task_default;
task_rescue.type = CBBA_Params.TASK_TYPES.RESCUE; % task type
task_rescue.value = 100; % task reward
task_rescue.start = 0; % task start time (sec)
task_rescue.end = 100; % task expiry time (sec)
task_rescue.duration = 15; % task default duration (sec)

%---------------------------------------------------------------------%
% Define sample scenario
%---------------------------------------------------------------------%

N = 5; % # of agents
M = 10; % # of tasks

% Create random agents
for n=1:N

if(n/N <= 1/2)
    agents(n) = agent_quad;
else
    agents(n) = agent_car;
end

% Init remaining agent params
agents(n).id   = n;
agents(n).x    = rand(1)*(WORLD.XMAX - WORLD.XMIN) + WORLD.XMIN;
agents(n).y    = rand(1)*(WORLD.YMAX - WORLD.YMIN) + WORLD.YMIN;
agents(n).clr  = WORLD.CLR(n,:);

end