李昊 汪超 王進(jìn) 孟濬 由林麟

1.加拿大新不倫瑞克大學(xué) 新不倫瑞克 E3B；2.北京航空航天大學(xué)航空科學(xué)與工程學(xué)院 北京 100191；3.中國(guó)家用電器研究院 北京 100037；4.浙江大學(xué)機(jī)器人研究院 浙江杭州 310027；5.中山大學(xué)智能工程學(xué)院 廣東廣州 510006

1 引言

家用機(jī)器人自90年代以來(lái)就已經(jīng)被廣泛應(yīng)用。一些主要的家用機(jī)器人包括應(yīng)用于清潔的吸塵器、自動(dòng)擦地機(jī)、割草機(jī)、游泳池清潔器和窗戶清潔器等；用于家庭娛樂(lè)的有玩具、業(yè)余興趣機(jī)器人；還有一些家用機(jī)器人主要負(fù)責(zé)家庭安全和監(jiān)視，如機(jī)器視覺(jué)、運(yùn)動(dòng)檢測(cè)機(jī)器人等。

預(yù)計(jì)未來(lái)幾年家用機(jī)器人的應(yīng)用將更加廣泛，有更多創(chuàng)新的人工智能（AI）技術(shù)將得到應(yīng)用。國(guó)際機(jī)器人聯(lián)合會(huì)（International Federation of Robotics）指出美國(guó)服務(wù)機(jī)器人產(chǎn)業(yè)的市場(chǎng)規(guī)模為52億美元。估計(jì)2020年服務(wù)機(jī)器人或家用機(jī)器人將貢獻(xiàn)110億美元的收入。企業(yè)也在加大投資進(jìn)行清潔機(jī)器人的AI研究與開(kāi)發(fā)。2017年2月，戴森公司投資5.87億美元在新加坡建立了研發(fā)技術(shù)中心，進(jìn)行互聯(lián)技術(shù)和機(jī)器人研究。人工智能非盈利組織OpenAI將“家用機(jī)器人”列為重要技術(shù)目標(biāo)之一。

在過(guò)去的十年中，清潔機(jī)器人的功能有了重大改進(jìn)[1]。該市場(chǎng)制造商越來(lái)越多的希望采用AI技術(shù)，特別是在吸塵、擦地板和割草等方面。市場(chǎng)上一些流行的清潔機(jī)器人包括：

iRobot Roomba：當(dāng)iRobot于2002年推出其第一臺(tái)機(jī)器人真空吸塵器Roomba時(shí)，產(chǎn)品只具有基本的AI功能，例如識(shí)別墻壁和使用內(nèi)置傳感器避開(kāi)樓梯。最新的980型Roomba具有由AI驅(qū)動(dòng)的高級(jí)決策功能。該機(jī)器人能夠掃描房間大小、識(shí)別障礙物并記住最有效的路線和方法。

博世Roxxter：博世機(jī)器人吸塵器Roxxter系列利用AI繪制環(huán)境的交互式地圖。機(jī)器人能夠通過(guò)Amazon兼容Alexa的設(shè)備處理語(yǔ)音命令。用戶可以通過(guò)命令A(yù)lexa來(lái)激活Roxxter機(jī)器人。

夏普RX-V100：夏普RX-V100內(nèi)置有語(yǔ)音識(shí)別AI引擎，可通過(guò)閃爍的指示燈和語(yǔ)音消息組合來(lái)執(zhí)行諸如報(bào)告機(jī)器人當(dāng)前狀態(tài)之類的任務(wù)。當(dāng)用戶向機(jī)器人發(fā)出語(yǔ)音命令“清潔”時(shí)，RX-V100使用AI語(yǔ)音回答“好”并“搖擺”以確認(rèn)命令。然后開(kāi)始在自動(dòng)模式下清潔。該產(chǎn)品還提供了一組預(yù)定義的消息和響應(yīng)功能，以進(jìn)行簡(jiǎn)單的對(duì)話。

此外，戴森、三星、Neato等品牌的機(jī)器人產(chǎn)品也都在市場(chǎng)中得到了較好的反響。

機(jī)器人吸塵器的設(shè)計(jì)和開(kāi)發(fā)通?；谑袌?chǎng)上的低成本組件，其吸塵結(jié)構(gòu)圖如圖1所示。吸塵器底座帶有電機(jī)及控制電路、驅(qū)動(dòng)輪、編碼器、腳輪等；底座可以移動(dòng)并攜帶電池、吸塵裝置、控制系統(tǒng)等其它組件。傳感器系統(tǒng)通常包括超聲波測(cè)距儀傳感器、相機(jī)、激光雷達(dá)、陀螺儀、IMU等。通訊系統(tǒng)有無(wú)線通訊、I/O總線、RS-232串行端口等。嵌入控制系統(tǒng)從傳感器接收測(cè)量信息，再依次處理傳感器信息、環(huán)境建模、導(dǎo)航、控制、執(zhí)行車輪速度命令并將這些命令發(fā)送到電動(dòng)機(jī)，以控制電機(jī)執(zhí)行任務(wù)。機(jī)器人控制器在主機(jī)中創(chuàng)建、開(kāi)發(fā)，然后下載到嵌入控制系統(tǒng)。本文主要介紹用于機(jī)器人吸塵器的環(huán)境建模和導(dǎo)航的人工智能技術(shù)。

圖1 機(jī)器人吸塵器結(jié)構(gòu)圖

在吸塵器機(jī)器人開(kāi)始任務(wù)前，必須完成環(huán)境建模。環(huán)境建模是基于工作空間地圖而實(shí)現(xiàn)的，而工作空間的地圖則是通過(guò)攝像頭、紅外傳感器或超聲波傳感器等不同傳感裝置獲得的傳感數(shù)據(jù)構(gòu)建。由于室內(nèi)掃地機(jī)器人缺少諸如GPS之類的絕對(duì)定位系統(tǒng)，因此機(jī)器人位置逐漸漂移，姿態(tài)的不確定性也越來(lái)越大。同步定位和映射（SLAM）技術(shù)的發(fā)展極大地改善了機(jī)器人的定位精度，該技術(shù)通過(guò)統(tǒng)計(jì)數(shù)據(jù)的方式來(lái)估計(jì)機(jī)器人的姿態(tài)（位置和方向）并對(duì)其進(jìn)行糾正。在智能機(jī)器人吸塵器頂部，配置一個(gè)攝像頭或激光雷達(dá)，利用SLAM技術(shù)對(duì)傳感器數(shù)據(jù)進(jìn)行處理。而SLAM算法是一種動(dòng)態(tài)構(gòu)建地圖同時(shí)跟蹤自己位置的方法，該算法可以處理相機(jī)圖片或雷達(dá)數(shù)據(jù)，從中挑選出例如室內(nèi)物體的邊角等諸多環(huán)境特征。機(jī)器人記住這些特征的形狀并在移動(dòng)時(shí)對(duì)其進(jìn)行跟蹤。在工作過(guò)程中，機(jī)器人將連續(xù)采集數(shù)據(jù)，檢測(cè)和跟蹤新特征，并逐步建立環(huán)境地圖。在自身定位方面，在機(jī)器人底部通常安裝編碼器、陀螺儀、IMU等傳感器，機(jī)器人需要將該環(huán)境地圖、里程表及其他傳感器結(jié)合。一旦機(jī)器人吸塵器獲取了自己的位置，便可以執(zhí)行各種任務(wù)。機(jī)器人可以進(jìn)行直線吸塵，以提高覆蓋效率。如果充電電池電量不足，機(jī)器人可以在房間內(nèi)直線返回充電器進(jìn)行充電。即使清潔工作還未完成，機(jī)器人也能記住確切位置，充電完成后再返回該處繼續(xù)完成剩余吸塵任務(wù)。環(huán)境建模和定位功能解決了傳統(tǒng)吸塵器沒(méi)有定位和導(dǎo)航功能，無(wú)法清理多個(gè)房間，以及充電后無(wú)法回到暫停位置繼續(xù)工作的問(wèn)題。

