張?jiān)娏?/p>

（沈陽職業(yè)技術(shù)學(xué)院，沈陽 110045）

0 引言

科技的進(jìn)步能夠改善人類的生活質(zhì)量以及提高生活的便利性，因此機(jī)器人的相關(guān)研究一直是許多科學(xué)家致力研究的方向。隨著人工智能、機(jī)器視覺與微處理器的迅速發(fā)展，自動(dòng)化的應(yīng)用也越來越普遍，智能機(jī)器人的相關(guān)研究也越來越廣泛，大至太空探索，小到制造自動(dòng)化及服務(wù)型機(jī)器人，處處都可以發(fā)現(xiàn)智能機(jī)器人成功的應(yīng)用。

目前，關(guān)于移動(dòng)式機(jī)器人的應(yīng)用已經(jīng)相當(dāng)?shù)膹V泛。移動(dòng)式機(jī)器人也可以在日常生活中給予人們越來越多的幫助，在日本娛樂型機(jī)器人的研究發(fā)展更是迅速。自從1999年Sony 公司發(fā)布的AIBO機(jī)器狗大賣之后，2000年又開發(fā)出多款擬人化的機(jī)器人，如日本本田發(fā)布會(huì)爬樓梯的Asimo，Sony發(fā)布了會(huì)隨音樂跳舞和與人對話的QRIO機(jī)器人等。Roomba吸塵機(jī)器人由麻省理工學(xué)院（MIT）人工智能驗(yàn)室研發(fā)，由iRobot公司制造。它主要用在居家清潔上，能像吸塵器一樣自動(dòng)清理地板，碰到墻壁或障礙物，也能輕巧彈開。另外，日立公司發(fā)布了功能與Roomba 類似的家用清潔機(jī)器人，機(jī)器人可以移動(dòng)至房間的角落，可動(dòng)吸塵口就能夠自動(dòng)伸出進(jìn)行清掃。

在各種應(yīng)用中，移動(dòng)式機(jī)器人必須在特定環(huán)境下完成指定的動(dòng)作，因此到達(dá)目標(biāo)的路徑規(guī)劃相當(dāng)重要[1]。移動(dòng)機(jī)器人的路徑規(guī)劃決定了移動(dòng)機(jī)器人一切的行動(dòng)，路徑規(guī)劃的策略包括了路徑的規(guī)劃及導(dǎo)航、尋找最優(yōu)的路徑、以及閃避障礙等。移動(dòng)機(jī)器人的路徑規(guī)劃與導(dǎo)航是控制移動(dòng)機(jī)器人行動(dòng)中最重要的研究內(nèi)容。路徑規(guī)劃的目標(biāo)是在最短時(shí)間內(nèi)，使用最短的距離朝著目標(biāo)標(biāo)地物前進(jìn)，且不能與其他障礙物相互碰撞。在移動(dòng)機(jī)器人完成各種任務(wù)時(shí)，無人導(dǎo)引控制的技術(shù)起著關(guān)鍵的作用，也是機(jī)器人的研究上一個(gè)重要的指標(biāo)。根據(jù)無人導(dǎo)引控制的技術(shù)，可將機(jī)器人分類為有軌式移動(dòng)機(jī)器人與無軌式移動(dòng)機(jī)器人兩類。有軌式的引導(dǎo)技術(shù)研究發(fā)展已經(jīng)成熟，目前大多研究致力于無軌式移動(dòng)機(jī)器人。

本文以制造業(yè)中的無軌式機(jī)器人為例，以多道加工工序中的螺絲安裝為任務(wù)，提出一種基于差分進(jìn)化算法的移動(dòng)式機(jī)器人的最優(yōu)路徑規(guī)劃方法，使得機(jī)器人在各個(gè)加工床上螺絲安裝的加工時(shí)間最短。實(shí)驗(yàn)結(jié)果顯示，在20個(gè)加工床的情況下，該方法能夠得到滿意的結(jié)果。

1 移動(dòng)機(jī)器人路徑規(guī)劃

