移動(dòng)機(jī)器人的路徑規(guī)劃實(shí)例分析

覆蓋路徑空間：關(guān)于移動(dòng)機(jī)器人路徑規(guī)劃的實(shí)例分析摘要本文介紹了移動(dòng)機(jī)器人在動(dòng)態(tài)環(huán)境下路徑規(guī)劃的一個(gè)實(shí)例的理論分析。不像其他基于案例的路徑規(guī)劃方法，我們用柵格地圖表示允許機(jī)器人在非結(jié)構(gòu)環(huán)境下運(yùn)行的環(huán)境。移動(dòng)機(jī)器人的目標(biāo)是選擇跟蹤低危險(xiǎn)度的路徑。本次實(shí)驗(yàn)以真正的機(jī)器人表現(xiàn)了我們想法的有效性。在本文，我們替換了種子實(shí)例庫(kù)中移動(dòng)機(jī)器人的搜索式路徑規(guī)劃算法并證實(shí)了實(shí)例庫(kù)中基數(shù)的上下極限。證據(jù)表明用一些解決路徑搜索問題的方案來(lái)發(fā)展實(shí)例庫(kù)是實(shí)際可行的，結(jié)果是不可能存在與實(shí)例庫(kù)中的路徑區(qū)別較大的方案。這保證了在理論上機(jī)器人將會(huì)搜索從起點(diǎn)到終點(diǎn)的所有路徑。實(shí)例庫(kù)中基數(shù)集上限表明，在長(zhǎng)遠(yuǎn)看來(lái)，實(shí)例庫(kù)將不斷擴(kuò)大，不可能保存所有解決方案。為了保持最有效的解決方案，實(shí)例庫(kù)在運(yùn)行中必須加以改進(jìn)，或必須考慮一些其他方法的路徑差異。Q2003ElsevierScienceB.V.保留所有權(quán)關(guān)鍵詞：基于實(shí)例的推理；路徑規(guī)劃；覆蓋度量空間1?簡(jiǎn)介本文介紹的工作是移動(dòng)機(jī)器人研究方面的理論延伸，我們調(diào)查了包括移動(dòng)機(jī)器人在解空間內(nèi)生成一個(gè)種子實(shí)例庫(kù)的問題。在我們先前的工作中，基于案例推理(CBR)的方式，我們已經(jīng)在實(shí)際的機(jī)器人上實(shí)現(xiàn)了移動(dòng)機(jī)器人路徑規(guī)劃和測(cè)試。在這項(xiàng)工作中，我們證明了理論上限和下限對(duì)于實(shí)例基數(shù)的可行性和我們的方法的局限性。本文的其余部分組織如下：在第1節(jié)我們著眼于機(jī)器人的導(dǎo)航領(lǐng)域介紹并解釋這個(gè)問題的重要性。第2節(jié)介紹了系統(tǒng)以前的實(shí)驗(yàn)做法和對(duì)實(shí)驗(yàn)結(jié)果的評(píng)語(yǔ)。在第3節(jié)，我們給出了基本的定義并且陳述了主要空間的機(jī)器人路徑，上述內(nèi)容也覆蓋了第4節(jié)的問題。第5、6節(jié)(精確)證明理論下限和上限，分別對(duì)覆蓋問題加以說明。第7節(jié)在當(dāng)前的介紹上將舊啟發(fā)式算法與新的進(jìn)行比較。第8節(jié)得出了一些結(jié)論，并討論了今后的工作。行動(dòng)方式我們的工作是基于一個(gè)事實(shí)，大部分的移動(dòng)機(jī)器人的應(yīng)用意味著在環(huán)境變化時(shí)重復(fù)遍歷于預(yù)定義的起點(diǎn)和目標(biāo)點(diǎn)之間。例如，一個(gè)移動(dòng)機(jī)器人可用于在商店和生產(chǎn)線之間傳送細(xì)節(jié)并分部裝配。這項(xiàng)任務(wù)暗示了在商店和最小單元生產(chǎn)組之間的的重復(fù)遍歷。這項(xiàng)任務(wù)也暗示著以一個(gè)預(yù)定義的順序在一個(gè)封閉的區(qū)域上訪問某些關(guān)卡。操作這些移動(dòng)機(jī)器人的真實(shí)環(huán)境本質(zhì)上是動(dòng)態(tài)的，從移動(dòng)機(jī)器人的導(dǎo)航視圖中看，這意味著意外障礙也會(huì)出現(xiàn)和消失。這些障礙的性質(zhì)和密度通常是未知的或很難模擬。與此同時(shí)在動(dòng)態(tài)環(huán)境中的移動(dòng)機(jī)器人必須盡可能快速安全地完成分配。這意味著在目標(biāo)點(diǎn)之間選擇路徑是最暢通的，并且在這些路徑中的機(jī)器人在障礙之間并不會(huì)花費(fèi)很多時(shí)間。迄今為止，很少有研究報(bào)告報(bào)道路徑選擇方面的問題。不像這些方法，我們并未假定環(huán)境結(jié)構(gòu)是已知的，因此，我們的方法也適用于環(huán)境是未知的并且環(huán)境會(huì)改變的案件。系統(tǒng)描述移動(dòng)機(jī)器人路徑選擇的方法包括整個(gè)世界模型以及存儲(chǔ)路徑運(yùn)行的經(jīng)驗(yàn)以備后用的記憶模式。內(nèi)存是一個(gè)實(shí)例庫(kù)用于存儲(chǔ)以前運(yùn)行過的路徑。世界模型是指一個(gè)允許路徑規(guī)劃的地圖，由于在動(dòng)態(tài)環(huán)境中，機(jī)器人不能模擬其周圍環(huán)境的所有方面，所以地圖總是或多或少不精確。圖1抓住了這種方法的底線,。該全局規(guī)劃師接收來(lái)自用戶的任務(wù)，這些任務(wù)是需要從機(jī)器人的現(xiàn)狀位置移動(dòng)到一個(gè)特定的點(diǎn)。全局規(guī)劃師有一個(gè)環(huán)境地圖，這個(gè)地圖僅僅呈現(xiàn)出目標(biāo)點(diǎn)的環(huán)境和位置的幾何方面。在環(huán)境中，動(dòng)態(tài)障礙的存在和位置是未知的。給定了新的任務(wù)，全局規(guī)劃師要么可以基于地圖的路徑規(guī)劃找到一個(gè)新的解決方案，要么重新使用一個(gè)從早期的實(shí)例庫(kù)中發(fā)現(xiàn)的路徑。由全局規(guī)劃師規(guī)劃的路徑被提交到低一級(jí)的規(guī)劃和執(zhí)行單位，該單位負(fù)責(zé)任務(wù)分解（如有必要），重新規(guī)劃，定位，傳感器的數(shù)據(jù)處理和執(zhí)行器的控制。全局規(guī)劃師的目標(biāo)是根據(jù)一些標(biāo)準(zhǔn)選擇最好的運(yùn)行路徑（如時(shí)間，距離，安全性）。CBR允許該機(jī)器人記住和學(xué)習(xí)其過去的經(jīng)驗(yàn)。該機(jī)器人將適應(yīng)動(dòng)態(tài)環(huán)境的變化，學(xué)會(huì)更好的使用路徑。圖1路徑規(guī)劃概覽基于實(shí)例的推理改變先前對(duì)類似問題的成功解決方案，基于案例推理（CBR）解決了新的問題。過去的經(jīng)驗(yàn)，通過應(yīng)用數(shù)據(jù)庫(kù)技術(shù)管理，都存儲(chǔ)在一個(gè)實(shí)例庫(kù)。為了便于案例檢索，在實(shí)例庫(kù)案件中應(yīng)加索引。當(dāng)一個(gè)新的問題出現(xiàn)時(shí)，從特性中提取索引，用于查找匹配的實(shí)例庫(kù)案件。如果不止一個(gè)匹配案例被發(fā)現(xiàn)，那么候選案件是非常有價(jià)值的，用以找到最合適的一個(gè)。除非檢索到的情況是一場(chǎng)勢(shì)均力敵的比賽，該解決方案可能必須在使用前加以修改以便解決問題。如果修改后的情況下發(fā)現(xiàn)是成功的，它會(huì)產(chǎn)生一種新的情形，即存儲(chǔ)在實(shí)例庫(kù)中。因此在CBR中，學(xué)習(xí)是通過新案例的積累來(lái)完成的。在本文描述的方法中，問題是從一個(gè)給定的出發(fā)點(diǎn)到一個(gè)給定的目標(biāo)點(diǎn)之間找到最佳路徑。該解決方案的結(jié)果是反映路徑的成本，反映了運(yùn)行此路徑是多么容易。如果機(jī)器人反復(fù)遍歷一條路徑，每次遍歷后路徑的成本都將更新。這筆費(fèi)用將反映這條道路的平均特點(diǎn)。通過選擇具有最小代價(jià)的路徑，機(jī)器人可以降低碰撞風(fēng)險(xiǎn)，以及減少運(yùn)行距離。路徑規(guī)劃的CBR方式在文獻(xiàn)［4-7］描述。這些方法用于規(guī)劃靜態(tài)環(huán)境。PRODIGY/ANALOGY將CBR應(yīng)用于美國(guó)匹茲堡［8］市動(dòng)態(tài)路徑規(guī)劃。這些方法使用一個(gè)基于圖形的地圖來(lái)進(jìn)行路徑規(guī)劃，該地圖的缺點(diǎn)是它假設(shè)環(huán)境的剛性結(jié)構(gòu)為不同的捕獲地方（節(jié)點(diǎn)）和連接路徑（邊）。如果結(jié)構(gòu)環(huán)境發(fā)生改變，整個(gè)圖形要改組，以更新地圖。在許多情況下，它是可行的，推定環(huán)境結(jié)構(gòu)是穩(wěn)定的。例如，在PRODIGY/ANALOGY的情況下，很明顯該匹茲堡結(jié)構(gòu)（即街道和口岸）不隨時(shí)間明顯變化。另一方面，也有許多移動(dòng)機(jī)器人的應(yīng)用領(lǐng)域，那里的環(huán)境可以根據(jù)機(jī)器人的任務(wù)（例如建筑或救助網(wǎng)站）巧妙地改變。為了能夠使用高動(dòng)態(tài)機(jī)器人環(huán)境，我們使用一個(gè)基于網(wǎng)格的地圖，而不是一個(gè)拓?fù)湫缘貓D?；诰W(wǎng)格的地圖針對(duì)單一路徑規(guī)劃問題也提供更多的解決方法，并提供更詳細(xì)的路徑規(guī)劃。由于可以有多個(gè)路徑之間的替代給定的目標(biāo)點(diǎn)，所以實(shí)例庫(kù)中的每個(gè)問題可以有多個(gè)解決方案。要從實(shí)例庫(kù)中查找類似問題，我們用最近鄰檢索，即機(jī)器人將查找該案例開始和目標(biāo)點(diǎn)盡可能接近當(dāng)前的問題。但是，為了分析我們的實(shí)例庫(kù)，我們假設(shè)它僅有一個(gè)問題組成，該問題有許多解決方法。這個(gè)問題將有盡可能多的解決方案，即在斜對(duì)面的角落之間通過的問題。將我們的問題正規(guī)化，所有其他路徑規(guī)劃問題都是這一最普遍問題的子問題。我們的目標(biāo)是根據(jù)一些相似的問題的解決措施，將現(xiàn)有問題的所有不同解決方案來(lái)生成實(shí)例庫(kù)。路徑規(guī)劃在移動(dòng)機(jī)器人學(xué)的背景中，路徑規(guī)劃方法是指尋找從開始到目標(biāo)的無(wú)碰撞路徑。該路徑規(guī)劃的方法取決于機(jī)器人世界模型。（文獻(xiàn)［9］為智能機(jī)器人技術(shù)的概述和路徑規(guī)劃技術(shù)）在這項(xiàng)工作中，我們選用一種常見的移動(dòng)機(jī)器人世界模型——柵格地圖。柵格地圖用一個(gè)個(gè)小的單元格來(lái)描述世界。那些已知的，包括靜態(tài)障礙物的單元格可被標(biāo)記為已占領(lǐng)。在我們先前的工作中，我們已經(jīng)研制了一個(gè)搜索式算法的修改版，由于地圖上隨機(jī)擾動(dòng)的生成，它對(duì)一個(gè)簡(jiǎn)單的路徑規(guī)劃問題會(huì)產(chǎn)生許多可選擇的解決方案。圖2表示一個(gè)網(wǎng)格地圖。地圖上的黑色區(qū)域代表靜態(tài)障礙，搜索式算法生成了從起點(diǎn)到目標(biāo)點(diǎn)的路徑。有兩個(gè)問題與路徑生成方式相關(guān)：首先，在理論上，他不可能保證找到從給定起點(diǎn)到給定目標(biāo)點(diǎn)的所有可能路徑。第二，即使在一個(gè)相對(duì)小網(wǎng)格，在指定的目標(biāo)點(diǎn)之間不同的路徑數(shù)量是十分巨大的；與此同時(shí)，區(qū)別較大的路徑數(shù)目較少。為了克服這一問題，我們定義了一個(gè)相似度（詳見第3部分）。有了相似度，我們可將區(qū)別較小的路徑視為相同。機(jī)器人運(yùn)行的路徑貯存在實(shí)例庫(kù)中，在此，我們利用相似度的特點(diǎn)，只貯存彼此間區(qū)別較大的路徑。這樣大大減少了實(shí)例庫(kù)的規(guī)模。圖2柵格地圖在我們的實(shí)驗(yàn)中，我們建立一個(gè)空的實(shí)例庫(kù)，若一個(gè)必要的解決方案沒在實(shí)例庫(kù)中或它的特性不是很好，則會(huì)產(chǎn)生基于地圖的路徑規(guī)劃的新的解決方案。我們可以在環(huán)境或用真正的機(jī)器人來(lái)深入檢驗(yàn)我們的算法。測(cè)試表明，機(jī)器人能快速適應(yīng)環(huán)境的變化并學(xué)會(huì)使用風(fēng)險(xiǎn)較小的路徑。所有的測(cè)試表明，即使環(huán)境很大，實(shí)例庫(kù)規(guī)模實(shí)際上是很小的。然而，測(cè)試也指出了我們算法的缺點(diǎn)。我們的路徑規(guī)劃算法可更改地圖來(lái)生成新的隨機(jī)解決方案。在測(cè)試中，很明顯可以觀察到，由算法生成的許多路徑是十分相似的。機(jī)器人花費(fèi)很多時(shí)間來(lái)等待尋找不同的解決方案。有時(shí)機(jī)器人也會(huì)困在局部區(qū)域——一些本來(lái)十分容易運(yùn)行的路徑是永遠(yuǎn)也不會(huì)生成的。2?3實(shí)例庫(kù)的生成為了克服我們目前裝備的缺點(diǎn)，我們實(shí)施了針對(duì)當(dāng)前問題所有解決方案來(lái)生成實(shí)例庫(kù)，從理論上講，從一個(gè)給定起點(diǎn)到給定終點(diǎn)的可能路徑數(shù)是十分龐大的。這些路徑中許多僅有小部分差別，從軌跡跟蹤角度講，大部分路徑是不可行的（如不可行的彎曲或過長(zhǎng)），因此，我們必須限制其在實(shí)例中使用的路徑設(shè)置。為確保我們的限制，我們必須解釋一些機(jī)器人軌跡跟蹤的細(xì)節(jié)。在現(xiàn)實(shí)生活中機(jī)器人永遠(yuǎn)無(wú)法精確按照已設(shè)計(jì)好的路徑進(jìn)行跟蹤。由于位置誤差，傳感器噪音以及機(jī)械間不精確連接，機(jī)器人常常會(huì)偏離它的軌跡。在動(dòng)態(tài)環(huán)境中，機(jī)器人也必須在意想不到的障礙周圍行進(jìn)。后者很大程度上會(huì)使得機(jī)器人偏離原來(lái)軌跡。因此，我們的相似度是基于路徑的偏差，我們認(rèn)為那些偏離彼此較大的路是不同的。相反，我們認(rèn)為那些通過環(huán)境地圖大致相同區(qū)域的路徑是相似的。我們的相似度是第3節(jié)中定義。移動(dòng)機(jī)器人使用避障軌跡和運(yùn)行時(shí)間重規(guī)劃來(lái)解決動(dòng)態(tài)障礙。在我們的真正的機(jī)器人實(shí)驗(yàn)中，我們觀察到規(guī)劃路徑與最終跟蹤路徑差別很大，因?yàn)閲@著障礙進(jìn)而重新規(guī)劃和定位誤差有時(shí)會(huì)使得機(jī)器人沿著另一個(gè)方向行進(jìn)而不是最先的規(guī)劃方向。因此，我們發(fā)現(xiàn)最實(shí)際的道路通行方式就是規(guī)劃路徑與實(shí)際跟蹤路徑之間相似路徑。能使的機(jī)器人跟蹤的越好，那么這個(gè)路徑就越好。我們可以用來(lái)評(píng)估估計(jì)的第二種方式是路徑跟蹤時(shí)間。這種方法也十分實(shí)用，因?yàn)橐苿?dòng)機(jī)器人通常能預(yù)期盡可能快的完成任務(wù)。因此生成實(shí)例路徑既短又直看起來(lái)是可行的。這些路徑是最可能滿足我們良好通行標(biāo)準(zhǔn)的。短路徑是最有可能導(dǎo)致機(jī)器人更快到達(dá)目標(biāo)。過于彎曲的路徑在技術(shù)上也很難跟蹤(而且機(jī)器人到達(dá)目標(biāo)花費(fèi)的時(shí)間更長(zhǎng))。因此我們限制我們對(duì)路徑的設(shè)置為能直接更快到達(dá)的移動(dòng)。它將排除所有不必要的又長(zhǎng)又復(fù)雜的路徑(實(shí)際指所有有回環(huán)的路徑)。這種約束的缺點(diǎn)在于該機(jī)器人在迷宮一樣的環(huán)境中不能有效運(yùn)作。然而，多數(shù)實(shí)際環(huán)境并不是迷宮一樣的。另一個(gè)缺點(diǎn)是指迂回式彎曲路徑，這個(gè)缺點(diǎn)不是那么嚴(yán)重，因?yàn)槲覀冎徽J(rèn)可短而直的路徑。這是典型的基于網(wǎng)格的方法和路徑規(guī)劃，通常移動(dòng)機(jī)器人運(yùn)用路徑松弛技巧在運(yùn)行時(shí)平滑通過路徑。本片文章其余部分我們主要討論實(shí)例管理的問題。第一個(gè)問題是是否能夠用相對(duì)較少的不同實(shí)例來(lái)生成實(shí)例庫(kù)以便涵蓋整個(gè)解空間。這個(gè)問題的答案是肯定的。第二個(gè)問題是系統(tǒng)是否可以在無(wú)人管理實(shí)例庫(kù)的情況下正常運(yùn)行。例如，僅在實(shí)例庫(kù)中路徑不太相似的條件下，機(jī)器人可隨機(jī)生成可能的路徑。這個(gè)問題的答案是否定的。不同解決方案的最大數(shù)量將增加很多，實(shí)例庫(kù)過大，機(jī)器人管理實(shí)例庫(kù)的能力減緩。因此，必須舍棄那些不太有用的解決方案。在下一章，我們將我們會(huì)描述問題，定義一個(gè)相似度并證明實(shí)例庫(kù)中基數(shù)的下限和上限?；径x設(shè)[a,b],a<beZ表示集合｛a,a+1,…,b｝。我們認(rèn)為機(jī)器人在一個(gè)【0,m]x[o,n]的長(zhǎng)方形網(wǎng)格中做正確和短距移動(dòng)。機(jī)器人從原點(diǎn)[0,0]出發(fā)(以網(wǎng)格的左下角為原點(diǎn))到達(dá)終點(diǎn)[m,n]。定義1:在【0,m]x[0n]的網(wǎng)格中，一條路徑由一系列的網(wǎng)格點(diǎn)構(gòu)成。((x,y),(x,y)xy))。比如，(1)x二y二0,x二m,y二n;對(duì)于每一個(gè)0011m+nmn00m+nm+nie[0,m+n-1],在網(wǎng)格中滿足條件(x=x且y+1=y)(x+1=x且y=y)的ii+1ii+1ii+1ii+i所有路徑集合記為P。m,n接下來(lái)，我們定義一個(gè)路徑間的相似度的概念。直觀地講，我們認(rèn)為機(jī)器人選擇的路徑分離幅度不是很大，我們就認(rèn)為這兩條路徑相似。為了描述這個(gè)想法，首先我們需要定義一個(gè)大致距離度量。每一種定義都有幾種可能性，在本文中我們選擇其中之一。

