楊岱川,文成林

(杭州電子科技大學(xué)系統(tǒng)科學(xué)與控制工程研究所，浙江 杭州 310018)

基于蟻群和改進(jìn)PRM算法的多目標(biāo)點(diǎn)路徑規(guī)劃

楊岱川,文成林

(杭州電子科技大學(xué)系統(tǒng)科學(xué)與控制工程研究所，浙江 杭州 310018)

針對(duì)移動(dòng)機(jī)器人最短路徑問題，設(shè)計(jì)了一種包含了蟻群算法和改進(jìn)PRM算法的融合算法.首先，根據(jù)實(shí)際地圖建立了柵格化地圖模型，并將地圖模型用瘦化方法優(yōu)化，然后，用蟻群算法排出其優(yōu)先級(jí)，用改進(jìn)的PRM算法進(jìn)行路徑規(guī)劃，最后，給出了基于實(shí)際地圖多目標(biāo)點(diǎn)的仿真路徑以及與同類算法的結(jié)果對(duì)比，改進(jìn)算法比Bug2算法和D*算法快約2 s，驗(yàn)證了蟻群算法和改進(jìn)PRM算法融合的有效性.

移動(dòng)機(jī)器人；蟻群算法；概率地圖算法；路徑規(guī)劃

0 引 言

移動(dòng)機(jī)器人的路徑規(guī)劃在工業(yè)和民用領(lǐng)域得到了廣泛的應(yīng)用，例如掃地機(jī)器人[1]、旋翼快遞飛行器以及采摘機(jī)器人[2]等，而各方面相關(guān)研究也在不斷推進(jìn).目前大多數(shù)算法研究的是二維平面的兩點(diǎn)間路徑規(guī)劃問題[3]，如A*算法[4]、Dijkstra算法[5]和粒子群算法[6]等.單獨(dú)使用一種算法雖然能夠解決實(shí)際地圖上的路徑規(guī)劃問題，但是對(duì)于多任務(wù)點(diǎn)問題難以勝任.為此，本文提出采用蟻群算法對(duì)多目標(biāo)點(diǎn)執(zhí)行順序進(jìn)行規(guī)劃.結(jié)合地圖優(yōu)化方法和改進(jìn)的概率地圖算法(Probabilistic Roadmap Method，PRM)對(duì)帶有實(shí)際地圖障礙物的多個(gè)目標(biāo)點(diǎn)進(jìn)行先后排序和路徑搜尋，較好地解決了目前存在的移動(dòng)處理器響應(yīng)速度慢和不能一次規(guī)劃多個(gè)目標(biāo)點(diǎn)路徑的問題.

1 實(shí)際地圖建立

機(jī)器人導(dǎo)航中地圖的表示方法大致有特征地圖[7]、拓?fù)涞貓D[8]和柵格地圖[9].本文地圖建模時(shí)使用的是柵格地圖.柵格地圖把整個(gè)地圖化為一個(gè)一個(gè)的柵格，并分別指出每個(gè)柵格是否被障礙物占據(jù)，形成了一個(gè)連通圖，通過指定起始柵格和目標(biāo)柵格，利用搜索算法進(jìn)行路徑搜索.這種方法應(yīng)用廣泛，有較強(qiáng)的魯棒性，由于其離散化的設(shè)計(jì)，地圖也便于維護(hù).

1.1 任務(wù)與地圖建模

1.2 地圖優(yōu)化

在傳統(tǒng)的PRM方法中存在狹窄通路(narrow passage)問題，其根本原因是PRM方法產(chǎn)生的隨機(jī)采樣點(diǎn)在空間上的分布不夠均勻，在狹窄區(qū)域或在轉(zhuǎn)角的分布點(diǎn)連線較少甚至沒有，導(dǎo)致明明存在的通路卻不能在運(yùn)算中被規(guī)劃出來.

針對(duì)該問題，普遍采用的解決方法有MLDP[10]、橋測(cè)試[11]等，本文使用障礙物合理瘦化的方法來解決.根據(jù)實(shí)際障礙物輪廓進(jìn)行等比例收縮，從而擴(kuò)大通路面積，同時(shí)把機(jī)器人看做為柵格地圖上的一個(gè)點(diǎn).

圖1 某高校校園實(shí)際地圖與柵格模型

地圖的優(yōu)化也是一個(gè)“預(yù)計(jì)算”的過程，只要工作區(qū)域的地圖不變，優(yōu)化后的地圖可以保留到下次再使用，所以對(duì)于柵格地圖的瘦化過程所花費(fèi)的時(shí)間并不計(jì)入總規(guī)劃時(shí)間.

2 蟻群算法與改進(jìn)PRM算法結(jié)合

2.1 蟻群算法與路徑點(diǎn)排序

蟻群算法[13]是從螞蟻在覓食過程中尋找路徑的方法中得到啟示.本文使用的是基于Ant-Cycle模型的算法，有

(1)