機(jī)器人吸塵器的一項(xiàng)重要任務(wù)是掃除整個(gè)環(huán)境中的每個(gè)可及區(qū)域，并避開(kāi)障礙物。當(dāng)機(jī)器人通過(guò)某個(gè)區(qū)域的位置時(shí)，將對(duì)其進(jìn)行清潔，如果尚未清潔，該區(qū)域則會(huì)保持不清潔狀態(tài)。機(jī)器人吸塵器設(shè)置了室內(nèi)地圖后，就能夠規(guī)劃覆蓋室內(nèi)的路徑。這種機(jī)制稱為覆蓋區(qū)域路徑規(guī)劃。覆蓋路徑規(guī)劃（CPP）的任務(wù)是確定一條路徑，該路徑將經(jīng)過(guò)感興趣區(qū)域中的所有點(diǎn)，同時(shí)避開(kāi)障礙物。路徑規(guī)劃是許多機(jī)器人應(yīng)用的必須功能，例如吸塵機(jī)器人、噴漆機(jī)器人、自動(dòng)水下機(jī)器人、割草機(jī)、自動(dòng)收割機(jī)、窗戶清潔器和復(fù)雜結(jié)構(gòu)的檢查器具等。要清潔一個(gè)房間，可以使用螺旋形或弓字形的運(yùn)動(dòng)軌跡。在該區(qū)域中，機(jī)器人應(yīng)通過(guò)覆蓋路徑規(guī)劃清掃每個(gè)可到達(dá)的自由區(qū)域，并以有效的軌跡避開(kāi)障礙物。這種有效的軌跡應(yīng)該是短距離的，并且包含最小數(shù)量的轉(zhuǎn)彎角。

本文主要介紹了機(jī)器人吸塵器的定位及室內(nèi)建模的技術(shù)，同時(shí)對(duì)路徑規(guī)劃問(wèn)題及相關(guān)算法進(jìn)行詳細(xì)的描述，給出了路徑規(guī)劃算法的案例及結(jié)果。

2 機(jī)器人吸塵器的定位及室內(nèi)建模技術(shù)

同步定位和映射（SLAM）技術(shù)通過(guò)機(jī)器人定位來(lái)建立環(huán)境地圖，同時(shí)解決定位和地圖的計(jì)算問(wèn)題。該技術(shù)在構(gòu)造或更新未知環(huán)境地圖時(shí)同時(shí)跟蹤機(jī)器人位置。主流的近似求解方法包括粒子濾波器、擴(kuò)展卡爾曼濾波器、協(xié)方差交點(diǎn)和GraphSLAM。其中基于統(tǒng)計(jì)的卡爾曼濾波器和粒子濾波器也被稱為蒙特卡洛法，它們?yōu)闄C(jī)器人的姿態(tài)和地圖參數(shù)提供了后驗(yàn)概率函數(shù)的估計(jì)；使用協(xié)方差交集近似上述模型的方法能夠避免依賴統(tǒng)計(jì)的獨(dú)立性假設(shè)來(lái)降低算法復(fù)雜性；而GraphSLAM算法仍然是一個(gè)新的研究領(lǐng)域，是否應(yīng)用通常是由對(duì)地圖、傳感器和模型類型的不同要求來(lái)決定。

SLAM算法廣泛用于導(dǎo)航、機(jī)器人定位、自動(dòng)駕駛汽車、無(wú)人駕駛飛機(jī)、水下自動(dòng)駕駛、行星漫游車、家用機(jī)器人等。

2.1 濾波

室內(nèi)環(huán)境的建模需要對(duì)傳感器數(shù)據(jù)進(jìn)行濾波，主要方法包括卡爾曼濾波、擴(kuò)展卡爾曼濾波、粒子濾波等。這些方法都基于貝葉斯濾波。通過(guò)對(duì)吸塵器傳感器濾波研究，可以對(duì)吸塵器定位，并建立室內(nèi)環(huán)境地圖。

2.1.1 貝葉斯定理

貝葉斯定理又稱為貝葉斯定律或貝葉斯規(guī)則，該定理是基于對(duì)事件之條件相關(guān)的先驗(yàn)知識(shí)來(lái)描述事件的概率。比如已知發(fā)生健康問(wèn)題的風(fēng)險(xiǎn)會(huì)隨著年齡的增長(zhǎng)而增加，貝葉斯定理則認(rèn)為比僅假設(shè)某人是整個(gè)人口中的典型情況更準(zhǔn)確地是評(píng)估已知年齡人的健康風(fēng)險(xiǎn)。貝葉斯推理是貝葉斯定理的一個(gè)擴(kuò)展，是統(tǒng)計(jì)推理的一種特殊方法。貝葉斯定理中涉及的概率可能具有不同的概率解釋。通過(guò)貝葉斯概率，該定理表達(dá)了應(yīng)合理改變概率以說(shuō)明相關(guān)證據(jù)的可用性。貝葉斯推理是貝葉斯統(tǒng)計(jì)的基礎(chǔ)。貝葉斯定理已在機(jī)器人領(lǐng)域廣泛應(yīng)用，用于去除或降低傳感器的噪音，以降低不確定性。通過(guò)使用貝葉斯定理，可以有效處理機(jī)器人吸塵器的傳感器數(shù)據(jù)，實(shí)現(xiàn)定位、環(huán)境建模、檢測(cè)障礙物等功能。貝葉斯定理中P(B)代表測(cè)量概率，(B│A)代表可能性，P(A)代表先驗(yàn)知識(shí)，公式如下：

貝葉斯定理解決了用吸塵器的低精度傳感器計(jì)算室內(nèi)環(huán)境模型的難題。

2.1.2 卡爾曼濾波（KF）

卡爾曼濾波（KF）可以用于處理吸塵器的傳感器數(shù)據(jù)，進(jìn)行定位及環(huán)境建模?？柭鼮V波是一種統(tǒng)計(jì)和控制理論算法，該算法使用隨時(shí)間推移觀察到的一系列測(cè)量值（包含統(tǒng)計(jì)噪聲和其他誤差），并生成未知變量的估計(jì)值，該估計(jì)值通過(guò)估計(jì)每個(gè)時(shí)間范圍內(nèi)變量的概率分布得出，比僅基于單個(gè)測(cè)量的結(jié)果更準(zhǔn)確。卡爾曼濾波是貝葉斯定理在存在高斯分布噪音的線性系統(tǒng)模型時(shí)的一個(gè)簡(jiǎn)單應(yīng)用。該過(guò)濾器以其理論的主要開(kāi)發(fā)者Rudolf Kalman命名?？柭鼮V波器在技術(shù)上有許多應(yīng)用，常見(jiàn)的應(yīng)用是運(yùn)動(dòng)物體的導(dǎo)航和控制，尤其是飛機(jī)、航天器和動(dòng)態(tài)定位的船舶?？柭鼮V波器是機(jī)器人運(yùn)動(dòng)和控制領(lǐng)域的主要方法之一。

2.1.3 擴(kuò)展卡爾曼濾波（EKF）

對(duì)于存在高斯分布噪聲的線性系統(tǒng)模型，卡爾曼濾波器是最佳的線性估計(jì)器。然而在現(xiàn)實(shí)工程中，大多系統(tǒng)具有非線性，需要對(duì)卡爾曼濾波器進(jìn)行改進(jìn)以便應(yīng)用于非線性系統(tǒng)。擴(kuò)展卡爾曼濾波（EKF）使用了多元泰勒級(jí)數(shù)展開(kāi)式及雅各布矩陣，以線性化工作點(diǎn)模型。通過(guò)線性近似，得以對(duì)具有高斯分布噪聲的非線性系統(tǒng)模型進(jìn)行估計(jì)。因此，通常先建立機(jī)器人吸塵器及其傳感器的非線性模型，然后用泰勒級(jí)數(shù)對(duì)其線性化，最后使用擴(kuò)展卡爾曼濾波進(jìn)行數(shù)據(jù)處理。

2.1.4 粒子濾波器

如果系統(tǒng)模型是非線性的且噪音不是高斯分布，則采用蒙特卡洛方法如粒子濾波器進(jìn)行數(shù)據(jù)處理并估計(jì)。這種蒙特卡洛技術(shù)最早用于火箭或太空技術(shù)，缺點(diǎn)是計(jì)算方面更加耗時(shí)。

