汪 琴 ,張波濤 ,宋士吉

(1.杭州電子科技大學(xué)自動化學(xué)院,浙江杭州 310018; 2.清華大學(xué)自動化系,北京 100084)

1 引言

移動機器人目標(biāo)搜索通常是指采用一個或多個機器人對工作環(huán)境中的單個或多個目標(biāo)進行信息采集或操作,屬于機器人領(lǐng)域的重要共性技術(shù)之一,被廣泛用于家庭服務(wù)、地震/火災(zāi)搜救、工業(yè)故障檢測、深海/外太空環(huán)境探索等[1–2].移動機器人目標(biāo)搜索涉及運動規(guī)劃、機器視覺、運動控制、SLAM(simultaneous localization and mapping)等多個領(lǐng)域,其中,路徑規(guī)劃是其進行任務(wù)決策、完成復(fù)雜工作的前提[3].移動機器人的目標(biāo)搜索路徑規(guī)劃屬于全局路徑規(guī)劃中的任務(wù)規(guī)劃,其主要目的是按照任務(wù)需求生成一條最優(yōu)或次優(yōu)的可行路徑[3–4].

雖然多機器人協(xié)作搜索具有更高的效率,但受運輸能力、成本所限,現(xiàn)實應(yīng)用中大多采用單體機器人搜索[5–6].目前一些研究者提出了采用最短距離為指標(biāo)生成搜索路徑進行時間優(yōu)化的方法[7],這些方法可以求解出近似最優(yōu)路徑.其后,研究者發(fā)現(xiàn)最短距離為目標(biāo)的搜索方式忽視了任務(wù)中的不確定性因素,假設(shè)目標(biāo)呈均勻分布,搜索距離與時間呈現(xiàn)非線性關(guān)系.然而,該假設(shè)在實際應(yīng)用中難以成立.為解決此問題,Sarmiento等在搜索中引入了概率方法[5],考慮了環(huán)境中的不確定性因素,使運動規(guī)劃更貼近實際,同時也意味著評價標(biāo)準(zhǔn)會因任務(wù)需求不同而多樣化,可為期望時間、最短距離、待遍歷節(jié)點數(shù)等.為了更適應(yīng)于實際環(huán)境需求,Espinoza等在文獻[5]的工作基礎(chǔ)上,將搜索環(huán)境由2D拓展至3D,將移動機械臂的手眼引入概率目標(biāo)搜索,用手眼拓展機器人的搜索能力,減少了本體移動,從而優(yōu)化期望搜索時間[8].文獻[9]提出了以最大可靠性為指標(biāo)的目標(biāo)搜索方法,并分析了文獻[5]所提出的“搜索分布概率是確定的,且搜索過程中移動機器人的速度是恒值”假設(shè)的局限性.近年來國內(nèi)外一些研究者嘗試將搜索模式進行細化研究,但截至目前只分析了有限的幾種模式,如最短距離搜索、最優(yōu)期望時間搜索、最大可靠性搜索等[7].以期望時間為指標(biāo)的路徑規(guī)劃綜合考慮了目標(biāo)分布的不確定性和需求指標(biāo)的多樣性,比采用單一的最短時間、最短距離為指標(biāo)的規(guī)劃方法更能適應(yīng)不同的搜索環(huán)境.

