任群

（亳州學(xué)院電子與信息工程系，安徽亳州236800）

高效的路徑規(guī)劃算法能夠使移動(dòng)機(jī)器人在有障礙的場地自主地移動(dòng)，以滿足人們對(duì)機(jī)器人的需求。根據(jù)與環(huán)境交互的特點(diǎn)，人工智能方法可分為三類：無監(jiān)督學(xué)習(xí)、監(jiān)督學(xué)習(xí)和強(qiáng)化學(xué)習(xí)[1]。增強(qiáng)學(xué)習(xí)（Reinforcement Learning，RL）是人工智能算法中的一種，其目的是使（動(dòng)態(tài)）環(huán)境中的Agent（實(shí)體）根據(jù)當(dāng)前的狀態(tài)，通過選擇合適的策略，最大限度地提高累計(jì)獎(jiǎng)勵(lì)。Agent是一個(gè)自治的智能體，即使外部環(huán)境提供的信息很少，Agnet也可以獲得環(huán)境狀態(tài)的適當(dāng)評(píng)估值，從而修改自己的操作策略以適應(yīng)環(huán)境[2]。機(jī)器人Agent是通過無線網(wǎng)絡(luò)（例如基于Ipv6協(xié)議的移動(dòng)網(wǎng)絡(luò)[3]）進(jìn)行信息交互。Q-learning[4]是一種獨(dú)立于模型的增強(qiáng)學(xué)習(xí)技術(shù)，它可以用來為任何給定的馬爾可夫決策過程（MarkovDecisionProcess,MDP）找到最佳的行動(dòng)選擇策略，適合于多機(jī)器人協(xié)作系統(tǒng)。Q-learning的優(yōu)點(diǎn)之一是不需要環(huán)境模型，其獨(dú)特之處在于它能在即時(shí)獎(jiǎng)勵(lì)和延遲獎(jiǎng)勵(lì)之間做出選擇。每次做決策的時(shí)候，機(jī)器人會(huì)觀察當(dāng)前狀態(tài)，選擇一個(gè)動(dòng)作，并轉(zhuǎn)移到下一個(gè)狀態(tài)。最終的目標(biāo)是找出能使未來累計(jì)收益最大化的動(dòng)作序列，從而產(chǎn)生最短的路徑。

現(xiàn)有的機(jī)器人路徑規(guī)劃算法包括全局路徑規(guī)劃和本地路徑規(guī)劃[5]，解決機(jī)器人路徑規(guī)劃問題的方法可以分為經(jīng)典方法和啟發(fā)式方法[6]。參考文獻(xiàn)[7]概述了三種機(jī)器人路徑規(guī)劃的經(jīng)典方法（勢(shì)場法、單元分解方法和路線圖法）。參考文獻(xiàn)[8]提出了一種介于勢(shì)場法（PotentialField）和遺傳算法之間的機(jī)器人路徑規(guī)劃系統(tǒng)。參考文獻(xiàn)[9]利用可視圖法（Visibility graphapproach）來生成一系列中間目標(biāo)，幫助機(jī)器人達(dá)到最終位置。經(jīng)典方法不能保證路徑的最優(yōu)性，尤其是在有障礙和動(dòng)態(tài)的環(huán)境中，因此研究人員逐漸把目光轉(zhuǎn)移到啟發(fā)式方法上。M.Al-Sagban和R.Dhaouadi提出了一種基于無源導(dǎo)航的新型神經(jīng)網(wǎng)絡(luò)系統(tǒng)，并將其應(yīng)用于在非結(jié)構(gòu)化室內(nèi)環(huán)境中的機(jī)器人路徑規(guī)劃問題，機(jī)器人能夠在沒有任何先驗(yàn)知識(shí)的情況下安全地朝著目標(biāo)位置移動(dòng)[10]。參考文獻(xiàn)[11]中的機(jī)器人路徑規(guī)劃針對(duì)多個(gè)機(jī)器人的場景，利用模糊邏輯控制器（Fuzzy logic Controllers，F(xiàn)LC）來為機(jī)器人做路徑規(guī)劃決策。遺傳算法（GA）和模糊算法被應(yīng)用于全局路徑規(guī)劃，參考文獻(xiàn)[12]利用GA在動(dòng)態(tài)環(huán)境中找到最佳路徑。

1 基于Q-learning的路徑規(guī)劃