2.2 地圖及定位

機(jī)器人吸塵器需要解決室內(nèi)定位、姿態(tài)估計(jì)和地圖建模的問(wèn)題。問(wèn)題的難點(diǎn)在于需要地圖才能進(jìn)行定位，需要位置姿態(tài)的精確信息才能測(cè)量繪制室內(nèi)地圖。SLAM是同時(shí)解決這兩個(gè)問(wèn)題的技術(shù)[2]。定位即先給定一個(gè)地圖，再進(jìn)行定位；地圖繪制則為先給定位置姿態(tài)，再測(cè)繪室內(nèi)地圖，如圖2所示。

圖2 地圖繪制

地圖主要有幾種：

（1）拓?fù)鋱D：拓?fù)鋱D是一種環(huán)境地圖表示的方法，它捕獲環(huán)境的連通性（即拓?fù)洌?，而不是?chuàng)建幾何上精確的圖。

（2）特征地圖：特征地圖是使用環(huán)境中的主要特征點(diǎn)及其位置來(lái)繪制地圖。

（3）網(wǎng)格地圖：網(wǎng)格地圖的基本思想是將環(huán)境圖表示為均勻分布的二進(jìn)制隨機(jī)變量的字段，每個(gè)字段代表環(huán)境中該位置存在障礙物。網(wǎng)格地圖算法計(jì)算近似后驗(yàn)估計(jì)隨機(jī)變量。

基于特征的定位方法：

定位指使用傳感器信息在環(huán)境中定位機(jī)器人，目的是找到給定的機(jī)器人位置。主要需要兩個(gè)模型進(jìn)行濾波定位：

（1）控制輸入和運(yùn)動(dòng)模型；

（2）傳感器測(cè)量和測(cè)量模型。

機(jī)器人吸塵器的運(yùn)動(dòng)模型如圖3所示。

EKF SLAM利用擴(kuò)展的卡爾曼濾波器（EKF）進(jìn)行同步定位和映射（SLAM）。EKF SLAM算法基于特征，并使用最大近似算法進(jìn)行數(shù)據(jù)關(guān)聯(lián)。直到FastSLAM出現(xiàn)，EKF SLAM一直是SLAM的主流方法。假設(shè)機(jī)器人具有基于特征的地圖，機(jī)器人可以將傳感器讀數(shù)與期望值進(jìn)行比較（基于當(dāng)前估計(jì)的機(jī)器人姿態(tài)）。傳感器需要測(cè)量特征的方位、范圍及相對(duì)位置，利用擴(kuò)展卡爾曼濾波器（EKF），將不確定性測(cè)量結(jié)果與機(jī)器人姿態(tài)的當(dāng)前估計(jì)值合并。通過(guò)運(yùn)動(dòng)學(xué)模型實(shí)現(xiàn)機(jī)器人姿態(tài)Xt的預(yù)測(cè)更新。控制信號(hào)Ut-1是運(yùn)動(dòng)學(xué)模型的輸入。使用已知特征位置M和估計(jì)姿勢(shì)Xt計(jì)算預(yù)測(cè)。然后，EKF用于融合距離和方位測(cè)量值Zt，以減少姿態(tài)不確定性。EKF SLAM的定位結(jié)果如圖4所示。

圖3 機(jī)器人運(yùn)動(dòng)模型

圖4 機(jī)器人定位（Matlab運(yùn)行結(jié)果）

機(jī)械人的狀態(tài)是向量X=[x yθ]T，測(cè)量值是Z=[dα]T，其中d是距離，α是傳感器測(cè)得的角度。運(yùn)動(dòng)命令是前進(jìn)速度和角速度。機(jī)器人不能完美執(zhí)行命令并運(yùn)動(dòng)。在運(yùn)動(dòng)中存在一些高斯噪聲，并相應(yīng)地改變了機(jī)器人的實(shí)際姿勢(shì)。傳感器測(cè)量機(jī)器人的實(shí)際運(yùn)動(dòng)，但也存在一些高斯噪聲。需要根據(jù)上述信息，找到系統(tǒng)的運(yùn)動(dòng)模型和測(cè)量模型，然后線性化運(yùn)動(dòng)模型和測(cè)量模型，并進(jìn)行濾波定位。這里使用EKF進(jìn)行狀態(tài)估計(jì)和校正。EKF是對(duì)非線性系統(tǒng)的線性卡爾曼濾波器的擴(kuò)展，它使用關(guān)于當(dāng)前均值和協(xié)方差值的泰勒線性化。類似于線性卡爾曼濾波器，EKF算法具有兩個(gè)主要步驟，即“預(yù)測(cè)”和“更新”。非線性系統(tǒng)可以描述為狀態(tài)函數(shù)f和觀察函數(shù)h。X是n×1狀態(tài)向量，Z是m×1狀態(tài)向量，U是控制信號(hào)。R和Q分別是過(guò)程和觀測(cè)高斯噪聲，其中R和Q為協(xié)方差矩陣。EKF使用f的雅可比行列式Jx。在每個(gè)步驟中，EKF計(jì)算狀態(tài)的估計(jì)值并更新不確定性，以及關(guān)聯(lián)狀態(tài)協(xié)方差矩陣。

3 路徑規(guī)劃

獲取了室內(nèi)環(huán)境地圖及定位信息后，要進(jìn)行機(jī)器人吸塵器的路徑規(guī)劃。覆蓋路徑規(guī)劃（CPP）是掃地機(jī)器人的一個(gè)重要功能。通過(guò)檢測(cè)灰塵、構(gòu)建室內(nèi)地面模型的方式，使掃地機(jī)器人在清掃時(shí)使用傳感器和吸塵器有效覆蓋所需清潔區(qū)域。以下簡(jiǎn)要介紹覆蓋路徑規(guī)劃的一些研究。

利用精確的單元分解算法將自由空間（即沒(méi)有障礙的空間）分解為簡(jiǎn)單的、不重疊的區(qū)域，并稱之為單元。所有單元的并集恰好填充了自由空間。這些區(qū)域沒(méi)有障礙物，可以“輕松”地遮蓋起來(lái)，并且可以通過(guò)機(jī)器人簡(jiǎn)單的動(dòng)作將其掃過(guò)。例如，每個(gè)單元都可以使用弓形的“割草”模式覆蓋。通常，基于精確的單元分解算法會(huì)分兩步生成覆蓋路徑：首先將自由空間分解為單元格，并將分解結(jié)果存儲(chǔ)為鄰接圖，再計(jì)算覆蓋鄰接圖的詳盡序列，所獲得的詳盡行動(dòng)路線是一系列節(jié)點(diǎn)，而不是實(shí)際的覆蓋路徑。

此后，一種基于摩爾斯功能臨界點(diǎn)的新型單元分解方法被提出?；谀査沟姆纸饩哂刑幚矸嵌噙呅握系K的優(yōu)勢(shì)。通過(guò)選擇不同的莫爾斯函數(shù)，可以獲得不同的單元形狀，例如圓形或尖刺。從理論上講，莫爾斯分解可以應(yīng)用于任何n維空間。通過(guò)使用一種感官距離信息檢測(cè)臨界點(diǎn)從而進(jìn)行平面空間覆蓋的方法，可確保遇到目標(biāo)區(qū)域中的所有臨界點(diǎn)。因此，這種方法可以實(shí)現(xiàn)完全覆蓋。