定義2:我們定義點(diǎn)ce[o,m]x[o,n]和路徑PeP間的網(wǎng)格距離為12m,nd(c,P)=min{d(c,c)}，定義d(c,c)為點(diǎn)C1和點(diǎn)C2間的距離。即g12c定義2:我們定義點(diǎn)ce[o,m]x[o,n]和路徑PeP間的網(wǎng)格距離為12m,nd(c,P)=min{d(c,c)}，定義d(c,c)為點(diǎn)C1和點(diǎn)C2間的距離。即g12c2eP2121212離。(見文獻(xiàn)10).對(duì)于任何內(nèi)部指標(biāo)d來(lái)說，Hausdorff距離并非是實(shí)際距離。因?yàn)樗芸赡懿皇菍?duì)稱的；只有當(dāng)d指的是歐式距離時(shí)，這樣的情況才可能會(huì)發(fā)生。為了解決這一問題，可以采取一些措施，最常見的一種方法就是用max{d(pl,p2),d(p2,pl)}[見文獻(xiàn)10]或d(pl,p2)+d(p2,pl)來(lái)代替向性距離。gggg[見文獻(xiàn)11]然而，在本文中，由于我們非常特殊的選擇相應(yīng)的設(shè)置和內(nèi)部指標(biāo)，向性豪斯多夫距離十分接近實(shí)際距離。引理1:(p,d)是一個(gè)度量空間。m,ng證據(jù)：首先，我們注意到d(pl,p2)始終是一個(gè)非負(fù)整數(shù)。度量空間的恒等式g和三角不等式的公理是很容易證明的(實(shí)際上，它們支持每一個(gè)向性Hausdorff距離)。為了證明對(duì)稱性，我們首先證明以下每?jī)蓷l路徑Pl，P2是對(duì)稱的。P,PeP:VcleP3c2eP「d(c1,P)=d(c2,P)]。(1)l2m,nl2g2gl取一點(diǎn)cleP，首先設(shè)若cleP，則得d(cl,P)=0且我們可令c2=c1來(lái)滿足方2g2程(1)?若cleP，則假設(shè)w.l.o.g是P2的運(yùn)行路徑在點(diǎn)cl上方。在度量空間2([o,m]x[o,n],d)中取圭寸閉圓形B，以c1點(diǎn)為圓心，d(cl,P)為半徑，d的含義正是g2指定義2中的距離。(標(biāo)注：這個(gè)圓實(shí)際看起來(lái)是指以c1為圓心，以2d(cl,P)為邊g2緣長(zhǎng)度所構(gòu)成的面積。)從定義2中可以看出，圓B內(nèi)部中不包含路徑P2上任一點(diǎn)，但圓B邊緣可能包含P2上的點(diǎn)。尤其是，B的左上角上的點(diǎn)必須始終屬于P2的，現(xiàn)將此點(diǎn)作為c2點(diǎn)，則P1上任何點(diǎn)都不可能比cl點(diǎn)離c2點(diǎn)更近，則d(cl,P)=d(c2,P)，g2gl方程(1)得證。