對于以最優(yōu)期望時間為指標(biāo)的移動機器人目標(biāo)搜索,文獻[6]通過在機器人目標(biāo)搜索問題中引入概率指標(biāo),使機器人搜索問題的理論模型與人類尋找物體的策略更相近,該方法的不足之處在于假設(shè)物體在工作環(huán)境下服從均勻分布,且正比于可行域面積,這種假設(shè)過于理想化[5,8],與實際工作環(huán)境相悖,從而導(dǎo)致該方法的表現(xiàn)雖比基于確定性指標(biāo)的方法要好,但理論概率分布模型與實際的誤差會降低搜索效率.在機器人實際工作環(huán)境中,因目標(biāo)物體屬性不同,出現(xiàn)在不同區(qū)域的概率也不同,例如:對于家庭服務(wù)機器人而言,水杯出現(xiàn)在餐廳的概率遠高于出現(xiàn)在廁所的概率,電視遙控器出現(xiàn)在電視附近的概率遠高于其它區(qū)域,目標(biāo)并不呈均勻分布.針對該問題,本文設(shè)計了非均勻分布的概率測算模型,并加入了因時間變化而更新的策略.對于目標(biāo)搜集、火災(zāi)救援等的搜索任務(wù)通常要求機器人搜得物體后返回出發(fā)點,但目前的最優(yōu)期望時間搜索方法局限于只對獲得目標(biāo)前的時間進行優(yōu)化,并未計入機器人攜帶目標(biāo)返回的時間[5,10].本文對期望時間進行了全局優(yōu)化,并采用多項式復(fù)雜度的改進改良圈算法替代了文獻[10]中的次優(yōu)貪心算法,得到全局效果較好的期望觀測點序列.對于局部路徑規(guī)劃采用隨機生成樹(rapid-exploration random tree,RRT)算法,該方法適合解決高維復(fù)雜環(huán)境問題,其缺點為隨機樹的擴展不確定性強,易陷入局部極小值.為解決該問題,本文引入目標(biāo)偏好、碰撞檢測機制和非完整約束對經(jīng)典RRT進行改進.

本文通過以下4部分對所提方法進行分析:首先,對目標(biāo)搜索的概率測算模型進行理論分析;其后,構(gòu)建上層序列規(guī)劃獲得期望觀測點序列,并構(gòu)建了下層節(jié)點間的局部路徑規(guī)劃;最后,通過實驗測試所提算法的全局優(yōu)化能力,并對結(jié)果進行分析與總結(jié).

2 基于期望時間的多目標(biāo)搜索問題

目前,移動機器人目標(biāo)搜索主要方法可分為:連續(xù)方法與離散方法.前者與人類在環(huán)境中搜索物體的方式類似,但存在嚴(yán)重的感知區(qū)域交叉問題,難以進行全局優(yōu)化;后者假設(shè)機器人按一定的順序訪問若干節(jié)點,整個規(guī)劃過程被分為若干觀測子階段.在離散方法中,若搜索物體的方式亦為離散,則會延遲目標(biāo)被發(fā)現(xiàn)的時間,降低目標(biāo)被發(fā)現(xiàn)的概率.鑒于以上問題,一些研究者對離散方法進行改進,采取折中的方式,即:用離散規(guī)劃優(yōu)化節(jié)點序列,采用全景攝像機連續(xù)掃描環(huán)境[5].基于該策略,以期望時間為指標(biāo)的多目標(biāo)搜索問題定義如下:

定義1對于移動機器人的工作空間S,Yk(Xk)是觀測點Xk對應(yīng)的可視區(qū)域,該區(qū)域滿足

觀測點集服從

其中:X為觀測點集,觀測點Xk∈X.基于期望時間的搜索路徑規(guī)劃是在S中生成滿足遍歷所有觀測點并返回起點的期望時間最優(yōu)序列.

在實際工作環(huán)境中,目標(biāo)的屬性不同,出現(xiàn)在不同區(qū)域的概率也不同,例如:電飯煲出現(xiàn)在客廳的概率遠低于出現(xiàn)在廚房的概率,針對目標(biāo)在工作環(huán)境中分布不均勻的問題,本文引入了概率密度因子,以Yk(λk,Xk)表示觀測點Xk對應(yīng)的可見區(qū)域,該區(qū)域中目標(biāo)呈非均勻分布,其中λk是Yk(λk,Xk)的密度因子,該密度因子和物體存在于區(qū)域Yk(λk,Xk)的單位面積的概率呈正相關(guān)關(guān)系,具體如下:

其中: n表示觀測點的數(shù)量,pk為目標(biāo)在觀測點Xk所覆蓋區(qū)域存在的概率.

且

隨著時間推移,目標(biāo)在各個觀測點的分布概率會發(fā)生改變,故需對各觀測點的概率進行更新,采用統(tǒng)計方法來提高測算模型與實際環(huán)境的匹配度.

基于離散搜索理論[5],在一個工作空間S中,機器人搜索目標(biāo)物體屬離散事件,其概率分布如下:

搜索到目標(biāo)物體的期望時間為