后來(lái)，一種用于移動(dòng)機(jī)器人的在線拓?fù)涓采w算法被提出。這種方法旨在用于簡(jiǎn)單的平面環(huán)境。雖然類似摩爾斯分解，但此處提出的拓?fù)渌惴ㄊ鞘褂貌煌氖录?lái)確定單元邊界。摩爾斯分解法是將單元邊界置于障礙物表面的關(guān)鍵點(diǎn)上，然而直線環(huán)境不能通過(guò)摩爾斯分解來(lái)處理，因?yàn)檫@種環(huán)境的臨界點(diǎn)已經(jīng)退化。另一方面，由于關(guān)鍵點(diǎn)只能在機(jī)器人執(zhí)行沿著墻走動(dòng)的指令時(shí)顯示在機(jī)器人的側(cè)面，因此需要一個(gè)矩形的覆蓋圖案，包括重新繪制軌跡。相比之下，拓?fù)浞椒梢允褂酶?jiǎn)單的界標(biāo)來(lái)確定被稱為“切片分解”的精確單元分解。由于使用了簡(jiǎn)單的地標(biāo)，切片分解可以處理更多種環(huán)境，包括具有多邊形、橢圓形和直線形障礙物的環(huán)境。此外，還可以從機(jī)器人的所有側(cè)面檢測(cè)障礙物，從而可以使用簡(jiǎn)單的弓形圖案而無(wú)需使用軌跡，該方法生成的覆蓋路徑更短。

另一種方法是基于接觸傳感器的直線環(huán)境覆蓋。這是一種精確的單元分解算法，用于接觸感應(yīng)機(jī)器人（即沒(méi)有范圍感應(yīng)）在線覆蓋未知的直線環(huán)境。在該系統(tǒng)中，平面線性電動(dòng)機(jī)在類似桌子的表面上運(yùn)行。實(shí)際上，這個(gè)方法構(gòu)造的分解可以看作是摩爾斯分解，然而所有臨界點(diǎn)都退化了。

還有一種方法是基于圖形表示的環(huán)境覆蓋算法，圖形可以是街道或道路網(wǎng)絡(luò)。這種方法解決了一些覆蓋率方面的問(wèn)題。首先，考慮到以圖形提供的先前地圖信息可能不完整；其次，考慮了環(huán)境約束，例如單行道；第三，當(dāng)執(zhí)行覆蓋路徑時(shí)，機(jī)器人的傳感器檢測(cè)到圖形中的變化后，將提供在線重新計(jì)劃的策略。圖形搜索算法能夠?yàn)閳D表的每個(gè)邊界分配一個(gè)數(shù)值并尋找最佳解決方案，或者在時(shí)間限制下找到一種近似優(yōu)化的解決方案。

3.1 覆蓋路徑規(guī)劃的定義

為了正式定義路徑規(guī)劃問(wèn)題，我們需要定義一些基本術(shù)語(yǔ)，如下：

配置空間（Q）：機(jī)器人可以實(shí)現(xiàn)的所有配置的集合。Q可以細(xì)分為自由配置空間Qfree和占用配置空間Qobs。Qobs中的任何配置都會(huì)導(dǎo)致與障礙物的接觸，而Qfree中的任何配置都不會(huì)。

工作區(qū)或環(huán)境（W）：機(jī)器人所在的世界。

路徑：通過(guò)Qfree的參數(shù)化曲線。

自由度：代表機(jī)器人配置所需的最少自變量。要完全描述移動(dòng)機(jī)器人，需要六個(gè)自由度：{x，y，z，φ，θ，ψ}，其中x，y和z表示3D空間中的位置，而φ，θ和ψ是歐拉角。通過(guò)假設(shè)θ=φ=0在2D平面完成掃地機(jī)器人的路徑規(guī)劃，在這種情況下存在3個(gè)自由度：{x，y，ψ}。

我們可以將路徑規(guī)劃的任務(wù)定義為在自由配置空間Qfree中找到一條曲線，該曲線連接起始位置q=qs與目標(biāo)位置q=qg。

路徑規(guī)劃任務(wù)通常屬于以下四個(gè)應(yīng)用：

（1）導(dǎo)航：在有障礙的環(huán)境中找到無(wú)碰撞的路徑。

（2）環(huán)境覆蓋：移動(dòng)傳感器覆蓋環(huán)境中的每個(gè)點(diǎn)。

（3）定位：使用傳感器數(shù)據(jù)來(lái)確定機(jī)器人在環(huán)境中的配置。

（4）建地圖：使用傳感器探索以前未知的環(huán)境。

本文介紹的大多數(shù)算法都適用于導(dǎo)航與環(huán)境覆蓋。它們對(duì)機(jī)器人吸塵器的路徑規(guī)劃很重要。以下術(shù)語(yǔ)定義路徑規(guī)劃算法的屬性，用作比較的基礎(chǔ)。

（1）最優(yōu)性：一種優(yōu)化（最大化或最小化）目標(biāo)的算法。

（2）完整性：如果路徑規(guī)劃算法始終能找到解決方案或在有限時(shí)間內(nèi)確定不存在解決方案，那么該算法是完整的。如果路徑完整且易于離散化，則也可以認(rèn)為該路徑已完成?；蛘?，如果可以保證算法收斂到完整性，則稱該算法是概率完整的。

（3）離線路徑規(guī)劃：在執(zhí)行任務(wù)之前了解所有環(huán)境知識(shí)，并完成路徑規(guī)劃。

（4）在線路徑規(guī)劃：在執(zhí)行任務(wù)過(guò)程中逐步構(gòu)建路徑。

（5）基于傳感器的路徑規(guī)劃：在線處理傳感器信息并用于規(guī)劃。

（6）思考式：意識(shí)思考 → 規(guī)劃 → 執(zhí)行任務(wù)。

（7）反應(yīng)式：使用感官信息來(lái)完成任務(wù)，而無(wú)需構(gòu)建整個(gè)環(huán)境。

覆蓋路徑規(guī)劃的目標(biāo)是生成一條路徑，該路徑將使工作空間中的每個(gè)點(diǎn)都被傳感器覆蓋，而不是生成從起點(diǎn)到目標(biāo)點(diǎn)的導(dǎo)航。該問(wèn)題可以表述為：考慮一個(gè)帶有嵌入傳感器的移動(dòng)機(jī)器人，其傳感器帶有一些二維覆蓋區(qū)域A。在工作空間W內(nèi)的軌跡將產(chǎn)生一組N個(gè)傳感器讀數(shù)：{A1，A2，...，AN}。覆蓋路徑規(guī)劃的目標(biāo)是生成一條穿過(guò)工作空間的路徑，使覆蓋W，這意味著一段時(shí)間后，傳感器覆蓋區(qū)已通過(guò)工作空間W中的每個(gè)點(diǎn)[3]。

3.2 路徑規(guī)劃算法

一旦掃地機(jī)器人建立了環(huán)境地圖，并且機(jī)器人已經(jīng)能夠自我定位，就必須完成路徑規(guī)劃的高級(jí)任務(wù)，以完成其任務(wù)目標(biāo)。通常，路徑由一組要連續(xù)命中的航路點(diǎn)表示。這些航路點(diǎn)被用作外環(huán)參考，內(nèi)環(huán)控制器將能夠控制機(jī)器人跟蹤參考路徑。鑒于外環(huán)引用獨(dú)立于電機(jī)控制，因此可以開(kāi)發(fā)出與系統(tǒng)硬件無(wú)關(guān)的非常通用的路徑規(guī)劃算法。航路點(diǎn)可以根據(jù)當(dāng)前的最新信息一次生成，也可以提前進(jìn)行全面規(guī)劃。例如，傳統(tǒng)的覆蓋路徑規(guī)劃使用一系列預(yù)先定義好的航路點(diǎn)來(lái)定義路徑（通常是弓字或之字形路徑）。航點(diǎn)定義的路徑的替代方法是更基于反應(yīng)行為的規(guī)劃。例如，可以通過(guò)保持距離墻壁的距離，或避開(kāi)障礙物，或遵循諸如室內(nèi)家具結(jié)構(gòu)來(lái)指定路徑軌跡。在這種被動(dòng)的方法中，沒(méi)有建立環(huán)境模型來(lái)輔助決策過(guò)程，因此很難實(shí)現(xiàn)全局目標(biāo)。路徑規(guī)劃的任務(wù)取決于許多因素，例如有關(guān)環(huán)境的信息，規(guī)劃路徑的期望質(zhì)量及任務(wù)。如果事先可以獲得詳細(xì)的環(huán)境信息，則路徑生成可能會(huì)很慢。如果需要即時(shí)規(guī)劃路徑，則需要一種可以接近實(shí)時(shí)運(yùn)行的算法。本節(jié)將總結(jié)現(xiàn)有的主要路徑規(guī)劃算法。

