A*算法在移動機器人自學習中的使用*

張燕,徐一超,盛洲

(南京大學金陵學院,南京210089)

A*算法在移動機器人自學習中的使用*

張燕,徐一超,盛洲

(南京大學金陵學院,南京210089)

通過讓移動機器人在未知環(huán)境下的自學習過程來得到環(huán)境地圖,然后利用A*算法進行最優(yōu)路徑規(guī)劃,并選取路徑中的關鍵節(jié)點傳給移動機器人,移動機器人就可以根據這些節(jié)點自主運行。通過移動機器人自主運行實驗,可以看出其運行效果良好。

路徑規(guī)劃;A*算法;自學習;二維地圖

引 言

自主移動機器人是一種通過傳感器來感知和探測周圍未知環(huán)境并在收到命令后進行自主移動的智能系統[1]。移動機器人能否進行高效率的導航移動即能否在環(huán)境中移動到目的地,是衡量機器人定位技術的關鍵[2]。移動機器人自學習需要以下幾部分技術,首先需要獲取未知環(huán)境下的障礙物地圖,其次需要移動機器人知道自己的位置信息,最后需要使用路徑規(guī)劃算法進行路徑規(guī)劃。

目前常用的環(huán)境信息是通過傳感器進行數據獲取的,機器人避障和測距傳感器主要有紅外、超聲波、激光及視覺傳感器[3]。激光傳感器和視覺傳感器價格較貴,對控制器的要求較高[4],因而,在移動機器人系統中多采用紅外及超聲波傳感器。因此本設計中采用超聲紅外傳感器進行數據獲取。目前移動機器人定位技術很多,常見的有內部傳感器定位技術、主動傳感器定位技術、視覺傳感器定位技術、全球衛(wèi)星定位技術[5]。綜合考慮成本等因素,本設計使用內部傳感器定位技術,采用里程計和陀螺儀進行位置定位。路徑規(guī)劃技術就是要機器人在障礙物環(huán)境中,尋找一條從出發(fā)點到目標點的合適路徑,保證按照該路徑行走時,不發(fā)生碰撞,并且滿足一定的約束條件[6],根據周圍環(huán)境信息是否已知,可分為全局路徑規(guī)劃技術和局部路徑規(guī)劃[7]。全局路徑規(guī)劃技術應用最普遍的是簡單柵格法[8],并且由于周圍的環(huán)境已知,故得出路徑前,必須每次都要對全局環(huán)境進行處理。局部路徑規(guī)劃側重于移動機器人當前周圍環(huán)境的局部信息,并利用傳感器來探測周圍環(huán)境信息,然后進行實時路徑規(guī)劃。自學習功能需要在未知環(huán)境走一圈之后,根據獲取的全局障礙進行路徑規(guī)劃,因此采用全局柵格地圖的方式來實現。

1 系統組成和結構

對于移動機器人路徑規(guī)劃系統設計,硬件部分如圖1所示,移動機器人下位機CPU是一個基于Cortex-M3內核的芯片,位置信息由里程計獲取。超聲紅外傳感器獲取障礙物距離信息,九軸傳感器中的陀螺儀用來獲取角度信息。移動機器人的運動通過串口控制舵機運行,上位機通過無線模塊進行數據通信。

2 移動機器人位姿和障礙信息獲取

2.1 里程計

里程計即為用來測量移動機器人位移的霍爾傳感器,本設計使用的是霍爾元件A3144,其能夠感知磁鋼信息。當磁鋼靠近霍爾傳感器時,傳感器中的綠燈會亮,并輸出低電平,用數字“0”表示輸出低電平;當磁鋼遠離霍爾傳感器時,傳感器中的綠燈滅,又回到原來的高電平,用數字“1”表示輸出高電平。當車輪轉動時,固定在車輪上的每個磁鋼會不斷地靠近和遠離霍爾開關傳感器,這時就會在示波器上顯示出方波。

圖1 移動機器人路徑規(guī)劃結構框圖