其中:tk表示機器人從第k個觀測點到第k+1個觀測點所消耗的時間,例如t1表示從第1個觀測點到第2個觀測點所消耗的時間;pk表示機器人在第k+1個觀測點的概率,假設(shè)累計分布函數(shù)為f(T),則

其中累計分布函數(shù)如圖1所示.

圖1 累計分布函數(shù)Fig.1 The cumulative distribution function

3 基于優(yōu)化改良圈的上層序列規(guī)劃算法

拓撲序列規(guī)劃目的是在特定的搜索環(huán)境下,依據(jù)某種評價標(biāo)準(zhǔn)生成任務(wù)所需的觀測點序列.文獻[11]用貪心算法搜索拓撲地圖,其計算復(fù)雜度較低,可確保找到可行解,但所用啟發(fā)式方法難以得到全局最優(yōu)解.原始的改良圈算法為圖論中的拓撲圖搜索算法,但只能從局部進行優(yōu)化,后來有研究者從全局角度考慮對改良圈算法進行改進,從而得到了一種基于優(yōu)化改良圈的拓撲序列搜索算法.與文獻[11]中的貪心算法相比,該方法具有更強的全局優(yōu)化能力且常被用于圖搜索,但并未用于概率目標(biāo)搜索問題.該算法所面向的圖論問題與機器人多目標(biāo)搜索問題較相似,本文根據(jù)任務(wù)需求對其改進,基于該方法解決非均勻分布目標(biāo)的搜索問題.面向多目標(biāo)搜索問題的改良圈搜索機制如下:若目標(biāo)在S中滿足非均勻分布,則遍歷全部觀測點,并返回起始點,移動機器人所走過的路徑記為L,根據(jù)權(quán)值最小原則反復(fù)修正L,從而得到滿足期望時間最優(yōu)的一條路徑L1,具體步驟如下:

步驟1在工作環(huán)境S中選擇一個觀測點X1作為起點,尋找一條與觀測點X1關(guān)聯(lián),且權(quán)值最小的邊m1,m1另一端的觀測點記為X2,從而得到一個觀測點序列X1,X2.

步驟2觀測點X2作為起點,尋找一條與觀測點X2關(guān)聯(lián),權(quán)值最小的邊m2,m2另一端的觀測點記為X3,從而得到一個觀測點序列X1,X2,X3.同理可得一個觀測點序列,記為X1,X2,X3,···,Xk.

步驟3假設(shè)已選出的路徑觀測點訪問順序是X1,X2,X3,···,Xk,在剩下路徑的觀測點中找到一個與觀測點Xk的權(quán)值最小的觀測點,記為Xk+1.從而得到邊序列:m1,m2,m3,···,mk+1.

步驟4令kk+1,重復(fù)步驟3,直至k+1n ?1,得到路徑L,

步驟5記路徑L為改良圈算法的初始圈,當(dāng)

其中:M(G)表示邊的集合,w(XkXj)表示觀測點Xk,Xj間的權(quán)值,L1表示新的觀測點序列.

步驟6令LL1,返回步驟5,循環(huán)(n ?1)!?1次.

步驟7找出回路最小權(quán)值和對應(yīng)的L1,即為優(yōu)化后的觀測點訪問順序.

4 基于GBC–RRT的下層點對點規(guī)劃

序列規(guī)劃是拓撲圖下生成的觀測點序列,并未考慮局部環(huán)境,需要用下層P–P(point to point)規(guī)劃方法根據(jù)局部環(huán)境生成一條機器人更易于跟蹤的路徑.目標(biāo)搜索問題的局部規(guī)劃問題已有大量相關(guān)研究,如:文獻[5]針對凸多邊形障礙以可視圖法進行規(guī)劃,文獻[10]采用人工勢場法(artifical potential field,APF)執(zhí)行P–P規(guī)劃,該方法的缺陷是易于陷入局部極小.RRT路徑規(guī)劃方法以“樹”的形式在空間擴展,從而生成可行路徑.它以初始點作為根節(jié)點,通過隨機采樣增加葉子節(jié)點的方式,生成隨機擴展樹,當(dāng)隨機樹中的葉子節(jié)點包含了目標(biāo)點或進入了目標(biāo)區(qū)域,便可以在隨機樹中找到一條從初始點到目標(biāo)點的路徑.由于RRT算法的隨機性強,導(dǎo)致路徑的權(quán)值較大,為解決該問題,研究者對RRT方法不斷改進,相繼提出目標(biāo)偏好RRT、雙向RRT等.為克服RRT方法隨機性強導(dǎo)致的目的趨向慢、易陷入局部極小的缺點[12–14],本文引入目標(biāo)偏好和物體碰撞檢測機制,對原始RRT方法加以改進,考慮全局環(huán)境信息,減小擴展的隨機性、避免陷入局部極小值的問題,縮短了算法的運行時間,從而提高整體的尋優(yōu)效率[15].

