周 萍

(武漢理工大學(xué)，湖北 武漢 430063)

0 引 言

防疫機(jī)器人是全球疫情大流行這一特殊場(chǎng)景下使用的一種無(wú)人配送機(jī)器人,路徑規(guī)劃問(wèn)題一直是無(wú)人配送機(jī)器人領(lǐng)域的熱點(diǎn)問(wèn)題。關(guān)于配送機(jī)器人的路徑規(guī)劃的研究最開(kāi)始是基于經(jīng)典的圖論搜索的算法研究,之后又逐步進(jìn)入不確定環(huán)境的局部路徑規(guī)劃研究,以及到如今的以智能算法研究為主的三大階段[1]。Hao等[2]于2014 年提出一種將免疫網(wǎng)絡(luò)和蟻群優(yōu)化算法相結(jié)合的新型免疫蟻群優(yōu)化算法,以提高多機(jī)器人系統(tǒng)搜索最短路徑的能力。Das等[3]于2016 年提出一種在動(dòng)態(tài)環(huán)境下利用改進(jìn)的重力搜索算法(IGSA)優(yōu)化多機(jī)器人路徑軌跡的新方法,用于從現(xiàn)有位置獲得機(jī)器人的最優(yōu)后續(xù)位置。彭凡彬等[4]于2018 年提出一種基于改進(jìn)蟻群算法的路徑規(guī)劃方法,提高了傳統(tǒng)蟻群算法的搜索能力。陳豪等[5]于2018 年提出一種改進(jìn)A*算法,使機(jī)器人在路徑搜索的同時(shí)還具備有一定的方向性和并行性。本文以智慧社區(qū)為應(yīng)用背景,將改進(jìn)的蟻群算法與柵格法相結(jié)合,求解了防疫機(jī)器人在配送物品時(shí)的路徑規(guī)劃問(wèn)題,對(duì)于之后的智能配送機(jī)器人在智慧社區(qū)的路徑規(guī)劃方面具有一定的借鑒意義。

1 環(huán)境描述

以某智慧社區(qū)為實(shí)驗(yàn)環(huán)境,以智慧社區(qū)的4個(gè)入口作為出發(fā)點(diǎn)、以智慧社區(qū)內(nèi)的9棟樓作為任務(wù)點(diǎn)以及作為障礙物的樓棟都是靜態(tài)且不隨時(shí)間變化的,機(jī)器人的任務(wù)就是根據(jù)當(dāng)前配送任務(wù)往返于指定地點(diǎn)之間,從而完成防疫物資的配送。

利用柵格法將防疫機(jī)器人在智慧社區(qū)的工作環(huán)境簡(jiǎn)化成二維平面圖,由40×40的網(wǎng)格劃分,如圖1所示。機(jī)器人從某一柵格到下一可選的柵格分別是與其相鄰的上、下、左、右、右上、右下、左上、左下這8個(gè)方向,對(duì)圖1中的每個(gè)柵格進(jìn)行編號(hào)[6],從左上角開(kāi)始對(duì)每個(gè)柵格按從左往右、從上往下的順序編號(hào),序號(hào)從1至1 600。

白色網(wǎng)格表示防疫機(jī)器人可以移動(dòng)區(qū)域(即路徑),而黑色網(wǎng)格則代表障礙物(樓棟和草坪等),藍(lán)色圓形(297、327、349、358、770、835、1 090、1 189、1 589)代表任務(wù)點(diǎn),紅色三角形(22、521、921、1 577)代表防疫機(jī)器人出發(fā)點(diǎn),定義左上角坐標(biāo)為(0.5,39.5)的柵格的序號(hào)為1,則序號(hào)為2的柵格坐標(biāo)為(1.5,39.5)。

圖1 防疫機(jī)器人工作環(huán)境模型

設(shè)可行路徑的柵格集為K{K1,K2,K3,K4…},障礙物的柵格集為A{A1,A2,A3,A4…},每個(gè)柵格對(duì)應(yīng)序號(hào)的坐標(biāo)轉(zhuǎn)換公式如下所示:

{xi=(mod)(i-1,n)+0.5

yi=39.5-(fix)((i-1)/n)

(1)

為了便于研究,并且不失一般性,假設(shè):

(1) 智慧社區(qū)的環(huán)境信息為已知信息,防疫機(jī)器人出發(fā)點(diǎn)、任務(wù)點(diǎn)、障礙物等在起始時(shí)間給定;

(2) 障礙物是靜態(tài)的,且不隨時(shí)間移動(dòng)。

目標(biāo)函數(shù)為每個(gè)防疫機(jī)器人從其起始的柵格開(kāi)始搜索,所有防疫機(jī)器人到達(dá)目標(biāo)柵格的最短路徑之和。

minD=∑nj=1∑ni=1(xi+1-xi)2+(yi+1-yi)2

(2)

式中：D是表示防疫機(jī)器人配送的總距離；n表示從起始柵格到目標(biāo)柵格的需要移動(dòng)的次數(shù)；m表示防疫機(jī)器人個(gè)數(shù)。

2 改進(jìn)的蟻群算法

在蟻群算法中,蟻群k(k=1,2…,m)由當(dāng)前路徑行走到下一路徑是由路徑上的信息素量來(lái)引導(dǎo)方向。形態(tài)轉(zhuǎn)移概率Pkij表示螞蟻從當(dāng)前柵格i到下一柵格j的概率,Pkij越大表示被選擇的概率也就越高。

Pkij(t)={ταij(t)ηβij(t)∑s∈allowedkταis(t)ηβis(t),j∈allowedk

0,otherwise

(3)

ηij(t)=1dij

(4)

式中：allowedk表示螞蟻k選擇的沒(méi)有障礙物柵格；τij(t)表示t時(shí)刻?hào)鸥駃到柵格j的信息素量；ηij(t)表示從柵格i到柵格j的啟發(fā)函數(shù)；α表示信息啟發(fā)式因子；β表示期望啟發(fā)式因子。dij表示柵格i到柵格j的距離,dij取值越小,則ηij越大,因此Pkij也就越大。

按照公式(3)的路徑轉(zhuǎn)移概率,螞蟻再根據(jù)轉(zhuǎn)輪賭法確定下一移動(dòng)節(jié)點(diǎn)。當(dāng)全部螞蟻從出發(fā)節(jié)點(diǎn)到達(dá)任務(wù)節(jié)點(diǎn)時(shí),需要計(jì)算每只螞蟻經(jīng)過(guò)的路徑長(zhǎng)度,并保持最小路徑長(zhǎng)度,然后更新每條路徑上的信息素濃度,信息素濃度的更新是指揮發(fā)一部分、增加一部分，如公式(5)和公式(6)所示:

τij(t+1)=(1-ρ)τij(t)+Δτij

(5)

Δτij(t)=∑mk=1Δτkij

(6)

式中：Δτij表示在此次搜索中路徑上蟻群殘留下的信息素濃度的總量;Δτij(t+1)表示t+1時(shí)刻蟻群在路徑(i,j)上殘留下的信息素濃度;τij(t)表示t時(shí)刻該路徑上的信息素濃度;ρ表示信息素?fù)]發(fā)系數(shù)，揮發(fā)系數(shù)越大說(shuō)明在算法完成一輪路徑搜索中信息素?fù)]發(fā)的程度越大。

對(duì)蟻群算法運(yùn)行過(guò)程中信息素分布的問(wèn)題通常采用的模型有3種，即蟻周模型(ACS)、蟻量模型(AQS)及蟻密模型(ADS),蟻量模型與蟻密模型屬于局部信息素,即螞蟻從節(jié)點(diǎn)i到節(jié)點(diǎn)j后更新其路徑(i,j)上的信息素。在蟻周模型中,信息素增量與搜索的整體路徑有關(guān),且信息素增量與具體路徑(i,j)無(wú)關(guān),屬于全局更新方式。本文采用的是蟻周模型,表示為:

Δτkij(t)={QLk,第k只螞蟻經(jīng)過(guò)路徑(i,j)

0,otherwise

(7)

在基本蟻群算法中,啟發(fā)函數(shù)ηij(t)只和當(dāng)前節(jié)點(diǎn)i與下一節(jié)點(diǎn)j之間路徑(i,j)的長(zhǎng)度相關(guān),如果路徑(i,j)的長(zhǎng)度越短,則下一節(jié)點(diǎn)被選擇的概率越大,所以蟻群算法在前期尋找路徑時(shí)具有很大的盲目性,降低了算法的搜索效率。為了提高蟻群算法的搜索速度和準(zhǔn)確度,防止陷入局部最優(yōu)解,考慮到A*算法的估價(jià)函數(shù)的思想重新構(gòu)造蟻群算法,以此解決算法的收斂速度慢的不足。估價(jià)函數(shù)如公式(8)所示:

f(n)=g(n)+h(n)

(8)

式中：f(n)代表節(jié)點(diǎn)i的估價(jià)函數(shù)；g(n)表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j的成本；h(n)由兩部分組成，一是可選節(jié)點(diǎn)j到目標(biāo)節(jié)點(diǎn)g的成本,二是可選節(jié)點(diǎn)j的個(gè)數(shù)Nj。h(n)的函數(shù)表達(dá)式如下:

h(n)=djg+1Nj

(9)

式中：Nj越大即當(dāng)前節(jié)點(diǎn)i到下一節(jié)點(diǎn)j的可選路徑越多,蟻群算法的搜索多樣性的成本就越小;djg表示下一節(jié)點(diǎn)j到目標(biāo)節(jié)點(diǎn)g的歐拉距離,djg越小,成本越小。由此構(gòu)造新的啟發(fā)函數(shù)如下:

ηij(t)=1f(n)=1dij+djg+1Nj

(10)

在基本蟻群算法中,信息素?fù)]發(fā)系數(shù)ρ的取值為介于0與1之間的一個(gè)常數(shù)。當(dāng)ρ的取值較小時(shí),由于每條道路的信息素濃度的相差不多導(dǎo)致之前的螞蟻對(duì)后續(xù)螞蟻的引導(dǎo)性減少?gòu)亩档土讼伻核惴ǖ乃阉魉俣?。?dāng)ρ的取值較大時(shí),前面的螞蟻對(duì)后面螞蟻的引導(dǎo)性過(guò)強(qiáng)從而導(dǎo)致螞蟻搜索更多路徑的可能性降低,更容易陷入局部最優(yōu)解[7，8]。所以,為了增加算法的全局搜索能力，同時(shí)又可以在一定程度上加快算法的收斂速度，提出一種兩段調(diào)整信息素?fù)]發(fā)系數(shù)的方法，即隨著迭代次數(shù)的增加,將算法按迭代次數(shù)均分為前期和后期。在算法的前期，將ρ取(0.1,0.3)之間的任意一個(gè)數(shù),這樣可以使得算法在前期的全局搜索能力增強(qiáng);在算法的后期,將ρ取(0.4,0.6),這樣有利于算法在后期加快收斂速度。信息素?fù)]發(fā)系數(shù)ρ的改進(jìn)如下:

