任群

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

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

現(xiàn)有的機器人路徑規(guī)劃算法包括全局路徑規(guī)劃和本地路徑規(guī)劃[5]，解決機器人路徑規(guī)劃問題的方法可以分為經(jīng)典方法和啟發(fā)式方法[6]。參考文獻[7]概述了三種機器人路徑規(guī)劃的經(jīng)典方法（勢場法、單元分解方法和路線圖法）。參考文獻[8]提出了一種介于勢場法（PotentialField）和遺傳算法之間的機器人路徑規(guī)劃系統(tǒng)。參考文獻[9]利用可視圖法（Visibility graphapproach）來生成一系列中間目標，幫助機器人達到最終位置。經(jīng)典方法不能保證路徑的最優(yōu)性，尤其是在有障礙和動態(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)境中的機器人路徑規(guī)劃問題，機器人能夠在沒有任何先驗知識的情況下安全地朝著目標位置移動[10]。參考文獻[11]中的機器人路徑規(guī)劃針對多個機器人的場景，利用模糊邏輯控制器（Fuzzy logic Controllers，F(xiàn)LC）來為機器人做路徑規(guī)劃決策。遺傳算法（GA）和模糊算法被應(yīng)用于全局路徑規(guī)劃，參考文獻[12]利用GA在動態(tài)環(huán)境中找到最佳路徑。

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

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

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

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

于是，Q值的表達式為：

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

2 搜索策略

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

3 實驗結(jié)果及分析

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

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

圖2 小迷宮

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

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

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

圖4 大迷宮

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

4 結(jié)論

基于人工智能算法的機器人路徑規(guī)劃的任務(wù)是確定一種最優(yōu)的策略，以最大限度地獲得回報為目標。當機器人處于一個新的狀態(tài)時，它需要從動作集中選擇一個動作并執(zhí)行它。為了提高算法的質(zhì)量，有必要對動作的選擇應(yīng)用搜索策略。Boltzmann策略是搜索策略之一，它是由Boltzmann分布推導(dǎo)而來的。實驗結(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].遵義師范學院學報,2011,13(3):72-77.

[3]唐曄.IPv6的展望與策略[J].遵義師范學院學報,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.