路徑規(guī)劃的方法有許多種。一些覆蓋路徑規(guī)劃的問(wèn)題，可以視為確定性方法，不考慮不確定性，可以在理想狀況下證明完整性。采用非確定性或概率性方法對(duì)傳感器和執(zhí)行器的噪聲魯棒性更好，但不能保證路徑的完整性。簡(jiǎn)單的覆蓋路徑規(guī)劃算法定義了預(yù)定形狀（如弓字形或之字形）的結(jié)構(gòu)化路徑，以確保覆蓋。一些復(fù)雜的方法則從搜索空間生成非結(jié)構(gòu)化軌跡，以實(shí)現(xiàn)探索目標(biāo)。

覆蓋路徑規(guī)劃的方法有啟發(fā)規(guī)則式、隨機(jī)式、單元分解技術(shù)、基于網(wǎng)格的方法：

（1）啟發(fā)規(guī)則式方法定義了要遵循的一組規(guī)則，這些規(guī)則最終導(dǎo)致覆蓋整個(gè)環(huán)境。

（2）隨機(jī)式方法通過(guò)隨機(jī)移動(dòng)，最終重復(fù)多次覆蓋整個(gè)環(huán)境。

（3）單元分解技術(shù)用于將環(huán)境劃分為可管理數(shù)量的單元或區(qū)域，可以采用圖形或查詢樹(shù)等搜索方法進(jìn)行路徑規(guī)劃。一旦所有單元都被覆蓋，則整個(gè)工作區(qū)都被覆蓋。分解可以是近似、半近似或精確分解。單元的形狀和分解類型可能會(huì)對(duì)搜索算法的性能產(chǎn)生影響。覆蓋路徑規(guī)劃算法的其他應(yīng)用包括：無(wú)人駕駛飛機(jī)、3D地形覆蓋，以及用于農(nóng)業(yè)的機(jī)器等。

（4）基于網(wǎng)格的方法是使用分解為統(tǒng)一網(wǎng)格單元的集合來(lái)表示環(huán)境。這種網(wǎng)格表示環(huán)境的方法是使用安裝在移動(dòng)機(jī)器人上的傳感器來(lái)繪制室內(nèi)環(huán)境圖。在此表示形式中，每個(gè)網(wǎng)格單元都存在一個(gè)關(guān)聯(lián)的值，該值可以表示是否存在障礙物或是否為自由空間。該值可以是二進(jìn)制值，也可以是概率值。通常，每個(gè)網(wǎng)格單元都是正方形，但是也可以使用不同的網(wǎng)格單元形狀，例如三角形。這種近似表示的結(jié)果是，大多數(shù)基于網(wǎng)格的方法都是“分辨率完整的”，也就是說(shuō)，其完整性取決于網(wǎng)格圖的分辨率。

簡(jiǎn)單的啟發(fā)式、反應(yīng)性方法可以通過(guò)遵循簡(jiǎn)單的規(guī)則來(lái)覆蓋整個(gè)工作空間。這種方法功能非常有限，無(wú)法處理計(jì)劃之外的情況，但是這種方法無(wú)需對(duì)環(huán)境的認(rèn)知或地圖。如果有地圖，那么計(jì)劃的選擇就會(huì)大大增加。一些算法依據(jù)障礙物的位置和目標(biāo)點(diǎn)在整個(gè)工作空間上生成潛在函數(shù)，使機(jī)器人跟隨每個(gè)位置的勢(shì)函數(shù)負(fù)梯度的方向。

自由空間的維數(shù)也可以減小以形成類似于路線圖的方案。路線圖必須遵循的規(guī)則是可以以某種簡(jiǎn)單的方式從自由空間的任意點(diǎn)進(jìn)入路線圖，并且路線圖本身已連接。單元分解法將環(huán)境分解為小塊的集合，這些小塊通常稱為單元。路線圖和單元分解的結(jié)果是將工作空間轉(zhuǎn)換為抽象表達(dá)，可以將其視為帶有節(jié)點(diǎn)的圖形，并通過(guò)邊連接。構(gòu)建圖形后，必須對(duì)其進(jìn)行搜索。遍歷或搜索圖形的算法在文獻(xiàn)中很常見(jiàn)。

由于基于網(wǎng)格的方法僅近似目標(biāo)區(qū)域及其障礙物的形狀，因此基于網(wǎng)格的方法也可歸類為近似單元分解。另外，受仿生啟發(fā)的生物算法和神經(jīng)網(wǎng)絡(luò)、深度學(xué)習(xí)等方法也可以解決包括搜索在內(nèi)的各種問(wèn)題。

以下使用簡(jiǎn)單2D環(huán)境比較各種算法。隨機(jī)放置的紅色方塊表示障礙，起點(diǎn)和終點(diǎn)如圖5所示。

圖5 路徑規(guī)劃環(huán)境（Matlab運(yùn)行結(jié)果）

3.2.1 啟發(fā)式反應(yīng)算法

蟲(chóng)子算法是一種簡(jiǎn)單的啟發(fā)式方法，可以幫助機(jī)器人在充滿障礙的環(huán)境中從起點(diǎn)導(dǎo)航到目標(biāo)。

1代蟲(chóng)子算法假定機(jī)器人只有接觸傳感器和目標(biāo)所在位置的信息。機(jī)器人開(kāi)始向目標(biāo)移動(dòng)，如果遇到障礙，就會(huì)繞過(guò)障礙找到最接近目標(biāo)的點(diǎn)，然后機(jī)器人會(huì)一直移動(dòng)到那個(gè)點(diǎn)，直到達(dá)到目標(biāo)為止。如果前進(jìn)方向與已知障礙相交，則推斷沒(méi)有通往目標(biāo)的路徑。事實(shí)證明，這種方法是完整的，也意味著機(jī)器人可以在有限的時(shí)間內(nèi)找到目標(biāo)或報(bào)告沒(méi)有可能通往目標(biāo)的路徑。

用1代蟲(chóng)子算法生成的路徑如圖6所示。

圖6 1代蟲(chóng)子算法規(guī)劃的路徑（Matlab運(yùn)行結(jié)果）

2代蟲(chóng)子算法則在起點(diǎn)和目標(biāo)點(diǎn)之間繪制一條假想線，機(jī)器人遵循這條線移動(dòng)，如果遇到障礙，將會(huì)繞過(guò)障礙，直到與線相交，然后繼續(xù)前進(jìn)。2代蟲(chóng)子算法通常比1代蟲(chóng)子算法快，但缺點(diǎn)是無(wú)法保證在有限的時(shí)間內(nèi)找到目標(biāo)，因?yàn)檫@種算法可能被某些奇形怪狀的障礙難住。如果機(jī)器人在映射中遇到已訪問(wèn)的點(diǎn)，則算法失敗。2代蟲(chóng)子算法生成的路徑如圖7所示。

還有一種類似蟲(chóng)子算法的方法叫做“相切蟲(chóng)”算法。“相切蟲(chóng)”算法假定機(jī)器人配備了范圍傳感器。機(jī)器人開(kāi)始朝目標(biāo)方向移動(dòng)，如果測(cè)距傳感器檢測(cè)到障礙物，則機(jī)器人會(huì)將其軌跡改變到測(cè)距傳感器上的點(diǎn)，以避開(kāi)障礙物并將其推向目標(biāo)。產(chǎn)生的路徑與障礙物相切。這種方法的性能大大超過(guò)1代蟲(chóng)子算法和2代蟲(chóng)子算法，但需要使用額外的傳感器。在所有蟲(chóng)子算法中，必須在搜索之前選擇繞過(guò)障礙的方向。通常，此選擇是隨機(jī)進(jìn)行的，但會(huì)對(duì)輸出路徑的長(zhǎng)度產(chǎn)生顯著影響。

3.2.2 勢(shì)能場(chǎng)算法