為了使測量的移動機器人行程信息更加準確,本設計在一個車輪輪彀上貼4個磁鋼。如果只計算一個車輪轉過的圈數,會因為車輪偶爾出現的打滑有較大的誤差,因此在移動機器人對角線的兩個車輪上分別安裝4個磁鋼,對兩個車輪測得的位移取平均值,以此來減小一個車輪打滑所產生的誤差。整體布局情況如圖2所示。

圖2 磁鋼分布的位置

軟件上采用GPIO中斷的方式讀取數據,每次CAP口捕捉到下降沿的時候,則計數一次,這樣根據捕捉到的下降沿的個數,就可以知道磁鋼和霍爾傳感器相互感應的次數,再乘以每次感應的一個周期內車輪轉過的距離,就可以得到機器人行走的距離。因為需要采集兩個車輪的數據,采用兩個GPIO中斷獲取數據,然后再去取平均值,以此來減小誤差。

假設左前輪上里程計與磁鋼感應的次數為n1,右后輪上的次數為n2,如圖3所示,測得機器人車輪的周長L為20 cm,最后機器人中心點O行走經過的路程S為:

2.2 陀螺儀和電子羅盤

移動機器人獲取角度信息可以采用陀螺儀或者電子羅盤,陀螺儀通過對角速度積分,便能得到角度值,但是時間較長會產生零漂。而電子羅盤可以直接獲取角度信息,但是容易受周圍磁場干擾。本設計考慮用兩者進行數據融合獲取角度信息。陀螺儀選用ITG3205,電子羅盤選用HMC5883L。為了減少一些電磁干擾,電子羅盤外加了屏蔽罩。兩者與CPU的連接使用的是I2C接口,其I2C的軟地址分別為0xd0和0x3c。硬件連接如圖4所示。

圖3 路程的測量

圖4 角度傳感器引腳連接

2.3 位姿獲取

移動機器人位姿獲取采用了航姿推算法計算機器人相對于初始位置的位移角度信息。

2.4 障礙物信息獲取

為了得到機器人的周邊環(huán)境信息,需要使用傳感器。本文使用超聲云臺傳感器和紅外傳感器結合起來獲取障礙物信息。對于超聲云臺,通過I/O口控制超聲傳感器旋轉,可以測量前方180度的障礙物信息,返回給CPU的是障礙物距離信息。其具體的流程如圖5所示。首先根據移動機器人運動速度調整云臺轉速,讓其很好地獲取每一個角度的信息,而后依次獲取前方5個點的信息,此時采樣完成,由于超聲傳感器有時候由于鏡面反射之類的原因,存在無判斷,因此采用濾波算法進行處理,由于篇幅問題這里不再贅述。

圖5 障礙物信息獲取流程圖

由于超聲云臺只能夠獲取前方障礙物信息,為了使移動機器人運行獲取周圍障礙物信息,設計采用4個紅外傳感器,分別布局在前方兩個,左方一個,右方一個。通過探測4個方向近距離處是否有障礙物,來指導機器人運動,避免碰撞到障礙物,同時獲取障礙物信息。

3 移動機器人路徑規(guī)劃研究

3.1 A*算法簡介

A*算法是一種啟發(fā)式搜索算法,即機器人對路徑規(guī)劃中所要搜索的點會預估其代價值,其代價值是猜測得到的,并不是實際測量的[11]。A*算法中最關鍵的公式是表示每一個節(jié)點代價值的預估代價函數F:

式中,G表示起始點到當前點的實際代價值,也即沿著路徑移動到指定方格的移動耗費;H表示當前點到目標點的預估代價值[12]。為了簡化計算,減小路徑規(guī)劃的時間復雜度,規(guī)定水平和垂直方向上的方格距離為10,對角線上距離為14。預估代價值H由曼哈頓函數計算得到[13],曼哈頓函數的計算方法就像在城市中從一個地方行走到另一個地方,在行走過程中是不能沿著對角線方向行走來穿過障礙物的,只可以通過直角轉彎來繞過障礙物,而曼哈頓計算的就是從起點行走到終點所經過的街區(qū)數。因此預估代價值可以用數學表達式表示為:

其中(ax,ay)表示起點的坐標,(bx,by)表示終點的坐標。簡言之,在計算預估代價值時,應忽略一切障礙物,只計算當前點坐標與終點坐標差的絕對值之和。進一步來說,預估代價值的計算是估算得到的,并不是通過測量計算得到的,這也是A*算法被稱為啟發(fā)式算法的原因。

A*算法實現過程中,需要建立兩個列表[14]:open表和close表。open表中存放的是當前節(jié)點周圍的可以訪問到的節(jié)點,這些節(jié)點不僅包括水平和垂直方向上的,還包括對角線上的節(jié)點,最多就是該節(jié)點周圍的8個節(jié)點,放在open表里的節(jié)點必須是非障礙物節(jié)點且不在open表或close表中的。close表則存放已經訪問過的節(jié)點。

首先,尋路的第一步應該是簡化搜索區(qū)域,即用一個二維數組來表示搜索區(qū)域,網格中的每一個方格可以用二維數組中的坐標來表示。其中方格用藍色表示為不可通過,用黑色表示即為可通過,并且路徑也可以被描述為從A到B所經歷的方塊的集合。其中的每一個格子會被當做節(jié)點對待,因為這樣做有利于描述不規(guī)則的地圖圖形,節(jié)點能夠被放置在地圖中的任何位置,可以在格子的中心,也可以在格子的邊界[15]。若直接用方格來描述,會比較麻煩,而且不夠準確。

其次,將起點A作為待處理節(jié)點存放到open表中,由于open表中此時只有A節(jié)點,所以A節(jié)點即為當前點,然后把起始點A從open表中取出放入關閉列表中。判定A點周圍可以通過的點并加入open表中,此時open表中會有8個節(jié)點,即為A節(jié)點周圍的8個格子,將A點設置成這些可通過點的“父方格”。

每個加入開啟列表里的方格都有一個F值,標注出了起始點周圍8個節(jié)點對應的F、G、H的值。經過多次取出,open表里F值最小的方格加入close表中,并比較G值大小來決定是否改變當前點的父方格,最終就可以得到close表中的格子集合,即所要求得的最短路徑。可以知道從起始點到目標點路徑規(guī)劃中所需要用到的點,及各個點對應的值的大小、指針指向等信息。如果從目標點開始沿著其指向父方格的指針開始尋找,最終能夠到達起始點,這條路徑就是通過A*算法來規(guī)劃出的最優(yōu)路徑。

3.2 A*算法實現

具體實現流程圖如圖6所示。

圖6 A*算法實現流程

4 上位機界面設計

4.1 串口通信界面設計

本設計使用Labwindows CVI進行上位機界面設計,首先編寫串口通信界面,如圖7所示。

圖7界面左邊幾個復選按鈕可以實現串口、波特率、校驗位等選擇,第一個文本框可以輸入字符,通過串口發(fā)送到下位機,第二個串口可以接收下位機發(fā)過來的傳感器數據。具體傳感器數據格式如圖8所示。

陀螺儀角度數據與超聲傳感器距離數據由分號隔開。第一部分的陀螺儀字符型數據被修改成整型數據,默認單位為度(°);第二部分為超聲傳感器發(fā)送的5個方向的距離數據,默認單位為厘米(cm),認為其可使用距離為30～ 100 cm;第三部分為里程計所獲取數據,用“P”與紅外測距傳感器隔開,默認單位為厘米(cm);第四部分為紅外測距傳感器發(fā)送的4個方向(左右側面各一個,正前方左右輪處各一個),默認單位為厘米(cm)。需要指出的是,根據實際測試,某一方向上紅外傳感器如果沒有感知到障礙物,就發(fā)送“99”,因此,當收到“99”時認為距離足夠遠,這里是由于紅外傳感器測距方位在4～30 cm之間,不會達到99。