蟻群算法在眾多路徑點(diǎn)中選出一條不重復(fù)經(jīng)過的連線，并且以盡量縮短路徑總長(zhǎng)度為優(yōu)化目標(biāo).每?jī)蓚€(gè)路徑點(diǎn)之間的距離為

(2)

本文所求的運(yùn)動(dòng)路線為

(3)

2.2PRM算法改進(jìn)

概率地圖算法PRM通過隨機(jī)采樣進(jìn)行碰撞檢測(cè)，并獲取所需要的障礙物或自由空間信息，再進(jìn)行路徑規(guī)劃.

普通PRM算法要想得到更好的結(jié)果，直接增加Ga中采樣點(diǎn)的數(shù)量，讓更多的點(diǎn)落入狹窄通路即可.配合前面所說的障礙物瘦化方法，在一定程度上進(jìn)一步解決了狹窄通路問題.但采樣點(diǎn)增多，運(yùn)算量也會(huì)成指數(shù)級(jí)增長(zhǎng)，這對(duì)大地圖上依靠增多采樣點(diǎn)來保證算法的可靠性提出了極高的計(jì)算性能要求.本文提出一種鄰域半徑r可動(dòng)態(tài)變化的改進(jìn)方法，代替了由最近k個(gè)節(jié)點(diǎn)或者固定半徑r連接構(gòu)建網(wǎng)絡(luò)的方法，更好地解決了這個(gè)問題.

動(dòng)態(tài)變化的鄰域半徑r指的是在地圖大小一定時(shí)，r并不是地圖邊長(zhǎng)的固定倍數(shù)，而是隨采樣點(diǎn)數(shù)目的變化而變化.具體的算法改進(jìn)為

(4)

3 仿真實(shí)驗(yàn)

3.1 不同參數(shù)仿真結(jié)果

以南大門到圖書館為例，在地圖中采用原始PRM算法和不同半徑r及采樣點(diǎn)數(shù)目的RPM算法仿真50次對(duì)比，得到結(jié)果如表1所示.

表1 不同參數(shù)設(shè)置的PRM算法結(jié)果

從表1中可以看出，采樣點(diǎn)的增減對(duì)算法復(fù)雜度的影響效果最顯著.通常的PRM算法在采樣點(diǎn)增多一倍的情況下復(fù)雜度增加到近4倍，但是對(duì)鄰域半徑進(jìn)行縮短處理后，復(fù)雜度隨之降低.對(duì)上述結(jié)果進(jìn)行分析與擬合，得出新的半徑公式

r=0.015 05E-0.207 6V+39.15

(5)

表示針對(duì)圖1(c)的PRM算法中邊的數(shù)目與頂點(diǎn)和鄰域半徑的關(guān)系.

3.2 結(jié)果分析與其他方法對(duì)比

在復(fù)雜度差不多的情況下，邊的數(shù)量越多，效果越好，所以本文的優(yōu)化目標(biāo)就是在復(fù)雜度可以接受的情況下得到Emax.如表2所示，采樣點(diǎn)150、鄰域半徑22的情況是相對(duì)優(yōu)秀的參數(shù)，相比之下，采樣點(diǎn)200、鄰域半徑12與之復(fù)雜度相近，但是邊數(shù)更少.同時(shí)也通過畫圖驗(yàn)證分析，圖2中灰色為障礙物(建筑，水池等)，黑色點(diǎn)為采樣點(diǎn)，灰色大圓點(diǎn)為要路過的采樣點(diǎn)，灰色粗線條為規(guī)劃出的路徑.在目前絕大多數(shù)的研究主要針對(duì)的都是兩點(diǎn)間的尋路，故針對(duì)從[42;5]南大門到[51;70]圖書館進(jìn)行了50次兩點(diǎn)間的尋路仿真及算法對(duì)比，如表2所示.

表2 代表性的參數(shù)結(jié)果

從表2的代表性統(tǒng)計(jì)數(shù)據(jù)上看出，改進(jìn)PRM路徑網(wǎng)絡(luò)明顯比另外兩種基于PRM的算法對(duì)地圖的覆蓋全面.由此可以說明，采用動(dòng)態(tài)變化鄰域半徑的改進(jìn)PRM算法可以漸進(jìn)達(dá)到最優(yōu)參數(shù)，從而保證運(yùn)算量合理的情況下有最優(yōu)的規(guī)劃，表現(xiàn)了改進(jìn)方法的優(yōu)越性.同時(shí)還比較了文獻(xiàn)[12]中的兩種常用算法：類D*算法與bug2算法.雖然這兩種方法的路徑更好，但是從用時(shí)看出算法的復(fù)雜度比新的改進(jìn)算法高很多.并且類D*算法與bug2算法無法一次完成下一節(jié)中四點(diǎn)快遞目標(biāo)點(diǎn)的規(guī)劃，而是需要至少3次運(yùn)行，這樣更增加了運(yùn)算時(shí)間.

3.3 實(shí)際地圖仿真