為克服RRT隨機性強的缺陷,本文借鑒目標(biāo)偏好RRT算法的策略,即設(shè)定一個閾值ρa,隨機觸發(fā)因子大于閾值ρa,便隨機選取地圖上的一個點作為下一節(jié)點的擴展方向,反之,把目標(biāo)區(qū)域點當(dāng)作隨機目標(biāo)點.此時隨機搜索樹從起點開始擴展,以終點為目標(biāo),從而規(guī)劃出一條路徑.

為避免陷入局部極小值,引入物體碰撞檢測機制,碰撞檢測示意圖如圖2所示,把Qinit當(dāng)作初始狀態(tài)的母節(jié)點,其子節(jié)點按圖2中所示逐層向外擴展,用g表示節(jié)點在其子節(jié)點方向上的碰撞概率,節(jié)點擴展方向由g值決定.假設(shè)起始節(jié)點和目標(biāo)節(jié)點間結(jié)點數(shù)為n,每個新節(jié)點的各子方向初始化為未擴展?fàn)顟B(tài),且每個新節(jié)點的g值為0. Qnearest節(jié)點為最臨近節(jié)點,其各子方向初始化為擴展?fàn)顟B(tài),Qnearest節(jié)點的g值將會增加1/n.依次類推,假設(shè)Qinit節(jié)點是Qnearest節(jié)點的第m?1階母節(jié)點,則Qinit節(jié)點的g值相應(yīng)增加1/nm.

圖2 碰撞檢測機制示意圖Fig.2 Schematic diagram of collision detection mechanism

以節(jié)點在其子節(jié)點方向上的碰撞概率來決定路徑的擴展方向,g值越大,表示在該方向上遇到障礙物的可能性越大;反之,在該方向上遇到障礙物的可能性越小.在考慮全局碰撞信息后,優(yōu)先選擇g值較小的方向作為隨機樹的下一步擴展方向.改進的快速隨機生成樹算法(goal biasing collision rapid-exploration random tree,GBC–RRT)算法用圖2所示的碰撞信息檢測函數(shù)優(yōu)先選擇隨機樹的擴展方向,從而代替經(jīng)典RRT算法隨機擴展的方式,提高了路徑尋優(yōu)的效率.基于期望時間下的移動機器人目標(biāo)搜索路徑規(guī)劃算法的偽代碼如下:

上層規(guī)劃是序列規(guī)劃,屬于在拓撲圖中進行圖搜索,旨在根據(jù)最優(yōu)期望時間規(guī)劃生成觀測點訪問序列,上層規(guī)劃給出了概要的路線,但是該路線不適于機器人跟蹤.故下層規(guī)劃采用GBC–RRT算法生成了適合移動機器人跟蹤的局部路徑.期望時間下的移動機器人目標(biāo)搜索路徑規(guī)劃示意圖如圖3所示.

5 實驗結(jié)果與分析

為驗證本文所提搜索策略的有效性,首先在拓撲點規(guī)劃將本文所提算法與貪心算法(greedy algorithm)比較,然后在P–P規(guī)劃方面,將RRT算法和GBC–RRT算法比較,分別將這兩種算法應(yīng)用于“T”形圖、“V”字形、“一”字形、“U”字形的路徑規(guī)劃,本文重點在于運動規(guī)劃問題,故目標(biāo)概率采用人工經(jīng)驗值.因環(huán)境與搜索結(jié)果相關(guān)性高,故采用多種目標(biāo)環(huán)境分步進行測試.