{ρ=unifrnd(0.1,0.3),k<0.25K

ρ=unifrnd(0.4,0.6),k≥0.25K

(11)

式中:K表示算法的最大迭代次數(shù);k表示當(dāng)前的迭代次數(shù)。

改進(jìn)后的蟻群算法為防疫機(jī)器人在智慧社區(qū)路徑規(guī)劃的具體步驟如下:

(1)防疫機(jī)器人環(huán)境建模和參數(shù)初始化。用柵格法將防疫機(jī)器人在智慧社區(qū)的運(yùn)行環(huán)境劃分成40×40 的柵格地圖,每個(gè)矩形柵格大小一樣,其中標(biāo)記1 的柵格為障礙物,標(biāo)記0 的柵格表示可移動(dòng)空間;

(2)設(shè)置改進(jìn)后的蟻群算法各個(gè)實(shí)驗(yàn)參數(shù);

(3)將m只螞蟻放在初始點(diǎn);

(4)螞蟻k選擇從起始節(jié)點(diǎn)能夠移動(dòng)到的下一節(jié)點(diǎn),由每個(gè)可選節(jié)點(diǎn)的信息素計(jì)算出到其節(jié)點(diǎn)的概率值,并通過(guò)公式(10)決定下一起始點(diǎn);

(5)更新路徑;

(6)重復(fù)4、5步驟,直到螞蟻到達(dá)目的點(diǎn)或者無(wú)路可走;

(7)重復(fù)4、5、6步驟,直到某一代所有螞蟻迭代結(jié)束;

(8)根據(jù)公式(11)更新信息素矩陣,不包括沒(méi)有到達(dá)的螞蟻;

(9)重復(fù)(4)～(8)步驟,直到第n代螞蟻迭代結(jié)束。

3 路徑規(guī)劃仿真與分析

防疫機(jī)器人在智慧社區(qū)配送的路徑規(guī)劃上,各個(gè)有關(guān)參數(shù)的取值對(duì)蟻群算法是否可以具備較好的性能有著十分重要的意義。通過(guò)對(duì)蟻群算法的各個(gè)參數(shù)進(jìn)行仿真實(shí)驗(yàn)，確定參數(shù)的取值,最后取螞蟻數(shù)目(m)=50,信息啟發(fā)式因子(α)=1,期望啟發(fā)式因子(β)=5,信息素?fù)]發(fā)系數(shù)(ρ)=0.4,信息素增加強(qiáng)度系數(shù)(Q)=1,迭代次數(shù)(K)=200。

通過(guò)仿真,對(duì)兩種算法分別測(cè)試20 次,然后取平均值。選取任務(wù)點(diǎn)358,出發(fā)點(diǎn)921,得到的兩種算法仿真結(jié)果統(tǒng)計(jì)見(jiàn)表1。

表1 仿真實(shí)驗(yàn)結(jié)果對(duì)比

兩種算法的最優(yōu)路徑對(duì)比圖和收斂曲線變化對(duì)比如圖2、圖3所示。

圖2 兩種算法最優(yōu)路徑比較圖

圖3 兩種算法收斂曲線變化對(duì)比圖

由表1可以看出,改進(jìn)的蟻群算法的平均收斂速度更快,算法的平均運(yùn)行時(shí)間更短。從圖2和圖3可以看出改進(jìn)的蟻群算法得到的最優(yōu)路徑比基本蟻群算法的路徑長(zhǎng)度要短。

4 結(jié)束語(yǔ)

綜合分析可知,本文改進(jìn)的蟻群算法在路徑長(zhǎng)度、迭代次數(shù)和運(yùn)行時(shí)間方面都優(yōu)于基本蟻群算法,較好地規(guī)劃了配送機(jī)器人在規(guī)整布局的智慧小區(qū)中的路徑,對(duì)其他功能性的移動(dòng)機(jī)器人的路徑規(guī)劃問(wèn)題有一定借鑒作用。本文簡(jiǎn)化了社區(qū)環(huán)境,研究場(chǎng)景較為簡(jiǎn)單,在研究更加復(fù)雜的場(chǎng)景時(shí),需要對(duì)環(huán)境建模方法做更加深入的探究。