4.2 環(huán)境地圖繪制界面設計

接下來編寫環(huán)境地圖繪制界面,要能夠在界面上實時繪制地圖,且在上位機利用獲取的全局地圖使用A*算法進行路徑規(guī)劃,如圖9所示。

圖9設計了環(huán)境網格地圖,可以在移動機器人自學習的時候進行起始點和目標點的設置,進行路徑規(guī)劃,能夠將A*算法計算的關鍵節(jié)點顯示出來,同時顯示關鍵節(jié)點的距離角度信息。該界面是串口通信界面的子界面,能夠點擊圖7中的“打開地圖”按鈕進入,點擊圖9的“退出”按鈕,退回到圖7界面。

5 實驗結果及分析

5.1 A*算法在上位機的仿真

為了驗證A*算法的正確性,在上位機上對A*算法用VC做了仿真測試。分別選取U型圖、Z型圖來作為環(huán)境地圖進行測試。實驗結果如圖10所示。

圖9 環(huán)境地圖界面

圖10 A*算法驗證

圖10(a)是一個22×21的網格,設起始點為(0,3),目標點為(7,5)。其中白色圓圈表示的路徑即為最短路徑,白色矩形路徑為其他路徑,只需要證明白色圓圈走過的路徑小于其他路徑的距離,即可證明A*算法得出的路徑即為最短路徑。通過計算,可以得到白色圓圈經過的距離為10×23+14×12=398,白色矩形路徑經過的距離為10× 25+14×11=404。很明顯398小于404,并且在確定此起始點和目標點后,找不出有比白色圓圈路徑更短的路徑,因此在此環(huán)境中,A*算法得到的是最短路徑。

圖10(b)是一個23×24的網格,我們設起始點為(2,1),目標點為(19,19)。其中白色圓圈表示的路徑仍為最短路徑,白色矩形路徑為其他路徑。通過計算,可以得到白色圓圈經過的距離為10×31+14×12=478,白色矩形路徑經過的距離為10×30+14×13=482。很明顯478小于482,并且在確定此起始點和目標點后,找不出有比白色圓圈更短的路徑,因此在此環(huán)境中,A*算法得到的是最短路徑。

5.2 利用傳感器繪制環(huán)境地圖

為了驗證移動機器人傳感器獲取的環(huán)境信息,在實驗室搭建環(huán)境進行測試。圖11(a)、(c)為實際環(huán)境,(b)、(d)為對應的傳輸到上位機的傳感器數據經過解析之后繪制出來的地圖,可見基本上障礙物信息能夠繪制出來。地圖中會存在一些數據的缺失,這是由于移動機器人運行時紅外傳感器探測過程中的誤差導致,但是整體數據說明探測情況還是基本符合實際地圖的。

圖11 移動機器人環(huán)境地圖繪制

5.3 A*算法進行路徑規(guī)劃

在上位機能夠進行環(huán)境地圖繪制的基礎上使用A*算法進行路徑規(guī)劃,并且通過路徑規(guī)劃得到關鍵點指導移動機器人自學習。對于環(huán)境C進行A*算法處理,圖12中節(jié)點1顯示的是起始點,節(jié)點7為目標點,其中灰色曲線為算法規(guī)劃的路徑曲線,選取一些關鍵節(jié)點傳輸給移動機器人,讓其進行自主運行。

從圖12(a)、(b)兩張圖中可以看出,關鍵點-1即第一個關鍵點(圖中節(jié)點2)與起點(圖中節(jié)點1)的距離為200 cm,與其角度為0度,它們之間有9個格子,再加上關鍵點共10個格子,乘以20 cm的比例尺,得到200 cm是正確的結果,且關鍵點1與起始點在同一直線上,所以其間角度的確實為0度。圖(b)中對于關鍵點0(圖中節(jié)點3),即表示第二個關鍵點(圖中節(jié)點3)與第一個關鍵點(圖中節(jié)點2)的距離為28 cm,與其角度為45度,它們之間有1個格子,再加上特殊點共2個格子,但對角線的距離應是直角邊的1.4倍,乘以14 cm的比例尺,得到28 cm是正確的結果。故在上位機得到的關于關鍵點間的距離和角度值是正確的。