“T”字形對應(yīng)環(huán)境中的客廳障礙物空間,“V”字形對應(yīng)環(huán)境中不規(guī)則可行空間,“一”字形對應(yīng)環(huán)境中難以檢測到入口的狹窄通道,“U”字形對應(yīng)環(huán)境中容易產(chǎn)生局部極小的陷阱問題,將RRT算法和GBC–RRT算法應(yīng)用于“T”字形、“V”字形、“一”字形、“U”字形,仿真結(jié)果如圖4–7所示,兩種環(huán)境下RRT和GBC–RRT對應(yīng)的運行時間、節(jié)點數(shù)和路徑長度見表1.

圖3 期望時間下的移動機器人目標(biāo)搜索路徑規(guī)劃Fig.3 Path planning of target search for mobile robot with expected time

表1 環(huán)境1下特殊情況仿真結(jié)果Table 1 Simulation results under special circumstances in E1

由圖4–7可見,經(jīng)典RRT算法隨機樹擴展區(qū)間更大,復(fù)雜度更高,目標(biāo)偏向性差,導(dǎo)致路徑成本比較高.經(jīng)典RRT算法沒有考慮非完整約束,規(guī)劃出的路徑狀態(tài)轉(zhuǎn)變較快,往往存在角度突變的情況,這對移動機器人來說難以跟蹤.GBC–RRT算法隨機樹探索的區(qū)間小、復(fù)雜度低、目標(biāo)偏向性強,并且GBC–RRT算法在規(guī)劃過程中考慮了非完整約束,規(guī)劃出的可執(zhí)行曲線比較光滑,不存在狀態(tài)突變的情況,機器人可以在該軌跡上直接跟蹤.由表1可見GBC–RRT算法在運行時間、節(jié)點數(shù)、路徑長度方面都比RRT算法占優(yōu).

圖4 T形環(huán)境下測試Fig.4 Test in a T-environment

圖5 V形環(huán)境下測試Fig.5 Test in a V-environment

圖6 “一”形環(huán)境下測試Fig.6 The test in a environment with a narrow gap

圖7 U形環(huán)境下測試Fig.7 Test in a U–environment

觀測點的訪問順序不同會導(dǎo)致期望時間存在一定的差異.以簡單搜索任務(wù)為例說明:假設(shè)搜索任務(wù)的工作環(huán)境如圖8所示,藍色區(qū)域表示不可行空間,其余區(qū)域表示可行空間,X1,X2,X3,X4為觀測點.觀測點的選取原則是盡可能少的點覆蓋整個工作環(huán)境,觀測點的數(shù)量越多對工作環(huán)境覆蓋效果越好,但會增加重疊區(qū)域,不利于優(yōu)化,本文分別采用4個和10個觀測點,按觀測點的選取原則置于工作環(huán)境S內(nèi).任務(wù)要求:機器人從起點開始按照最優(yōu)期望時間遍歷每個觀測點對工作環(huán)境S存在的目標(biāo)進行搜索,最后攜帶所得目標(biāo)返回起點.分別測試貪心–RRT(GA–RRT)算法、貪心–GBC–RRT算法和本文所提算法對搜索目標(biāo)期望時間的優(yōu)化效果.對于復(fù)雜的任務(wù)搜索路徑規(guī)劃,為避免機器人本身對問題分析的影響,采用膨脹處理的方式,不考慮移動機器人的大小和形狀,把移動機器人作為質(zhì)點處理[5].算法中ρa值取0.05,觀測點概率均按照表2中所示的經(jīng)驗值設(shè)置,分別采用貪心–RRT算法、貪心–GBC–RRT算法和本文所提算法對移動機器人進行路徑規(guī)劃,生成的路徑及數(shù)據(jù)如圖9–11,表3所示.由圖9–10可見,根據(jù)貪心算法可得X1–X3–X2–X4–X1節(jié)點順序,在節(jié)點之間分別用RRT,GBC–RRT算法得到了局部路徑,由表3可見,貪心–RRT 算法得到的期望時間為60.54 s,運行時間為22.32 s,貪心–GBC–RRT 算法得到的期望時間是57.78 s,運行時間為16.30 s.由以上結(jié)果可見,GBC–RRT算法在期望時間這一指標(biāo)上并未發(fā)生顯著變化,但是在運行時間方面有較大的提升,顯著改善了算法的實時性,本文所提算法所獲結(jié)果的期望時間為49.59 s,運行時間為14.86 s,在期望時間指標(biāo)上有明顯優(yōu)勢,提高的百分比為18.09%.

