防疫機器人在智慧社區(qū)的配送路徑規(guī)劃研究

周 萍

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

0 引 言

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

1 環(huán)境描述

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

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

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

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

設可行路徑的柵格集為K{K1,K2,K3,K4…},障礙物的柵格集為A{A1,A2,A3,A4…},每個柵格對應序號的坐標轉換公式如下所示:

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

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

(1)

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

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

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

目標函數(shù)為每個防疫機器人從其起始的柵格開始搜索,所有防疫機器人到達目標柵格的最短路徑之和。

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

(2)

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

2 改進的蟻群算法

在蟻群算法中,蟻群k(k=1,2…,m)由當前路徑行走到下一路徑是由路徑上的信息素量來引導方向。形態(tài)轉移概率Pkij表示螞蟻從當前柵格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選擇的沒有障礙物柵格；τij(t)表示t時刻柵格i到柵格j的信息素量；ηij(t)表示從柵格i到柵格j的啟發(fā)函數(shù)；α表示信息啟發(fā)式因子；β表示期望啟發(fā)式因子。dij表示柵格i到柵格j的距離,dij取值越小,則ηij越大,因此Pkij也就越大。

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

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

(5)

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

(6)

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

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

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

0,otherwise

(7)

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

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

(8)

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

h(n)=djg+1Nj

(9)

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

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

(10)

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

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

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

(11)

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

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

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

(2)設置改進后的蟻群算法各個實驗參數(shù);

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

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

(5)更新路徑;

(6)重復4、5步驟,直到螞蟻到達目的點或者無路可走;

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

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

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

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

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

通過仿真,對兩種算法分別測試20 次,然后取平均值。選取任務點358,出發(fā)點921,得到的兩種算法仿真結果統(tǒng)計見表1。

表1 仿真實驗結果對比

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

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

圖3 兩種算法收斂曲線變化對比圖

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

4 結束語

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