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

楊岱川,文成林

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

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

楊岱川,文成林

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

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

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

0 引 言

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

1 實際地圖建立

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

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

1.2 地圖優(yōu)化

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

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

圖1 某高校校園實際地圖與柵格模型

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

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

2.1 蟻群算法與路徑點排序

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

(1)

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

(2)

本文所求的運動路線為

(3)

2.2PRM算法改進(jìn)

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

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

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

(4)

3 仿真實驗

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

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

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

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

r=0.015 05E-0.207 6V+39.15

(5)

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

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

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

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

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

3.3 實際地圖仿真

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

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

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

4 結(jié)束語

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

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

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

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

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

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

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

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

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

[9]楊興,張亞.基于改進(jìn)柵格模型的移動機器人路徑規(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é)基金資助項目(61304186;U1304615)

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

TP24

A

1001-9146(2017)03-0063-05