圖8 移動機器人路徑規(guī)劃工作空間Fig.8 The workspace for mobile robot path planning

表2 環(huán)境2下目標(biāo)點在觀測區(qū)域的概率分布Table 2 Probability distribution of target points in the observation area of E2

圖10 環(huán)境2下貪心GBC–RRT的多目標(biāo)搜索Fig.10 Multi-target search path generated by GA–GBC–RRT in E2

圖11 環(huán)境2下最優(yōu)期望時間的多目標(biāo)搜索Fig.11 Multi-target search with optimal expected-time approach in E2

表3 環(huán)境2下3種算法指標(biāo)的對比Table 3 Comparison of three algorithms in E2

為進一步驗證改進算法的有效性,將觀測點的數(shù)量增為10個,記為E3,增加3組對比實驗,ρa取0.05,各個觀測點對應(yīng)的概率如表4所示.重復(fù)以上實驗,仿真生成路徑規(guī)劃如圖12–14和表5所示.圖12–13為貪心式算法生成的節(jié)點訪問順序,其結(jié)果為X1–X9–X2–X7–X10–X4–X8–X6–X5–X3–X1,節(jié)點之間分別采用RRT和GBC–RRT進行局部路徑規(guī)劃,圖14是根據(jù)改進改良圈生成的節(jié)點訪問順序,其結(jié)果為X1–X3–X5–X6–X7–X10–X8–X9–X4–X2–X1,節(jié)點之間同樣采用GBC–RRT算法進行路徑規(guī)劃.由表5可見,按照貪心算法生成的節(jié)點順序,即使局部路徑采用GBC–RRT算法,期望時間沒有明顯的提高,但其在運行時間得到了改善.在期望時間這一指標(biāo)上,本文所提算法路徑規(guī)劃的期望時間顯著縮短,提高了約50%.

表4 環(huán)境3下目標(biāo)點在觀測區(qū)域的概率分布Table 4 Probability distribution of target points in the observation area of E3

圖12 環(huán)境3下貪心RRT的多目標(biāo)搜索路徑Fig.12 Multi-target search path generated by GA–RRT in E3

圖13 環(huán)境3下貪心GBC–RRT的多目標(biāo)搜索路徑Fig.13 Multi-target search path generated by GA–GBC–RRT in E3

隨時間推移,目標(biāo)在觀測點的概率會發(fā)生變化,由式(7)得到表6所示對應(yīng)概率.采用本文所提算法得到路徑規(guī)劃如圖15所示.由圖15可見,當(dāng)概率發(fā)生變化時,觀測點訪問序列會發(fā)生變化,進而導(dǎo)致整體路徑規(guī)劃結(jié)果的變化,例如:在環(huán)境3下的節(jié)點訪問序列為X1–X2–X3–X4–X5–X6–X7–X8–X10–X9–X1,當(dāng)該環(huán)境的目標(biāo)概率發(fā)生更新后,節(jié)點序列隨之發(fā)生變化,整體路徑的期望時間也由26.08 s變?yōu)?9.64 s.

圖14 環(huán)境3下最優(yōu)期望時間的多目標(biāo)搜索路徑Fig.14 Multi-target search with optimal expected-time approach in E3

表5 環(huán)境3下3種算法指標(biāo)的對比Table 5 Comparison of three algorithms in E3

表6 環(huán)境3下更新后目標(biāo)點在觀測區(qū)域的概率分布Table 6 Updated probability distribution of target points in the observation area of E3

圖15 環(huán)境3下概率更新后的多目標(biāo)搜索路徑Fig.15 Multi-target search path with updated probability in E3