圖12 關鍵點角度和距離的測量曲線

結 語

本文設計了可以探測未知環(huán)境的移動機器人,能夠通過傳感器獲取移動機器人的位姿信息,實現了下位機與上位機的無線通信,在此基礎上,利用A*算法實現了移動機器人路徑規(guī)劃和指導移動機器人自主運行。搭建一些實驗環(huán)境,通過移動機器人運行結果說明有一定的效果,當然還存在一些不足,譬如對于動態(tài)障礙物就無法實時更新地圖進行重新規(guī)劃,接下來會對于動態(tài)路徑規(guī)劃作進一步的研究。

[1]許亞.基于強化學習的移動機器人路徑規(guī)劃研究[D].濟南:山東大學,2013:78-83.

[2]Kazuo Sugihara,Ichiro Suzuki.Distributed Algorithms for Formation of Geometric Patterns with Many Mobile Robots [J].Journal of Robotic Systems,1996,13(3):127-139.

[3]張洪,錢勝,陳路.多傳感器在確定智能小車安全區(qū)域中的應用[J].傳感器與微系統,2013,32(12):145-147.

[4]韓保亮.基于多傳感器的機器人環(huán)境建模與導航[D].南京:南京師范大學,2013:2-4.

[5]莊春華,趙治華,張益青,等.衛(wèi)星導航定位技術綜述[J]. 2014,3(2):34-36.

[6]Willms A R,Yang S X.An efficient dynamic system for realtime robot-path planning[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B:Cybernetics,2006,36 (4):755-766.

[7]H R Everett.Sensors for Mobile Robots[M].New-York:Theory and Applications,1995:568-789.

[8]Ulrich I,Borenstdn J.VFH+:Reliable obstacle avoidance for fast mobile robots[C]//Proceedings of the 1998 IEEE International Conference on Robotics and Automation,1998.

[9]王耀賓.超聲導航移動機器人系統設計及模糊避障技術研究[D].青島:中國海洋大學,2008:1-3.

[10]Tao Gao,Zhen Jing Yao.Sensors Network for Ultrasonic Ranging System[J].International Journal of Advanced Pervasive and Ubiquitous Computing(IJAPUC),2013,5(3): 47-59.

[11]劉軍.基于改進蟻群算法的移動機器人路徑規(guī)劃研究[D].鄭州:鄭州大學,2010:92-95.

[12]Jin F,Hong B.Path planning for free-flying space robot using ant algorithm[J].Robot,2002,24(6):526-529.

[13]汪浩杰.多機器人系統中圍捕策略的研究[D].武漢:華中科技大學,2007:37-43.

[14]Kazuo Sugihara,Ichiro Suzuki.Distributed Algorithms for Formation of Geometric Patterns with Many Mobile Robots [J].Journal of Robotic Systems,1996,13(3):127-139.

[15]張前哨.基于A*算法的地圖尋徑的研究[D].武漢:武漢科技大學,2005.

張燕(講師),主要從事嵌入式系統以及移動機器人的研究。

(責任編輯:薛士然 收修改稿日期:2016-05-24)

Usage of A*Algorithm in Self-learning of Mobile Robot

Zhang Yan,Xu Yichao,Sheng Zhou
(Jinling College of Nanjing University,Nanjing 210089,China)

The unknown environment is studied by the sensors to get the environment map,then A*algorithm is used to get the optimal path planning.The key nodes are choosed by the algorithm and then are passed to the mobile robot.The mobile robot can move autonomously according to these nodes in the same environment.The experiment results show that the robot can run well.

path planning;A*algorithm;self-learning;2D map

TP751.1

:A

省部級江蘇省高校自然科學研究面上項目申報書(15KJB510013)。