現(xiàn)設(shè)c1eP作為令d(c1,P)=max{d(cl,P)}成立的點(diǎn)。通過方程(1)我們可TOC\o"1-5"\h\z1g2cleplg2選取一點(diǎn)c2eP使得d(C1,P)=d(c2,P)，貝U2g2gld(P,P)=d(c1,P)=d(c2,P)<max{(c2,P)}=d(P,P).gl2g2glc2eP2glg2l同理可證，d(P,P)<d(P,P)，故得d(P,P)=d(P,P)。g21g12g21g12根據(jù)引理1，定義3僅僅是度量空間中封閉圓形標(biāo)準(zhǔn)定義的應(yīng)用。定義3：在度量空間(P,d)中，設(shè)一個(gè)以p點(diǎn)為圓心，以5為半徑的圓。令m,ng，則我們得到以下標(biāo)準(zhǔn)結(jié)果。Pm,nB(P,5)={reP:d(P,Pr)<5)，兀(m,n，則我們得到以下標(biāo)準(zhǔn)結(jié)果。Pm,nm,ng引理2.兀引理2.兀(m,n)=<m丿證明.每一路徑包含m+n步，其中m步向右移動(dòng)。問題表述在度量空間(P,d)中，我們主要著眼于覆蓋問題。m,ng問題。對(duì)于一個(gè)給定整數(shù)5和尺寸為m,n的網(wǎng)格，尋找基數(shù)子集S匸P一個(gè)上m,nTOC\o"1-5"\h\z限和下限的估計(jì)使之滿足下列性質(zhì)：UB(P,5)=P(2)m,nPeSVPreSP@UB(P,5)(3)-PeS\{P，}-下限估計(jì)與有效覆蓋問題相關(guān)，在這一背景下，為了獲取偏差不超過極限5的所有可能路徑，我們問在實(shí)例庫(kù)中要求預(yù)先計(jì)劃的路徑的最少數(shù)目是多少。與此相反，上限估計(jì)是處理最糟糕情況的。在這種情況下，我們考慮一個(gè)隨機(jī)路徑的產(chǎn)生過程并思考如果我們每次只包含那些與先前記錄的所有路徑偏離最多不超過5得新路徑，那那我們可設(shè)置的最大路徑是多少。

下限定理1：對(duì)任意8gN且任意子集S匸P滿足性質(zhì)（2）和（3），則不等式（4）成m,n立。s叫君s叫君j，[詮D4）甚至，存在一個(gè)集合S滿足（2）和（3）的性質(zhì)以及不等式（4）。證明：首先我們考慮一種特殊情況，定義m,n：28+1，和子集T匸P滿足下列條件:m,nT=?（x,y（x,y））gP:Vg[o,m+n]x:28+1vy:28+1｝。我們注00m+nm+nm,niii意到P主PgT時(shí)不等式d（P,P）＞28+1成立。因此，集合T中任兩個(gè)元素都不可12g12能被包含在半徑為8的同一個(gè)圓內(nèi)。所以，當(dāng)覆蓋以集合S（滿足條件（2））中元素為圓心，8為半徑的圓構(gòu)成的空間P時(shí)，至少有與集合T中元素?cái)?shù)量相同的圓。m,n但T的路徑實(shí)際上是網(wǎng)格尺寸為+1X少28+]的網(wǎng)格上的路徑（網(wǎng)格面積（28+1）x（28+1））,因此，T=兀mn(28+128+1丿，在此情況下，定理中的不等式成立。為了證明在m:28+1vd28+1這種情況下的不等式，我們簡(jiǎn)單認(rèn)為考慮一個(gè)尺寸為（28+1）mx（28+1）/的次網(wǎng)格是可能的，并且以與定義集合T的情況_28+1」28+1_相似的方式定義一組（局部的）路徑。上述提供的論證也可以很容易適用于這種情況。以等式成立為條件的集合S的存在也可先在m,n：28+1的情況下證明。我們可以證明S=T，T是上面定義的集合。它有正確的基數(shù)，條件（3）成立是顯而易見的。它還需證明條件（2）也成立。為了證明這一結(jié)論，我們必須表明，集合P中每一m,n條可能路徑都屬于圓B（P：8）中某些路徑，其中P'gT。令PgP可能是網(wǎng)格中任m,n意路徑。我們將網(wǎng)格劃分為（28+1）x（28+1）的區(qū)域并建立一條新路徑P以便于：（1）它沿大區(qū)域邊緣行進(jìn)（則P'gT）；

(2)對(duì)于P路徑上的每一點(diǎn)cl,則在P'路徑上存在一點(diǎn)c2使得d(cl,c2)<5(則d(P,Pf)<5)。g我們將沿大區(qū)域跟蹤路徑P并表示出路徑P0在每種情況下必須大區(qū)域的邊緣和頂點(diǎn)：我們?cè)诖髤^(qū)域按照路徑P起始點(diǎn)的位置分情況,有四種可能的區(qū)域作為起點(diǎn)和終點(diǎn)，每一區(qū)域包含長(zhǎng)度為5的兩部分，它們位于大區(qū)域的四個(gè)角落。共有8種可能情況，路徑P'相關(guān)部分所有可能情況見圖3.T11J?":.■r?-:-J_:匸■■■■■■■■■■■■n-L?-rT11J?":.■r?-:-J_:匸■■■■■■■■■■■■n-L?-r?-「-:?-r-L:_r.Fll圖3路徑P'的建立「--?「■-?「I「」FQJrp匡在m:25+1vd25+1的情況下推廣這種存在性證明是很簡(jiǎn)單的。正如上面所做,我們選擇一個(gè)規(guī)模為(2我們選擇一個(gè)規(guī)模為(25+1)mx(25+1)n25+125+1的次網(wǎng)格，但我們必須更謹(jǐn)慎。也就是說，次網(wǎng)格必須定位以便次網(wǎng)格的邊緣間沒有距離而且為了包含網(wǎng)格中所有路徑，整個(gè)網(wǎng)格的相關(guān)邊緣不能大于5。由于m和n除以25+1的最大余數(shù)是25，這樣的定位可以很容易做到。它仍填補(bǔ)了網(wǎng)格中由集合T給定的路徑，網(wǎng)格中的子

路徑加入了整個(gè)網(wǎng)格的左上角和左下角。右上角和右下角也是類似的。上限定理2：對(duì)任意5GN且任意子集S匸P滿足性質(zhì)（2）和（3）,則不等式m,nn,5n,5丿成立。若5是奇數(shù)，選上面式子；若5為偶數(shù)，選下面的式mn(_5+1_,_5+1_丿J_5+1-子。而且，存在一個(gè)集合S滿足性質(zhì)（2）（3）和等式|S|二兀證明：這個(gè)定理的證明與定理1的證明十分相似。首先我們考慮當(dāng)5為偶數(shù)且m,n：5+1時(shí)的情況。我們定義集合T如下：T=?（x,y（x,y））gP:Vg[o,m+n]x：5+1vy：5+1｝。假設(shè)我們還有一■00m+nm+nm,niii集合S符合性質(zhì)（2）和（3）。類似與定理1的證明，可以表示對(duì)每一條PGS的路徑,存在一條PgS的路徑滿足d（P,Pr）＜-。若對(duì)兩條不同路徑P,PgS，相應(yīng)的g21255P'gT路徑相同，則有d（P,P）＜d（P,Pr）+d（P：P）＜_+_=5，與性質(zhì)（3）矛g12g1g222盾。因此，集合S不可能比集合T含有更多的元素。正如定理1，我們有T|=兀[斗，二]，在這種情況下，定理中的不等式成立。（5+15+1丿為了在m：5+1vn：5+1的條件下也推廣結(jié)果，我們?cè)俅慰紤]一個(gè)規(guī)模為（5+1）|y+Jx（5+1）|j+J的次網(wǎng)格位于mXn的網(wǎng)格中心。我們也注意到令S=T提供了符合要求的集合來(lái)實(shí)現(xiàn)該定理的不等式。當(dāng)5為奇數(shù)時(shí)的證明是完全類似的。唯一不同的地方是在這種情況下，我們不

能要求任何路徑P在集合T中存在一條距離遠(yuǎn)大于5/2路徑,但我們必須用5-12來(lái)代替。

7.算法比較與以前的探索式算法相比，為了說明現(xiàn)有算法的優(yōu)越性，我們用我們以前實(shí)際實(shí)驗(yàn)之一的參數(shù)。對(duì)于一個(gè)51x67單元格的柵格，以及相似的極限值6二5，種子實(shí)例庫(kù)的尺寸為什旦卄旦H丄2.5+1」'|_什旦卄旦H丄2.5+1」'|_2.5+1」丿4J=210個(gè)實(shí)例。與此同時(shí)，如果使用探索式路徑生成算法，雖然實(shí)驗(yàn)所涉及的解空間包括500多個(gè)運(yùn)行，新生成的路徑不可能覆蓋解空間。另一套我們以前的實(shí)驗(yàn)，在仿真環(huán)境下，20，000個(gè)運(yùn)行給出一個(gè)相似的結(jié)果。此外，搜索式算法常常產(chǎn)生隨機(jī)路徑，與實(shí)例庫(kù)中已經(jīng)存在的舊路徑十分相似。新路徑中大約四分之一的路徑是創(chuàng)新性的，即與實(shí)例庫(kù)中的所有路徑不同。新算法有雙重優(yōu)點(diǎn)：（1）它產(chǎn)生的種子實(shí)例庫(kù)可以保證覆蓋機(jī)器人的路徑空間而以前的搜索式算法不能給出這樣的保證。（2）它可以加快學(xué)習(xí)速度因?yàn)樗械穆窂蕉純?chǔ)存在種子實(shí)例庫(kù)中。不像搜索式算法，因?yàn)闄C(jī)器人無(wú)法花時(shí)間在尋找新的創(chuàng)新性解決方案。然而，如果6減小，種子實(shí)例庫(kù)的規(guī)模會(huì)迅速增加。當(dāng)6=2時(shí)。實(shí)例庫(kù)將包含超過一百萬(wàn)的實(shí)例。實(shí)際上，一個(gè)機(jī)器人永遠(yuǎn)不會(huì)嘗試所有可能的解決方案。當(dāng)它找到了一個(gè)足夠好的解決方案，他會(huì)減少探索。當(dāng)現(xiàn)有路徑的花費(fèi)增加時(shí)，它才會(huì)又開始探索新的可能性。種子實(shí)例庫(kù)在理論上保證了概無(wú)可能的解決辦法仍未被發(fā)現(xiàn)。10+13、10J證明上限的想法是為了檢驗(yàn)我們是否能給出實(shí)例庫(kù)中可能案例的最少數(shù)量。這將給實(shí)例庫(kù)設(shè)計(jì)者一個(gè)信心，實(shí)例庫(kù)不會(huì)擴(kuò)展大于一個(gè)必然的可行數(shù)量。不幸的是，實(shí)例庫(kù)的上限太大。在上面所給例子中，（m=51,n=67,10+13、10J=1，44，6個(gè)實(shí)例。因此，保持實(shí)例庫(kù)的規(guī)模受到控制是十分有必要的維修策略。在我們以前的工作中，我們使用過基于解決方案質(zhì)量的遺忘策略。例如，當(dāng)學(xué)習(xí)程序成功驅(qū)動(dòng)機(jī)器人時(shí)只記憶最好的解決方案，當(dāng)學(xué)習(xí)程序驅(qū)動(dòng)失敗，機(jī)器人會(huì)記憶最糟糕的解決方案。然后，實(shí)例庫(kù)只用來(lái)驗(yàn)證一個(gè)新的解決方案是否好到值得從頭開始生成。我們的實(shí)驗(yàn)還沒有表現(xiàn)出遺忘算法的優(yōu)越性。這更能看出實(shí)例庫(kù)的管理技巧很大程度上取決于環(huán)境的特點(diǎn)和手頭上的問題。8.結(jié)論及未來(lái)工作我們的工作是基于一個(gè)事實(shí)，即以前的搜索式算法不可能生成當(dāng)前路徑搜索問題的所有可能的不同解決方案。因此，我們研究這種可能性是為了創(chuàng)造一個(gè)覆蓋機(jī)器人所有解決方案的種子案例庫(kù)。在本文中，我們已經(jīng)證明了解空間的下限和上限。下限的證明表明了生成一個(gè)包含對(duì)任意一條可能路徑密切相符的解集的實(shí)例庫(kù)是可行的。這保證了在理論上沒有路徑仍未被發(fā)現(xiàn)。與此同時(shí)，上限的證明表明將所有不同的可能解決方案保存到實(shí)例庫(kù)是不可行的。為了限制實(shí)例庫(kù)，它在運(yùn)行時(shí)必須加以修正。實(shí)例庫(kù)激增的可能解決方案之一是基于以下觀察。從柵格距離的角度講，盡管實(shí)例庫(kù)包含了距離彼此較遠(yuǎn)的路徑，但仍有許多路徑明顯重疊。如果我們只是盡量覆蓋路徑的網(wǎng)格碎片而不是通過所有路徑本身，那么這會(huì)使得實(shí)例庫(kù)變得更小。如何更好處理這個(gè)問題是未來(lái)研究課題。同樣重要的是要強(qiáng)調(diào)上述例子代表的只是對(duì)一個(gè)問題的解決方案數(shù)量。這個(gè)問題是最普遍的斜對(duì)角間遍歷問題。其他問題是這個(gè)問題的子問題，并將需要少量解決方案覆蓋其解空間。在實(shí)際應(yīng)用中移動(dòng)機(jī)器人通常都有少部分目標(biāo)點(diǎn)（除非它是一個(gè)映射或探索性問題）。在今后的研究中，我們還打算分析解決方案數(shù)量與案例庫(kù)規(guī)模之間的依賴關(guān)系。我們還打算研究一些不同的相似性方式來(lái)更大的減小解空間的規(guī)模。一種可能性是將將其定義為由路徑所包圍的區(qū)域。參考文獻(xiàn)M.KruusaaRepeatedPathPlanningforMobileRobotsinDynamicEnvironments,PhDThesis,ChalmesUniversityofTechnology,Gothenburg,Sweden,2002.H.Hu,M.Brady,Dynamicglobalpathplanningwithuncertaintyformobilerobotsinmanufacturing,iEEeTrans.Robot.Automat.13(5)(1997)760—