重復(fù)進行50次實驗,得到如圖16–17所示多次實驗與期望時間、運行時間曲線圖.根據(jù)統(tǒng)計學(xué)的方法,計算期望時間的平均值為26.80 s,運行時間的平均值為17.29 s,期望時間的標(biāo)準(zhǔn)差是1.07,運行時間的標(biāo)準(zhǔn)差為1.27.根據(jù)期望時間、運行時間的平均值能說明50次實驗結(jié)果下期望時間大小主要集中在26.80 s、運行時間主要集中在17.29 s.期望時間、運行時間的標(biāo)準(zhǔn)差越小說明數(shù)據(jù)的離散程度較小,改進算法的穩(wěn)定性較高,數(shù)據(jù)有較小范圍的波動,存在一定的波動源于RRT算法本身節(jié)點生成過程的隨機性.

圖16 環(huán)境3下50次實驗的期望時間Fig.16 Expected-time of 50 tests in E3

圖17 環(huán)境3下50次實驗的算法運行時間Fig.17 Run time of 50 tests algorithm in E3

為了測試目標(biāo)偏好參數(shù)ρa對模型的影響,在復(fù)雜環(huán)境下分別將ρa調(diào)小至0.005和將ρa調(diào)大至0.5,觀測點概率保持不變,重復(fù)進行實驗,仿真結(jié)果如圖18–19所示.由圖18–19可見,當(dāng)ρa越小,隨機樹擴展的隨機性越強,目標(biāo)的偏好性越低,會出現(xiàn)冗余的搜索,降低了多目標(biāo)搜索的效率,反之,隨機樹擴展的隨機性越弱,目標(biāo)的偏好性越高,出現(xiàn)冗余的搜索較小,提高了搜索效率.ρa參數(shù)的改變,生成的路徑變化幅度小,驗證了目標(biāo)偏好值的大小對目標(biāo)搜索時上層路徑規(guī)劃的影響不大.

為了得到更多ρa值下路徑規(guī)劃的期望時間,以步長為0.03在[0.01,0.58]區(qū)間內(nèi)依次取值,得到圖20所示的期望時間曲線圖.綜上所述,目標(biāo)參數(shù)的改變影響了觀測點間的局部路徑規(guī)劃,當(dāng)目標(biāo)偏好參數(shù)越大,隨機樹擴展的隨機性越低,目標(biāo)的偏好性越高,運行時間變化顯著,但是當(dāng)目標(biāo)偏好參數(shù)選擇足夠大時,仿真實驗時規(guī)劃算法容易陷入局部極小值;當(dāng)目標(biāo)偏好參數(shù)越小,雖能避免局部極小值問題,但是隨機性強,目標(biāo)的偏好性較差,需要更多的時間來搜索節(jié)點,直接表現(xiàn)為仿真運行時間會更長.因此,需要根據(jù)環(huán)境的復(fù)雜性,進行偏好參數(shù)調(diào)節(jié).目標(biāo)偏好參數(shù)變化屬于下層局部規(guī)劃部分,只影響下層規(guī)劃,對上層規(guī)劃的序列沒有影響.

圖18 環(huán)境3下ρa=0.005的路徑規(guī)劃Fig.18 Path planning in E3 with ρa=0.005

圖19 環(huán)境3下ρa=0.5的路徑規(guī)劃Fig.19 Path planning in E3 with ρa=0.5

圖20 不同ρa值下期望時間曲線Fig.20 Expected-time curve for ρa

6 結(jié)論

為了解決不確定環(huán)境下多目標(biāo)搜索效率低的問題,本文提出了一種基于最優(yōu)期望時間的目標(biāo)搜索路徑規(guī)劃方法.通過引入一種新的觀測點,構(gòu)建非均勻分布概率測算模型,在上層序列規(guī)劃采用改進的改良圈算法優(yōu)化觀測點序列,比常用的貪心算法具有更強的全局優(yōu)化能力;下層采用GBC–RRT算法進行節(jié)點間路徑規(guī)劃,相比于經(jīng)典RRT算法具有更好的目標(biāo)趨向性.實驗結(jié)果表明,該方法可以顯著縮短移動機器人獲取目標(biāo)的期望時間,適用于以期望時間為指標(biāo)的單機器人多目標(biāo)搜索取回任務(wù),在部分其它任務(wù)模式下雖可生成可行路徑,但優(yōu)化效率會有所降低.