?一、 帶時(shí)間窗的多UAV航跡規(guī)劃問題的兩階段啟發(fā)式算法

本文采用一種兩階段啟發(fā)式算法用于問題求解, 算法的第一階段利用“最遲完成服務(wù)節(jié)點(diǎn)優(yōu)先” (Latest-Service-Finished-First, 簡稱LSFF) 算法求得問題的初始解, 第二階段利用模擬退火算法 (SA算法) 改善初始解, 獲得“滿意解”。

1 LSFF算法
LSFF算法是一種逆向計(jì)算的迭代算法, 其基本思想是:從返回機(jī)場開始, 逆向迭代計(jì)算從待服務(wù)節(jié)點(diǎn)飛往后繼節(jié)點(diǎn)的最遲動身 (完成物資投放) 時(shí)間, 并選擇最晚可服務(wù)節(jié)點(diǎn)優(yōu)先服務(wù), 重復(fù)上述過程直至全部節(jié)點(diǎn)均被服務(wù)為止;這里只接受可行解。

假設(shè)當(dāng)前后續(xù)節(jié)點(diǎn)為succ, 其最遲抵達(dá)時(shí)間為maxatsucc, 待服務(wù)節(jié)點(diǎn)i的最遲動身時(shí)間為maxdepti, 則LSFF算法的流程可描述如下:

步驟1:創(chuàng)建空航行線路為當(dāng)前航跡, 令succ=0, maxatsucc=l0;

步驟2:計(jì)算所有的maxdepti=max{maxatsucc-ti, succ, lsucc+stsucc}, 并進(jìn)行約束條件校驗(yàn), 從可行節(jié)點(diǎn)中選擇滿足maxdeptk=max{maxdepti}的節(jié)點(diǎn)k作為優(yōu)先服務(wù)節(jié)點(diǎn);

步驟3:將節(jié)點(diǎn)k插入至航段間<0, succ>, 令succ=k, maxatsucc=maxdeptk-stk, 更新節(jié)點(diǎn)k的服務(wù)標(biāo)志;

步驟4:重復(fù)步驟2、步驟3, 直至無節(jié)點(diǎn)可服務(wù)為止。若仍有節(jié)點(diǎn)未服務(wù), 創(chuàng)建新路徑, 令succ=0, maxatsucc=l0, 轉(zhuǎn)步驟2;否則轉(zhuǎn)步驟5;

步驟5輸出初始解sinit。

從上述描述顯見, LSFF算法是一種“頭插式”算法, 新節(jié)點(diǎn)的插入位置必定是航跡的第一條航段之間。由此可將時(shí)間窗約束的處理方法修正如下:計(jì)算UAV從機(jī)場出發(fā)抵達(dá)新節(jié)點(diǎn)i的最早時(shí)間minati=e0+t0i, 若maxdepti同時(shí)滿足式 (14) 、式 (15) , 則時(shí)間窗約束滿足, 否則不滿足。

2 SA算法
利用LSFF算法產(chǎn)生初始解后, 進(jìn)一步利用SA算法改進(jìn)初始解, 下面分別對SA算法的鄰域結(jié)構(gòu)和算法流程進(jìn)行描述。

(1) 鄰域結(jié)構(gòu)

本文采用兩種鄰域變換:remove操作和insert操作來構(gòu)造鄰域, 如圖1所示。
(2) 算法流程

步驟1:設(shè)置起始溫度btemp和etemp, 設(shè)置溫度迭代步長tstep, 令當(dāng)前溫度temp=btemp, 令當(dāng)前解x=sinit, 當(dāng)前最優(yōu)解s=sinit, 初始化內(nèi)循環(huán)次數(shù)maxcnt;

步驟2:如果temp>etemp, 重復(fù)執(zhí)行步驟3~步驟5;

步驟3:令內(nèi)循環(huán)次數(shù)cnt=1, 重復(fù)步驟4, 直至cnt=maxcnt為止;

步驟4:隨機(jī)選擇交換節(jié)點(diǎn)node, 利用remove和insert操作, 將其插入任一條可行路徑, 產(chǎn)生鄰域解x’;令f (·) 表示解·對應(yīng)的目標(biāo)函數(shù)值, rand_max為隨機(jī)數(shù)的上限, 比較f (x’) 和f (x) , 如果f (x’) <f (x) , 則令x=x’, 如果f (x’) <f (s) , 則令s=x’;如果f (x’) ≥f (x) , 則計(jì)算接受概率Pos=exp (- (f (x’) -f (x) ) /temp) , 并產(chǎn)生[0, rand_max]間的隨機(jī)數(shù)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

?三、運(yùn)行結(jié)果

?四、matlab版本及參考文獻(xiàn)

1 matlab版本
2014a

2 參考文獻(xiàn)
[1]馬華偉,王天曉,胡笑旋.帶時(shí)間窗的多無人機(jī)航跡規(guī)劃兩階段啟發(fā)式算法[J].火力與指揮控制. 2014,39(08)

3 備注
簡介此部分摘自互聯(lián)網(wǎng)，僅供參考，若侵權(quán)，聯(lián)系刪除文章來源地址http://www.zghlxwxcb.cn/news/detail-778987.html

到了這里，關(guān)于【任務(wù)分配】共識的捆綁算法CBBA多無人機(jī)多任務(wù)調(diào)度【含Matlab源碼 3609期】的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！