基于人工智能算法的機(jī)器人路徑規(guī)劃系統(tǒng)架構(gòu)如圖1所示。

圖1 路徑規(guī)劃系統(tǒng)的架構(gòu)

假設(shè)環(huán)境是一個(gè)有限狀態(tài)的馬爾可夫過程，在每一次迭代過程中，機(jī)器人會(huì)從有限的動(dòng)作集合中選擇動(dòng)作a，執(zhí)行動(dòng)作a之后，環(huán)境會(huì)返回回報(bào)信號(hào)例如，在時(shí)刻，機(jī)器人選擇動(dòng)作a，此時(shí)，狀態(tài)從變?yōu)閠+1，并得到回報(bào)t。在采取策略的情況下，狀態(tài)的值函數(shù)為：

于是，Q值的表達(dá)式為：

在Q-learning算法的執(zhí)行過程中，機(jī)器人會(huì)觀察當(dāng)前的狀態(tài)，然后選擇動(dòng)作，執(zhí)行動(dòng)作之后轉(zhuǎn)移到下一狀態(tài)，機(jī)器人會(huì)從環(huán)境得到回報(bào)，該回報(bào)會(huì)被用來更新Q值。更新Q值的迭代式為：

2 搜索策略

當(dāng)機(jī)器人處于一個(gè)新的狀態(tài)時(shí)，它需要從動(dòng)作集合中選擇一個(gè)動(dòng)作。機(jī)器人應(yīng)該盡可能多地嘗試不同的動(dòng)作來完成任務(wù)，但這種操作會(huì)影響算法的收斂。因此，有必要設(shè)計(jì)一個(gè)合適的搜索策略。搜索策略可分為兩類：無定向和定向。無定向搜索策略不使用學(xué)習(xí)結(jié)果來指導(dǎo)動(dòng)作的選擇，而定向搜索策略則采用學(xué)習(xí)結(jié)果來指導(dǎo)搜索方向。采用Boltzmann[13]策略，在狀態(tài)執(zhí)行動(dòng)作a的概率是：

3 實(shí)驗(yàn)結(jié)果及分析

PlayerProject是一個(gè)為機(jī)器人和傳感器系統(tǒng)研發(fā)免費(fèi)軟件的項(xiàng)目[14]，其組件包括Player網(wǎng)絡(luò)服務(wù)器和Stage機(jī)器人平臺(tái)模擬器。雖然難以獲得準(zhǔn)確的統(tǒng)計(jì)數(shù)據(jù)，但Player Project是最受研究人員歡迎的開源機(jī)器人接口之一[15]。Player可以運(yùn)行在與posix兼容的操作系統(tǒng)上，包括Linux、Mac OS X、Solaris、BSD衍生版本和MicrosoftWindows。Player可以是一個(gè)“機(jī)器人抽象層”，所有的設(shè)備都被抽象成一組預(yù)定義的接口。Player支持各種各樣的硬件（傳感器設(shè)備和機(jī)器人平臺(tái)），包含支持多種編程語言的客戶端庫，包括C、C++、Python和Ruby。Stage是一個(gè)建立在FLTK之上的二維多機(jī)器人模擬器，Stage提供了一個(gè)基本的仿真環(huán)境，可以在一段時(shí)間內(nèi)對(duì)數(shù)百個(gè)機(jī)器人進(jìn)行建模。Stage可以單獨(dú)使用，通過用戶定義的控制程序來模擬機(jī)器人的行為；Stage也可以與Player交互，允許Player通過Player界面訪問模擬傳感器和設(shè)備。

實(shí)驗(yàn)中，參數(shù)的取值為0.8，使用C++程序?qū)崿F(xiàn)了本文提出的算法。利用模擬器生成迷宮，機(jī)器人使用基于Q-learning的路徑規(guī)劃在迷宮中生成路徑。首先考察算法在一個(gè)小迷宮中的性能，該小迷宮如圖2所示。機(jī)器人從狀態(tài)1出發(fā)，到達(dá)終點(diǎn)狀態(tài)8。

圖2 小迷宮

對(duì)比采用和不采用Boltzmann作為搜索策略（即公式（5））的搜索次數(shù)，實(shí)驗(yàn)結(jié)果如圖3所示。由圖3可知，在非終止?fàn)顟B(tài)（即狀態(tài)0到7），采用Boltzmann搜索策略的搜索次數(shù)明顯要少于傳統(tǒng)策略的搜索次數(shù)。