本文1.1節(jié)中提到地圖上有4個(gè)目標(biāo)點(diǎn)：[42;5]南大門、[51;70]圖書館、[95;98]北一門、[70;40]第三教學(xué)樓，要求機(jī)器人走過4個(gè)點(diǎn)，并且尋求一條最短的路徑.首先使用蟻群算法規(guī)劃先后順序?yàn)槟洗箝T→第三教學(xué)樓→北一門→圖書館，之后再運(yùn)行改進(jìn)的PRM算法尋找路徑，得到最終路徑如圖2所示.

圖2 最終路徑規(guī)劃

圖2(a)-(d)依次展示的是從南大門到第三教學(xué)樓，再到北一門，然后到圖書館，最后回到南大門的路徑.這些路徑并非十分光滑、平直，但是合理可行.

4 結(jié)束語

針對(duì)多目標(biāo)點(diǎn)尋路問題，本文給出了一種基于蟻群算法和PRM算法的改進(jìn)路徑規(guī)劃方法，將大多數(shù)規(guī)劃方法的兩點(diǎn)規(guī)劃擴(kuò)展到多點(diǎn)規(guī)劃.改進(jìn)算法針對(duì)柵格化的地圖模型，進(jìn)行了障礙物瘦化，成功找出合適路徑，并縮減了運(yùn)算時(shí)間，提高了反應(yīng)速度.針對(duì)當(dāng)前移動(dòng)機(jī)器人領(lǐng)域發(fā)展趨勢(shì)，多機(jī)器人的任務(wù)目標(biāo)分配和動(dòng)態(tài)地圖上的路徑規(guī)劃均可作為進(jìn)一步的研究方向.

[1]張健,陳立偉,郭玉驕,等.自動(dòng)清掃機(jī)器人研究[J].中國高新技術(shù)企業(yè),2015(10):10-11.

[2]黃玲,胡蔚蔚.基于改進(jìn)蟻群算法的果蔬采摘機(jī)器人三維路徑規(guī)劃[J].農(nóng)機(jī)化研究,2016(9):38-42.

[3]史恩秀,陳敏敏,李俊,等.基于蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法研究[J].農(nóng)業(yè)機(jī)械學(xué)報(bào),2014,45(6):53-57.

[4]林巍凌.引入導(dǎo)航網(wǎng)格的室內(nèi)路徑規(guī)劃算法[J].測(cè)繪科學(xué),2016,41(2):39-43.

[5]裴小兵,賈定芳.基于模擬退火算法的城市物流多目標(biāo)配送車輛路徑優(yōu)化研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2016(2):105-113.

[6]張萬緒,張向蘭,李瑩.基于改進(jìn)粒子群算法的智能機(jī)器入路徑規(guī)劃[J].計(jì)算機(jī)應(yīng)用,2014,34(2):510-513.

[7]朱建國,高峻峣,李科杰,等.室內(nèi)未知環(huán)境下移動(dòng)機(jī)器人特征地圖創(chuàng)建研究[J].計(jì)算機(jī)測(cè)量與控制,2011,19(12):3044-3046.

[8]蘇麗穎,宋華磊.基于激光傳感器構(gòu)建環(huán)境拓?fù)涞貓D[J].傳感器與微系統(tǒng),2012,31(9):64-66.

[9]楊興,張亞.基于改進(jìn)柵格模型的移動(dòng)機(jī)器人路徑規(guī)劃研究[J].農(nóng)家科技旬刊,2016(3):416.

[11]HSU D, JIANG T, REIF J, et al. The bridge test for sampling narrow passages with probabilistic roadmap planners[C]//Robotics and Automation, 2003. Proceedings. ICRA'03. IEEE International Conference on. IEEE, 2003,3:4420-4426.

[12]CORKE P. Robotics, Vision and Control[M]. Berlin:Springer, 2011:91-97.

[13]COLORNI A, DORIGO M, MANIEZZO V, et al. Ant system for job-shop scheduling[J]. Operations Research Statistics & Computer Science, 1994,34(1):39-53.

Multiple Targets Robot Path Planning Based on Ant Colony and Improved Probabilistic Road Map

YANG Daichuan, WEN Chenglin

(InstituteofSystemScienceandControlEngineering,HangzhouDianziUniversity,HangzhouZhejiang310018,China)

Aiming at shortest path of robot path planning, this paper designs an ant colony algorithm(ACA) combine with improved probabilistic road map(PRM) method of moving robots in real map, which need to pass by several work points and back to starting point in a shortest way. Firstly, building a model of grid of work space and diminish it, then work out a priority level of work points, next using improved PRM method to plan a path, and finally gives the results of simulation based on real map, and results compared with other algorithm to show the reliability of this fusion algorithm. Improved algorithm is faster than Bug2 and D*method for 2 seconds, which proved the effectiveness of it.

moving robot; ant colony; probabilistic road map; path planning

10.13954/j.cnki.hdu.2017.03.013

2016-10-14

國家自然科學(xué)基金資助項(xiàng)目(61304186;U1304615)

楊岱川(1992-)，男，四川樂山人，碩士研究生，機(jī)器人學(xué).通信作者：文成林教授，E-mail：wencl@hdu.edu.cn.

TP24

A

1001-9146(2017)03-0063-05