現(xiàn)有的目標(biāo)、障礙位置等環(huán)境知識(shí)可用來(lái)定義一個(gè)勢(shì)能場(chǎng)。規(guī)劃路徑可以由勢(shì)能函數(shù)的負(fù)漸變生成。此方法計(jì)算簡(jiǎn)單，因?yàn)椴恍枰阉鞔_定路徑，而是自動(dòng)選擇勢(shì)能場(chǎng)負(fù)梯度的方向。勢(shì)能場(chǎng)如圖8所示。圖中障礙物所在位置勢(shì)能高，目標(biāo)位置勢(shì)能低。

圖7 2代蟲(chóng)子算法規(guī)劃的路徑（Matlab運(yùn)行結(jié)果）

圖8 勢(shì)能場(chǎng)（Matlab運(yùn)行結(jié)果）

勢(shì)能場(chǎng)方法通過(guò)將目標(biāo)看作吸引力，將障礙物看作排斥力來(lái)生成勢(shì)場(chǎng)函數(shù)，空間中的任何一點(diǎn)的勢(shì)能函數(shù)是正負(fù)力的和：

勢(shì)能場(chǎng)算法快速且能夠處理多自由度的場(chǎng)景。在循環(huán)中，先計(jì)算吸引和排斥力矢量和梯度，然后計(jì)算梯度下降。在循環(huán)中的每一步，都會(huì)沿負(fù)梯度的方向移動(dòng)一些距離。

勢(shì)能場(chǎng)算法生成的路徑如圖9所示。

圖9 勢(shì)能場(chǎng)算法規(guī)劃的路徑（Matlab運(yùn)行結(jié)果）

3.2.3 波浪邊緣算法

波浪邊緣算法與勢(shì)能場(chǎng)算法相似，但在幾個(gè)重要方面有所不同。波浪邊緣算法對(duì)自由空間中的每一點(diǎn)的勢(shì)能都是通過(guò)模擬從目標(biāo)位置移動(dòng)到起點(diǎn)的波產(chǎn)生?？捎每臻g由網(wǎng)格表示，所有網(wǎng)格的初始化都為不可見(jiàn)。目標(biāo)單元格初始標(biāo)記為已訪問(wèn)并指定值2，然后，此算法迭代查找訪問(wèn)的單元格中未被查看的相鄰單元，并為其分配一個(gè)大于訪問(wèn)的單元格的值。結(jié)果將是一個(gè)“波浪”從目標(biāo)單元向外輻射，新單元?jiǎng)t被分配到增加的值。

一旦波浪邊緣到達(dá)起始單元，表示勢(shì)能方程完成，然后通過(guò)梯度遞減規(guī)劃路徑。通過(guò)從起始位置開(kāi)始并迭代選擇最小值的相鄰單元來(lái)實(shí)現(xiàn)梯度下降。

由于波浪邊緣算法不會(huì)出現(xiàn)局部最小值，比勢(shì)能場(chǎng)方法具有優(yōu)勢(shì)。然而，它在計(jì)算上更復(fù)雜，并需要事先了解所有障礙的位置，是一種離線算法。

圖10中顯示了波浪邊緣算法的結(jié)果。如圖10所示，可用空間的較淺區(qū)域具有較高的勢(shì)能。黑色顯示的障礙物被認(rèn)為是無(wú)限的負(fù)勢(shì)能。起點(diǎn)以綠色顯示，終點(diǎn)以紅色顯示。在這種情況下，自由空間被離散為單元格，在梯度下降步驟中只考慮四個(gè)鄰域。

3.2.4 路線圖算法

路線圖可以通過(guò)環(huán)境空間的子集生成，它滿足三個(gè)主要規(guī)則：

（1）可以從環(huán)境空間的任何一個(gè)起始點(diǎn)到達(dá)路線圖。

（2）可以從路線圖上的任何一點(diǎn)到達(dá)路線圖上的任何其他點(diǎn)。

（3）可以從路線圖到達(dá)環(huán)境空間中的任何目標(biāo)點(diǎn)。

圖10 波浪邊緣算法規(guī)劃的路徑（Matlab運(yùn)行結(jié)果）

常用路線圖算法包括：

（1）沃羅尼圖（Voronoi圖）是與至少2個(gè)障礙物等距離的點(diǎn)的集合。

（2）可見(jiàn)性圖是通過(guò)連接每一個(gè)可以用直線連接的障礙物頂點(diǎn)而生成的。

生成路線圖后，就可以用邊和節(jié)點(diǎn)的圖來(lái)表示環(huán)境，然后可以用經(jīng)典的搜索方法來(lái)搜索，如A*、廣度優(yōu)先搜索、深度優(yōu)先搜索等。要生成路線圖，需要事先知道所有障礙物的位置。在線路線圖方法是在機(jī)器人所在環(huán)境中，基于采樣的方法建立路線圖。

廣義Voronoi圖（GVD）算法是地圖自由空間中至少與最近的兩個(gè)障礙物等距的所有點(diǎn)的集合。GVD是一個(gè)回縮，因?yàn)镚VD上的所有點(diǎn)都會(huì)被映射到自己身上，自由空間中的所有點(diǎn)都會(huì)被映射到GVD上。因此，能將自由空間平滑映射到GVD上的函數(shù)是一個(gè)變形回縮。這種表述使我們對(duì)GVD的兩個(gè)重要性質(zhì)加以利用。

（1）GVD是連通的，因?yàn)樽杂煽臻g的集合是連通的，在變形回縮下保持了連通性。

（2）一個(gè)地圖的GVD是唯一的，并且對(duì)變換和輪回不變，因?yàn)樗且粋€(gè)回縮。

GVD可以解釋為地圖結(jié)構(gòu)的拓?fù)浔硎?，它包含了地圖固有的關(guān)鍵信息，但以更緊湊的一維形式存在。生成GVD的一個(gè)簡(jiǎn)單方法是給地圖的每個(gè)網(wǎng)格qi分配一個(gè)半徑很小的圓，然后增加圓的半徑，直到它接觸到至少一個(gè)障礙物。如果只有一個(gè)接觸點(diǎn)，那么qi不屬于GVD，否則屬于GVD。GVD如圖11所示。

圖11 GVD圖算法規(guī)劃的路徑（Matlab運(yùn)行結(jié)果）

可見(jiàn)度圖算法是自由空間的另一種路線圖表示。在可見(jiàn)度圖中，所有障礙物頂點(diǎn)都是圖中的節(jié)點(diǎn)。邊緣線用來(lái)連接自由空間中彼此視線一致的節(jié)點(diǎn)?？梢?jiàn)度圖算法生成的圖具有較高的連通性。該圖可以通過(guò)以下兩個(gè)定義來(lái)修剪。

（1）支撐線與2個(gè)障礙物相切，并且障礙物都在線的同一側(cè)。

（2）分離線與2個(gè)障礙物相切，且障礙物各自在線的相對(duì)側(cè)。

支撐線和分離線是最佳方案。因此其他邊都可以去掉?？梢?jiàn)度圖規(guī)劃的路徑如圖12所示。在現(xiàn)實(shí)中，可以在所有障礙物周圍實(shí)現(xiàn)一個(gè)安全邊距，使路徑不緊密地接近障礙物，增強(qiáng)容錯(cuò)性。

圖12 可見(jiàn)度圖規(guī)劃的路徑（Matlab運(yùn)行結(jié)果）

與GVD路線圖相比，可見(jiàn)度圖的優(yōu)勢(shì)在于它的生成非常簡(jiǎn)單。然而，生成的圖一般有更多的邊和節(jié)點(diǎn)，因此搜索更耗時(shí)。另外，按照可見(jiàn)度圖生成的路徑可以保證非常接近障礙物，而且該算法要求障礙物必須用多邊形表示。

3.2.5 基于采樣的算法

在某些情況下，使用GVD或可見(jiàn)度圖生成路線圖存在太難或是導(dǎo)致圖中的節(jié)點(diǎn)和邊太多，無(wú)法實(shí)現(xiàn)有效搜索。如果有很多障礙物，或者環(huán)境空間的維度很高，就會(huì)出現(xiàn)這種情況。為了解決這些問(wèn)題，人們提出了基于采樣的算法。雖然這些算法不完整且非最優(yōu)，但其已經(jīng)被證明能夠有效地解決實(shí)際問(wèn)題。