在移動(dòng)機(jī)器人的移動(dòng)路徑上，為了在最小時(shí)間完成所有的加工工序，隨時(shí)都要憑著實(shí)時(shí)的環(huán)境信息，來更新機(jī)器人的位置及目標(biāo)點(diǎn)之間路徑。首先描述本文的移動(dòng)機(jī)器人規(guī)劃問題：給定n個(gè)加工床{b1,b2,…,bn}，它們存在于一個(gè)二維地圖上，我們的目的是機(jī)器人經(jīng)過所有的加工床，滿足并避免重復(fù)走過相同的路徑，即尋找一條從起點(diǎn)到目標(biāo)點(diǎn)的最短距離路徑：

其中，di,j是加工床bi,bj之間的距離。

目前求解該問題的方法大多集中在啟發(fā)式解法。這些啟發(fā)式解法可以分成如下四種[2,3]。

1）窮盡搜索法

我們以最直觀的遍歷方法一一計(jì)數(shù)來求解最優(yōu)路徑，亦即找出所有可能的路徑，計(jì)算每條路徑的成本后，找出其最小者。如果有n個(gè)加工床，那么共有(n-1)!條路徑。若n=26，則有25! 條不同路徑。假設(shè)計(jì)算機(jī)每秒可計(jì)算100條路徑的成本，求出所有路徑的成本就需時(shí)五千億年，這樣造成較低的計(jì)算效率。

2）分支界定法

最優(yōu)路徑問題的解可以樹(tree) 表示，因此我們需找出最短距離路徑的樹，分支界定法搜尋此最優(yōu)解的思想為：將樹形不斷分支，但隨時(shí)以問題的條件限制分支的繼續(xù)，即如果知道最優(yōu)解不會(huì)出現(xiàn)在通過此點(diǎn)的路徑，則不必繼續(xù)分支，因此所需搜尋的路徑將大大減少。

3）動(dòng)態(tài)規(guī)劃

以動(dòng)態(tài)規(guī)劃求解，其計(jì)算復(fù)雜度 (computational complexity) 仍然呈指數(shù)上升，對目前及未來的計(jì)算機(jī)而言，一個(gè)計(jì)算復(fù)雜度呈指數(shù)上升的問題，在 n相當(dāng)大時(shí)仍無法解決。

4）近似法

既然最優(yōu)路徑問題是個(gè)難題，我們可以退而求其次找一個(gè)近似解，這種解法從直觀而來，稱為最近鄰法 (nearest-neighbor method )。 例如，從加工床 1 開始，先找最近 1 的加工床 d1，次找最接近 d1 的加工床 d2，再找最接近d2 的加工床d3，，直至找出所有的加工床，將最后一個(gè)加工床與 1 連接，即得所求的路徑。

2 基于差分進(jìn)化算法的路徑規(guī)劃

差分進(jìn)化算法( Differential Evolution Algorithm，DEA)是 R.Storn,及 Price,K.在 1997 年第一次提出[4]，它是一種以群體為基礎(chǔ)，來進(jìn)行空間中的隨機(jī)搜尋的優(yōu)化方法。相比經(jīng)典的遺傳算法，差分進(jìn)化算法具有實(shí)現(xiàn)簡單，參數(shù)少，收斂速度快的優(yōu)勢。而且不管初始解的好壞，它都可以找到全部可行域的最優(yōu)解。

差分進(jìn)化算法在搜尋空間中，每一個(gè)向量代表一個(gè)解，稱為解向量，每一個(gè)解向量在搜尋空間中各自擁有方向和大小，解向量不用解向量之間的差距，使每一個(gè)解向量不斷地往最優(yōu)解方向前進(jìn)，以達(dá)到最好的位置。差分進(jìn)化算法如圖1所示。

圖1 差分進(jìn)化算法步驟

差分進(jìn)化算法在解向量的進(jìn)化中，經(jīng)過迭代的方式，調(diào)整出最正確的參數(shù)解，來更新種群，演化的過程中包括了變異、交叉及選擇方法。變異是由三個(gè)不同的解向量產(chǎn)生一個(gè)差分向量。交叉是復(fù)制差分向量中的某段位置來覆蓋父代中相對應(yīng)的位置，覆蓋的長度由一個(gè)解變量決定。選擇是評估父代與子代的適應(yīng)值，兩者之中刪除較差的保留最優(yōu)的。一直重新配置，最后差分根據(jù)目標(biāo)函數(shù)值找出最優(yōu)解。

