機(jī)器人吸塵器環(huán)境建模與路徑規(guī)劃研究綜述

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

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

1 引言

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

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

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

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

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

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

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

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

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

在吸塵器機(jī)器人開始任務(wù)前，必須完成環(huán)境建模。環(huán)境建模是基于工作空間地圖而實現(xiàn)的，而工作空間的地圖則是通過攝像頭、紅外傳感器或超聲波傳感器等不同傳感裝置獲得的傳感數(shù)據(jù)構(gòu)建。由于室內(nèi)掃地機(jī)器人缺少諸如GPS之類的絕對定位系統(tǒng)，因此機(jī)器人位置逐漸漂移，姿態(tài)的不確定性也越來越大。同步定位和映射（SLAM）技術(shù)的發(fā)展極大地改善了機(jī)器人的定位精度，該技術(shù)通過統(tǒng)計數(shù)據(jù)的方式來估計機(jī)器人的姿態(tài)（位置和方向）并對其進(jìn)行糾正。在智能機(jī)器人吸塵器頂部，配置一個攝像頭或激光雷達(dá)，利用SLAM技術(shù)對傳感器數(shù)據(jù)進(jìn)行處理。而SLAM算法是一種動態(tài)構(gòu)建地圖同時跟蹤自己位置的方法，該算法可以處理相機(jī)圖片或雷達(dá)數(shù)據(jù)，從中挑選出例如室內(nèi)物體的邊角等諸多環(huán)境特征。機(jī)器人記住這些特征的形狀并在移動時對其進(jìn)行跟蹤。在工作過程中，機(jī)器人將連續(xù)采集數(shù)據(jù)，檢測和跟蹤新特征，并逐步建立環(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)吸塵器沒有定位和導(dǎo)航功能，無法清理多個房間，以及充電后無法回到暫停位置繼續(xù)工作的問題。

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

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

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

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

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

2.1 濾波

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

2.1.1 貝葉斯定理

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

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

2.1.2 卡爾曼濾波（KF）

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

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

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

2.1.4 粒子濾波器

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

2.2 地圖及定位

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

圖2 地圖繪制

地圖主要有幾種：

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

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

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

基于特征的定位方法：

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

（1）控制輸入和運動模型；

（2）傳感器測量和測量模型。

機(jī)器人吸塵器的運動模型如圖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ī)器人姿態(tài)）。傳感器需要測量特征的方位、范圍及相對位置，利用擴(kuò)展卡爾曼濾波器（EKF），將不確定性測量結(jié)果與機(jī)器人姿態(tài)的當(dāng)前估計值合并。通過運動學(xué)模型實現(xiàn)機(jī)器人姿態(tài)Xt的預(yù)測更新。控制信號Ut-1是運動學(xué)模型的輸入。使用已知特征位置M和估計姿勢Xt計算預(yù)測。然后，EKF用于融合距離和方位測量值Zt，以減少姿態(tài)不確定性。EKF SLAM的定位結(jié)果如圖4所示。

圖3 機(jī)器人運動模型

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

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

3 路徑規(guī)劃

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（2）環(huán)境覆蓋：移動傳感器覆蓋環(huán)境中的每個點。

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

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

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

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

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

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

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

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

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

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

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

3.2 路徑規(guī)劃算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

用1代蟲子算法生成的路徑如圖6所示。

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

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

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

3.2.2 勢能場算法

現(xiàn)有的目標(biāo)、障礙位置等環(huán)境知識可用來定義一個勢能場。規(guī)劃路徑可以由勢能函數(shù)的負(fù)漸變生成。此方法計算簡單，因為不需要搜索確定路徑，而是自動選擇勢能場負(fù)梯度的方向。勢能場如圖8所示。圖中障礙物所在位置勢能高，目標(biāo)位置勢能低。

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

圖8 勢能場（Matlab運行結(jié)果）

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

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

勢能場算法生成的路徑如圖9所示。

圖9 勢能場算法規(guī)劃的路徑（Matlab運行結(jié)果）

3.2.3 波浪邊緣算法

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

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

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

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

3.2.4 路線圖算法

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

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

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

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

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

常用路線圖算法包括：

（1）沃羅尼圖（Voronoi圖）是與至少2個障礙物等距離的點的集合。

（2）可見性圖是通過連接每一個可以用直線連接的障礙物頂點而生成的。

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

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

（1）GVD是連通的，因為自由空間的集合是連通的，在變形回縮下保持了連通性。

（2）一個地圖的GVD是唯一的，并且對變換和輪回不變，因為它是一個回縮。

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

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

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

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

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

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

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

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

3.2.5 基于采樣的算法

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

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

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

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

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

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

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

3.2.6 單元分解算法

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

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

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

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

3.2.7 搜索算法

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

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

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

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

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

3.2.8 遺傳算法

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

進(jìn)化是一種解決問題的有效方法。遺傳算法于1975年首次被提出，是一種借鑒基因的計算方法，它通過計算機(jī)實現(xiàn)進(jìn)化理論，以解決現(xiàn)實生活中的問題。遺傳算法定義一組染色體，其中每個染色體代表搜索空間中的一個可能的解。在每次迭代過程中，根據(jù)染色體的“適合度”選擇染色體，并重組以產(chǎn)生新的后代，直到產(chǎn)生全新的一代。新一代的每個成員也可以選擇“突變”，以保持染色體的多樣性。實現(xiàn)遺傳算法的主要問題是如何對代表潛在解決方案的染色體進(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)，其動態(tài)神經(jīng)活動圖代表動態(tài)變化的工作空間。

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

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

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

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

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

4.1 信息增益法

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

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

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

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

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

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

4.2 單元分解法

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

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

圖19 單元分解法

5 結(jié)束語

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