基于采樣的算法很多，但本質(zhì)上其目標(biāo)都是通過(guò)在自由空間中隨機(jī)生成樣本來(lái)建立路線圖。一種基于采樣的算法是概率路線圖（PRM）算法。根據(jù)這個(gè)算法，整個(gè)自由空間被隨機(jī)樣本覆蓋，然后這些樣本以某種方式連接起來(lái)，生成一個(gè)路線圖。PRM算法的設(shè)計(jì)是這樣的：路線圖的構(gòu)建和操作的查詢階段是分開(kāi)的；在找到從起點(diǎn)到目標(biāo)的路徑之前，整個(gè)路線圖就已經(jīng)構(gòu)建完成。這種類型算法的關(guān)鍵是：

（1）確定隨機(jī)生成的樣本是否位于自由空間中。

（2）確定兩個(gè)節(jié)點(diǎn)之間的邊緣是否仍在自由空間中。

用PRM算法規(guī)劃的路徑如圖13所示。這種算法是概率完全的，也就是說(shuō)其朝向最優(yōu)解的方向收斂。

圖13 概率路線圖規(guī)劃的路徑（Matlab運(yùn)行結(jié)果）

其他基于采樣的方法可以在生成樣本的同時(shí)就找到了一條通往目標(biāo)的路徑，例如快速探索隨機(jī)樹(shù)（RRT）算法。RRT算法在自由空間中隨機(jī)生成新的樣本，但偏向目標(biāo)。如果沒(méi)有障礙物，則向隨機(jī)生成的點(diǎn)邁出一小步，這個(gè)過(guò)程一直持續(xù)到找到目標(biāo)。如前所述，在空間維度非常高的情況下，這些方法很適合尋找可接受的解。

3.2.6 單元分解算法

單元分解算法是指任何將配置空間分割成一組較小單元格的方法。一旦完成了分解，就可以建立一個(gè)連接圖，其中單元是節(jié)點(diǎn)，在圖中有共同邊緣的單元是連接的。這種方法對(duì)于規(guī)劃實(shí)現(xiàn)完全覆蓋的路徑非常有效，因?yàn)橐坏﹫D中的每個(gè)節(jié)點(diǎn)都被訪問(wèn)過(guò)，整個(gè)空間就會(huì)被覆蓋，但單元分解也可以用于起點(diǎn)到目標(biāo)的路徑規(guī)劃。

單元分解的形狀和樣式對(duì)規(guī)劃路徑的效果有很大影響。單元分解可以分為精確、半近似或近似。比如可以采用近似矩形分解來(lái)規(guī)劃從起點(diǎn)到目標(biāo)的路徑。這種方法的好處是內(nèi)建了避障功能，而且可以利用信息增益指標(biāo)搜索目標(biāo)。但是，它的前提是事先知道障礙物和目標(biāo)的信息。此外，連接圖的搜索可能需要很長(zhǎng)時(shí)間。

對(duì)于帶有多邊形障礙物的二維環(huán)境，可以通過(guò)檢測(cè)臨界點(diǎn)進(jìn)行單元分解，這些臨界點(diǎn)是多邊形障礙物的頂點(diǎn)，它們會(huì)導(dǎo)致自由空間的連通性發(fā)生變化。在每個(gè)臨界點(diǎn)，一個(gè)臨界片被繪制，通過(guò)臨界點(diǎn)，但不通過(guò)任何其他障礙或環(huán)境邊界，由此產(chǎn)生的自由空間的分區(qū)就是單元分解。這種方法是對(duì)梯形分解進(jìn)行改進(jìn)，它從每個(gè)障礙物頂點(diǎn)延伸出線，適用于非多邊形障礙物的環(huán)境，而且它產(chǎn)生的單元更少，使搜索更簡(jiǎn)便快速。一旦單元格分解完成，就會(huì)生成一個(gè)圖，其中每個(gè)單元格表示圖中的一個(gè)節(jié)點(diǎn)，相鄰的單元格用一條邊連接。如圖14所示，每個(gè)單元由其中心點(diǎn)代表。圖中小區(qū)的中心點(diǎn)用黑點(diǎn)表示。藍(lán)線代表臨界片。每個(gè)臨界片都與障礙物相切，但不能穿透障礙物。障礙物用紅色顯示。通過(guò)連接中心點(diǎn)從而找到的路徑顯示為黃線。由于將單元縮減到只有其中心點(diǎn)，所以會(huì)產(chǎn)生一個(gè)次優(yōu)路徑。

圖14 單元分解規(guī)劃的路徑（Matlab運(yùn)行結(jié)果）

3.2.7 搜索算法

一旦自由空間用路線圖或單元分解等技術(shù)轉(zhuǎn)化為圖形，就可以使用搜索算法來(lái)搜索圖形。下面介紹一些流行的方法。

廣度優(yōu)先搜索（BFS）是在沒(méi)有啟發(fā)的情況下，詳盡地搜索最接近的節(jié)點(diǎn)。最接近根節(jié)點(diǎn)的節(jié)點(diǎn)總是先被展開(kāi)。算法維護(hù)了兩個(gè)集合，一個(gè)開(kāi)放集和一個(gè)封閉集。封閉集包含所有已經(jīng)處理過(guò)的節(jié)點(diǎn)，開(kāi)放集包含已經(jīng)訪問(wèn)過(guò)的、等待擴(kuò)展的節(jié)點(diǎn)。當(dāng)一個(gè)節(jié)點(diǎn)被擴(kuò)展時(shí)，會(huì)考慮所有還沒(méi)有處于封閉集的鄰近節(jié)點(diǎn)。如果鄰近節(jié)點(diǎn)還沒(méi)有在開(kāi)放集中，則計(jì)算其成本，并將其加入到開(kāi)放集。除了成本之外，我們還必須跟蹤哪個(gè)節(jié)點(diǎn)是為了到達(dá)這個(gè)相鄰節(jié)點(diǎn)而展開(kāi)的。這被表示為父節(jié)點(diǎn)，在原程序中通過(guò)一個(gè)指針實(shí)現(xiàn)，它可以讓我們恢復(fù)查到的路徑。這種搜索可以保證找到最優(yōu)解，但是一般來(lái)說(shuō)，它的速度非常慢，而且只對(duì)小型查詢問(wèn)題可用。廣度優(yōu)先搜索的樹(shù)狀圖如圖15所示。BFS能找到最優(yōu)搜索，但每個(gè)節(jié)點(diǎn)都會(huì)被擴(kuò)展。

圖15 廣度優(yōu)先算法規(guī)劃的路徑（Matlab運(yùn)行結(jié)果）

A*算法是Dijkstra搜索算法的擴(kuò)展。A*通過(guò)使用距離成本進(jìn)行啟發(fā)，因?yàn)榫哂休^好的運(yùn)算速度。A*搜索的一個(gè)基本要素是定義一些啟發(fā)式成本，將每個(gè)節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)聯(lián)系起來(lái)。通常情況下，使用曼哈頓或歐幾里得距離來(lái)計(jì)算成本。每個(gè)節(jié)點(diǎn)都包含一個(gè)從開(kāi)始通過(guò)圖到達(dá)該節(jié)點(diǎn)的真實(shí)成本，用g表示，以及一個(gè)啟發(fā)式成本，代表該節(jié)點(diǎn)離目標(biāo)節(jié)點(diǎn)的距離，用h表示。所有展開(kāi)節(jié)點(diǎn)的兩個(gè)成本之和，用f=g+h表示。f值最小的節(jié)點(diǎn)被選為下一個(gè)展開(kāi)的節(jié)點(diǎn)。如上所述，一旦達(dá)到目標(biāo)，就可以按照父指針從目標(biāo)節(jié)點(diǎn)向后倒推出到起始節(jié)點(diǎn)的路徑。圖16中所示是A*搜索樹(shù)規(guī)劃的路徑?；疑倪吘壓凸?jié)點(diǎn)沒(méi)有被展開(kāi)。與BFS一樣，A*也能夠找到最優(yōu)解，然而它無(wú)需進(jìn)行窮盡搜索。