在差分進(jìn)化算法中，其每個(gè)候選解(candidate solution)即為一個(gè)解向量，變異策略是在差分階段找到的解向量中隨機(jī)選取三個(gè)不同的解向量，彼此之間相互交叉運(yùn)算，得到一個(gè)新的個(gè)體，這個(gè)新個(gè)體又稱為差分向量Dv (Difference vector)：

其中，p1, p2, p3為種群P(t)中的個(gè)體，F(xiàn)為比例系數(shù)。計(jì)算后得到的差分向量Dv不再是整數(shù)，我們按照值的大小進(jìn)行排序，將所得到的序號(hào)來代替差分向量Dv，作為變異后的個(gè)體。類似的，交叉之后也會(huì)產(chǎn)生類似的無效解，也是按照值的大小進(jìn)行排序，將所得到的序號(hào)來代替交叉后的解向量。在有相同數(shù)值的情況下，隨機(jī)選擇先后順序。差分進(jìn)化算法的目標(biāo)函數(shù)值定義為式(1)所示。基于差分進(jìn)化的路徑規(guī)劃算法步驟如下。

1）初始化代數(shù)初始化：t=0；初始化種群P(t)，種群中每一個(gè)個(gè)體代表一個(gè)可行的路徑；

2）按式(2)執(zhí)行個(gè)體變異操作，生成新的P(t)；

3）執(zhí)行個(gè)體交叉操作，生成新的P(t)；

4）按照式(1)計(jì)算目標(biāo)函數(shù)值，評價(jià)群體P(t)的優(yōu)劣，選擇目標(biāo)函數(shù)值最小的個(gè)體；

5）停機(jī)條件判斷：當(dāng)滿足停機(jī)條件時(shí)，輸出當(dāng)前最優(yōu)個(gè)體，否則繼續(xù)；

6）更新 P(t)，t=t+1，轉(zhuǎn)到 2）。

3 實(shí)驗(yàn)與結(jié)果

考慮20個(gè)加工床的問題，差分進(jìn)化算法中種群的規(guī)模為100，將差分進(jìn)化算法中種群的每個(gè)個(gè)體編碼為一個(gè)長度為20的向量。F設(shè)為0.2，最大迭代次數(shù)設(shè)為300。由差分進(jìn)化算法確定得到的最優(yōu)路徑如圖2所示，其對應(yīng)的最短距離為219米，時(shí)間為298秒。從圖2中可以看出：在時(shí)間上與路徑距離上都還是滿意的。

圖2 差分進(jìn)化算法得到的最優(yōu)路徑

4 結(jié)論

如何在最短時(shí)間內(nèi)，使用最短的距離讓移動(dòng)式機(jī)器人朝著目標(biāo)地前進(jìn)，這是路徑規(guī)劃的基本目標(biāo)。本文以制造業(yè)機(jī)器人為例，以多道加工工序中的螺絲安裝為任務(wù)，提出一種基于差分進(jìn)化算法的移動(dòng)式機(jī)器人的最優(yōu)路徑，使得機(jī)器人的制造加工時(shí)間最短。實(shí)驗(yàn)結(jié)果證明了該方法的有效性

[1] M.S. Lee, M.J. Jung and J.H. Kim, “Evolutionary programming-based fuzzy logic path planner and follower for mobile robots,”[C], Proceedings of the 2000 Congress on Evolutionary Computation, vol. 1, pp. 139 - 144, 2000.

[2] 涂序彥. 人工智能: 回顧與展望[M]. 北京: 科學(xué)出版社,2006.

[3] 閻平凡, 張長水. 人工神經(jīng)網(wǎng)絡(luò)與模擬進(jìn)化計(jì)算[M]. 北京: 清華大學(xué)出版社, 2000.

[4] R. Storn, and K. Price, “Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces Storn,” Journal of Global Optimization[J], 1997,11(4): 341-359.