圖3 搜索次數(shù)對(duì)比（小迷宮）

再利用一個(gè)大迷宮評(píng)估算法的性能，大迷宮如圖4所示。對(duì)比采用和不采用Boltzmann作為搜索策略的搜索次數(shù)，實(shí)驗(yàn)結(jié)果如圖5所示。由圖5可知，在非終止?fàn)顟B(tài)（即狀態(tài)0到34），采用Boltzmann搜索策略的搜索次數(shù)明顯要少于傳統(tǒng)策略的搜索次數(shù)。在終止?fàn)顟B(tài)35時(shí)，搜索次數(shù)突然增加，這是因?yàn)榇藭r(shí)需要通過增加搜索次數(shù)來使算法進(jìn)一步收斂。

圖4 大迷宮

圖5 搜索次數(shù)對(duì)比（大迷宮）

4 結(jié)論

基于人工智能算法的機(jī)器人路徑規(guī)劃的任務(wù)是確定一種最優(yōu)的策略，以最大限度地獲得回報(bào)為目標(biāo)。當(dāng)機(jī)器人處于一個(gè)新的狀態(tài)時(shí)，它需要從動(dòng)作集中選擇一個(gè)動(dòng)作并執(zhí)行它。為了提高算法的質(zhì)量，有必要對(duì)動(dòng)作的選擇應(yīng)用搜索策略。Boltzmann策略是搜索策略之一，它是由Boltzmann分布推導(dǎo)而來的。實(shí)驗(yàn)結(jié)果表明，Boltzmann策略通過減少搜索次數(shù)，提高了算法的效率。

[1]Bush R R,Mosteller F.Stochastic models for learning[J].Mathematical Gazette,1955,43(39):237.

[2]魏超,余臘生.分布式環(huán)境下基于多Agent的人群模擬的研究與應(yīng)用[J].遵義師范學(xué)院學(xué)報(bào),2011,13(3):72-77.

[3]唐曄.IPv6的展望與策略[J].遵義師范學(xué)院學(xué)報(bào),2004,6(3):91-93.

[4]Watkins CJCH.LearningfromDelayed Rewards[J].Robotics&Autonomous Systems,1989,15(4):233-235.

[5]Mac T T,Copot C,Tran D T,et al.Heuristic approaches in robot path planning:A survey[J].Robotics&Autonomous Systems,2016,86:13-28.

[6]Masehian E,Sedighizadeh D.Classic and Heuristic Approaches in Robot Motion Planning-A Chronological Review[J].Proc World Academy of Science Engineering&Technology,2007，(1)：101-106.

[7]Eda M.Roadmap methods vs.cell decomposition in robot motion planning[C].Wseas International Conference on Signal Processing,Robotics and Automation.World Scientific and Engineering Academy and Society(WSEAS),2007.127-132.

[8]Cosío F A,Casta?eda M A P.Autonomous robot navigation using adaptive potential fields[J].Mathematical&Computer Modelling,2004,40(9-10):1141-1156.

[9]Ma Y,Zheng G,Perruquetti W.Cooperative path planning for mobile robots based on visibility graph[C].Control Conference,IEEE,2013.4915-4920.

[10]Al-Sagban M,Dhaouadi R.Neural-based navigation of a differential-drive mobile robot[C].International Conference on Control Automation Robotics&Vision,IEEE,2012.353-358.

[11]Pradhan S K,Parhi D R,Panda A K.Neuro-fuzzy technique for navigation of multiple mobile robots[J].Fuzzy Optimization&Decision Making,2006,5(3):255-288.

[12]Farshchi S M R,Nezhadhoseini S A,Mohammadi F.A Novel Implementation of G-Fuzzy Logic Controller Algorithm on Mobile Robot Motion Planning Problem[J].Computer&Information Science,2011,4(2):102.

[13]Bach A.The Maxwell-Boltzmann distribution derived from Bose-Einstein statistics[J].Physics Letters A,1988,134(1):1-3.

[14]Gerkey B P,Vaughan R T,Howard A.The Player/Stage Project:Tools for Multi-Robot Distributed Sensor Systems[C].International Conference on Advanced Robotics,2003.317-323.

[15]CollettTHJ,MacDonald BA,Gerkey BP.Player 2.0:Toward a practical robotprogramming framework[C].Proceedingsof the Australasian Conference on Robotics and Automation,2005.145.