圖16 A*算法規(guī)劃的路徑（Matlab運(yùn)行結(jié)果）

3.2.8 遺傳算法

遺傳算法（GA）是受達(dá)爾文進(jìn)化論啟發(fā)衍生的算法。所有生物體都是由細(xì)胞組成的，在每個(gè)細(xì)胞中都有同一組染色體。染色體是一串DNA，是整個(gè)生物體的模型。一條染色體由基因組成，基因是DNA塊。每個(gè)基因編碼一種特定的蛋白質(zhì)。在生殖過(guò)程中，首先發(fā)生交叉或重組。來(lái)自父母的基因以某種方式形成一條全新的染色體。一套完整的遺傳物質(zhì)（所有染色體）稱為基因組。

進(jìn)化是一種解決問(wèn)題的有效方法。遺傳算法于1975年首次被提出，是一種借鑒基因的計(jì)算方法，它通過(guò)計(jì)算機(jī)實(shí)現(xiàn)進(jìn)化理論，以解決現(xiàn)實(shí)生活中的問(wèn)題。遺傳算法定義一組染色體，其中每個(gè)染色體代表搜索空間中的一個(gè)可能的解。在每次迭代過(guò)程中，根據(jù)染色體的“適合度”選擇染色體，并重組以產(chǎn)生新的后代，直到產(chǎn)生全新的一代。新一代的每個(gè)成員也可以選擇“突變”，以保持染色體的多樣性。實(shí)現(xiàn)遺傳算法的主要問(wèn)題是如何對(duì)代表潛在解決方案的染色體進(jìn)行編碼，以及如何定義“適合度”函數(shù)。

3.2.9 人工神經(jīng)網(wǎng)絡(luò)

另一種受生物啟發(fā)的路徑規(guī)劃算法是人工神經(jīng)網(wǎng)絡(luò)。受神經(jīng)元分流模型的啟發(fā)，可以構(gòu)造一種神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，其動(dòng)態(tài)神經(jīng)活動(dòng)圖代表動(dòng)態(tài)變化的工作空間。

如圖17所示，這是一個(gè)拓?fù)浣M織的神經(jīng)網(wǎng)絡(luò)，它代表一個(gè)狀態(tài)空間S。用矢量qi表示第i個(gè)神經(jīng)元在S中網(wǎng)格的位置。qi代表機(jī)器人在狀態(tài)空間中的一個(gè)狀態(tài)，每個(gè)神經(jīng)元都有與其鄰近神經(jīng)元的局部側(cè)向連接，構(gòu)成S中的一個(gè)子集，在神經(jīng)生理學(xué)中稱為第i個(gè)神經(jīng)元的接受場(chǎng)。第i個(gè)神經(jīng)元的動(dòng)態(tài)由分流方程來(lái)描述。對(duì)于S中給定的當(dāng)前狀態(tài)，用qp表示，通過(guò)查找鄰近神經(jīng)元的最大值來(lái)確定下一個(gè)狀態(tài)qn，這個(gè)過(guò)程重復(fù)執(zhí)行最終規(guī)劃起點(diǎn)至終點(diǎn)的路徑。

圖17 神經(jīng)活動(dòng)圖（Matlab運(yùn)行結(jié)果）

通過(guò)正確定義工作空間的外部輸入和內(nèi)部的神經(jīng)連接，保證目標(biāo)和障礙物分別停留在神經(jīng)網(wǎng)絡(luò)活動(dòng)圖的高峰和低谷。目標(biāo)可以通過(guò)神經(jīng)活動(dòng)在全局范圍內(nèi)傳播，吸引機(jī)器人在整個(gè)工作空間內(nèi)活動(dòng)，而障礙物只具有局部影響，從而避免局部碰撞。

4 路徑規(guī)劃案例及結(jié)果

本節(jié)簡(jiǎn)要介紹兩種路徑規(guī)劃算法的結(jié)果。

4.1 信息增益法

下面介紹一種創(chuàng)新的運(yùn)用信息論來(lái)量化機(jī)器人吸塵器的清潔效率，從而進(jìn)行路徑規(guī)劃。這種方法結(jié)合吸塵器傳感器的不確定性，比傳統(tǒng)方法更加實(shí)用、有效。對(duì)于室內(nèi)地圖每個(gè)網(wǎng)格清潔狀態(tài)離散隨機(jī)變量X，熵定義為：

交互信息定義了一個(gè)標(biāo)量，該標(biāo)量表示Z中包含的有關(guān)X的信息量，或者換句話說(shuō)，Z所提供的信息將減少X的熵。

對(duì)于吸塵器，X表示狀態(tài)向量，Z代表傳感器測(cè)量值。先驗(yàn)是尚未進(jìn)行測(cè)量的狀態(tài)，無(wú)法直接訪問(wèn)該量，因此無(wú)法直接評(píng)估相互信息。定義預(yù)期的熵減少量，通過(guò)進(jìn)行測(cè)量Z將實(shí)現(xiàn)的預(yù)期的熵減少量，從而有效規(guī)劃路徑并清潔環(huán)境。

將增益信息表述為所需行駛方向ψd的函數(shù)，從而定義信息增益目標(biāo)函數(shù)。定義一條從機(jī)器人當(dāng)前位置（x，y）開(kāi)始并在每個(gè)方向ψd上行駛固定距離r的軌跡進(jìn)行路徑規(guī)劃并評(píng)估?？梢灶A(yù)測(cè)將要進(jìn)行的測(cè)量，然后可以使用評(píng)估從沿給定軌道行進(jìn)中獲得的預(yù)期信息，并最大化信息增益[4]。

本方法通過(guò)最大化對(duì)環(huán)境的置信度來(lái)最小化熵。最終確保了整個(gè)房間的清潔效率。圖18中顯示了通過(guò)信息增益的方法進(jìn)行路徑規(guī)劃，環(huán)境中每個(gè)網(wǎng)格的清潔程度不斷提高。

圖18 信息增益路徑規(guī)劃案例及結(jié)果

4.2 單元分解法

通過(guò)將機(jī)器人自由空間細(xì)分為單元的較小區(qū)域來(lái)確定初始配置和目標(biāo)配置之間的路徑。分解之后，根據(jù)單元之間的相鄰關(guān)系構(gòu)造連接圖，其中節(jié)點(diǎn)表示自由空間中的單元，節(jié)點(diǎn)之間的鏈接表明相應(yīng)的單元彼此相鄰 。根據(jù)此連通性圖，可以通過(guò)簡(jiǎn)單地跟蹤從初始點(diǎn)到目標(biāo)點(diǎn)的相鄰空閑單元來(lái)確定連續(xù)路徑或信道。

以下是這種方法的結(jié)果。單元分解的第一步如圖19（a）所示，通過(guò)簡(jiǎn)單地從配置空間中每個(gè)內(nèi)部多邊形的每個(gè)頂點(diǎn)繪制平行線段，將多邊形在內(nèi)部和外部都受到多邊形限制的自由空間分解為梯形或三角形單元，如圖19（b）所示。然后，對(duì)每個(gè)單元進(jìn)行編號(hào)，并將其表示為連接圖中的一個(gè)節(jié)點(diǎn)。配置空間中相鄰的節(jié)點(diǎn)在連通性圖中連接。該圖中的路徑對(duì)應(yīng)于自由空間中的信道。然后，通過(guò)通道中相鄰單元格將初始配置連接到目標(biāo)配置，可以將此通道轉(zhuǎn)換為自由路徑。

圖19 單元分解法

5 結(jié)束語(yǔ)

本文以吸塵器機(jī)器人為例綜述了機(jī)器人的定位及室內(nèi)建模技術(shù)，并詳細(xì)介紹了路徑規(guī)劃的概念及算法。結(jié)合實(shí)例，根據(jù)吸塵器傳感器不確定性的特點(diǎn)，提出了基于信息理論的路徑規(guī)劃方法，給出了相應(yīng)結(jié)果。本文對(duì)機(jī)器人路徑規(guī)劃的算法及技術(shù)研究，將有助于家用機(jī)器人的科技發(fā)展。