2000年一篇論文 Coverage of Known Spaces: The Boustrophedon Cellular Decomposition 橫空出世，解決了很多計算機和機器人領域的覆蓋路徑問題，今天我來詳細解讀這個算法。

The Boustrophedon Cellular Decomposition 算法詳解

這篇論文標題為"Coverage Path Planning: The Boustrophedon Cellular Decomposition",是由Howie Choset和Philippe Pignon發表。
Abstract
Coverage path planning is the determination of a path that a robot must take in order to pass over each point in an environment. Applications include vacuuming, floor scrubbing, and inspection. We developed the boustrophedon cellular decomposition, which is an exact cellular decomposition approach, for the purposes of coverage. Each cell in the boustrophedon is covered with simple back and forth motions. Once each cell is covered, then the entire environment is covered. Therefore, coverage is reduced to finding an exhaustive path through a graph which represents the adjacency relationships of the cells in the boustrophedon decomposition. This approach is provably complete and Experiments on a mobile robot validate this approach.

1 引言
覆蓋路徑規劃確定了一條路徑,保證了代理(agent)會經過給定環境中的每一個點。這個過程有多種應用。海軍應用包括水雷反制任務和大陸架海洋測繪。商業應用包括污染清理、地板清潔、農作物犁地和橋梁檢查。沒有覆蓋算法,這些應用就無法處理。目前大多數覆蓋路徑規劃器充其量只是初級的,因為它們基于啟發式方法。在掃雷中使用這種方法,就像用有故障的探雷器進行掃雷一樣。因此,本文描述的覆蓋路徑規劃算法是完備的;也就是說,在有限時間內,它將找到一條覆蓋路徑或確定不存在這樣的路徑。

我們的方法利用了一種稱為精確Cell分解的幾何結構,它是組成目標環境的非相交區域的并集。每個區域稱為一個單元格,單元格的并集填充了整個環境。在每個單元格中,覆蓋路徑都可以很容易地確定,例如簡單的來回運動;因此覆蓋路徑規劃簡化為規劃從一個單元格到另一個單元格的運動。本文將開發一種新的Cell分解方法,稱為Boustrophedon分解,并將其應用于覆蓋路徑規劃。

Boustrophedon這個詞在1699年首次在英語中使用,字面意思是"牛的方式"。通常,當牛在田地里拖犁時,它會沿著一條直線穿過整個田地,然后轉身,沿著與前一條路徑相鄰的新直線路徑前進。通過重復這個過程,牛保證覆蓋(從而犁)整個田地。見圖1。

Boustrophedon Cell分解是一種新型的分解方法,其中機器人的自由空間被分解成單元格,使得機器人可以用來回的 boustrophedic 運動覆蓋每個單元格。一旦機器人覆蓋了每個單元格,它就覆蓋了環境中的整個自由區域。這種方法已經通過仿真和 Nomadic 200 移動機器人基座進行了驗證。

2 背景工作
2.1 覆蓋的現有工作
覆蓋的早期工作包括真空吸塵和地板清潔等應用。在這些方法中,必須將路徑顯式地編程到機器人中;也就是說,它們不使用算法來生成覆蓋路徑,而是"手工"規定一條路徑。此外,這些算法依賴于部署在環境中的地標。

一些現代農業作業代表了覆蓋路徑易于自動生成的重要機會。Demeter項目用于收割大型農田;在這種方法中,機器人只是使用視覺來引導其路徑,沿著先前割下的作物線,只能覆蓋矩形田地。

考慮了非完整約束的地板覆蓋方法。在這項工作中,一組模板用于僅覆蓋沒有障礙物的有界區域。這些模板用于適應機器人的非完整約束,因此可能有助于規劃每個單元格內的來回運動。然而,其局限性在于它不能在存在障礙物時規劃路徑。

Zelinsky等人的覆蓋算法非常適合非結構化環境。盡管它是完備的,但它在離散環境中實現了地板覆蓋(即它是分辨率完備的)。Kurabayashi等人提出了一種類似的方法,沒有證明,采用了合作機器人。最后,Lumelsky等人提出了一種與平面情況下提出的方法類似的算法。盡管提出的算法在平面情況下產生了與Lumelsky小組幾乎相同的路徑,但本文中描述的方法更易于實現,因為它只有兩種情況,而他們的方法包含一系列特殊情況。最后,Hert等人的方法不是完備的。Hert等人提供的算法的主要貢獻是它是增量的,因此可能導致在移動機器人上的基于傳感器的實現。

2.2 精確Cell分解
本文中使用的覆蓋方法是對現有完備運動規劃方案的改編,稱為精確Cell分解。Cell分解是一種運動規劃技術,其中自由配置空間(機器人不與障礙物重疊的所有機器人配置的集合)被分解成單元格,使得單元格的并集是原始自由空間。每個單元格可以表示為圖中的一個節點,相鄰單元格在它們對應的節點之間有一條邊。這個圖稱為鄰接圖。如果機器人可以覆蓋每個單元格,那么地板覆蓋問題就簡化為確定訪問每個節點至少一次的鄰接圖遍歷,即旅行商問題,對于旅行商問題總是存在解(可能是次優的)。

一種流行的Cell分解技術是梯形分解(也稱為條帶法),它可以產生完備的覆蓋路徑解。在梯形分解中,機器人的自由空間被分解成梯形單元格。由于每個單元格都是梯形,因此可以通過簡單的來回運動輕松實現每個單元格的覆蓋(見圖1)。通過訪問鄰接圖中的每個單元格來實現對環境的覆蓋。

梯形分解方法假設一條垂直線段(稱為slice)從左到右掃過由多邊形障礙物填充的有界環境。單元格是通過一系列打開和關閉操作形成的,當slice遇到一個事件時,事件是slice與多邊形頂點相交的實例。有三種類型的事件:IN、OUT和MIDDLE。粗略地說,在IN事件中,當前單元格關閉(從而完成其構造),兩個新單元格打開(從而啟動其構造)(圖2)。OUT事件正好相反:兩個單元格關閉,一個新單元格打開(圖3)。IN事件可以看作是一個單元格分解成兩個單元格,而OUT事件是兩個單元格合并成一個單元格。在MIDDLE事件中,當前單元格關閉,一個新單元格形成。這些操作的結果是自由空間被分解成梯形單元格。

VanderHeide和Rao的地形覆蓋系統基于對由一個或兩個分離良好的障礙物填充的平面環境進行梯形分解。這個系統的優點是它是基于傳感器的。

不幸的是,梯形方法需要太多冗余的來回運動來保證完備性。在圖4的左側,機器人需要進行一次額外的縱向運動來覆蓋梯形單元格的剩余部分。這可以看作是保證機器人窮盡地覆蓋整個環境的代價的一部分。梯形方法的另一個缺點是它要求環境是多邊形的。

3 貢獻
本文介紹的Boustrophedon Cell分解是對梯形分解的增強,旨在最小化前一段中描述的多余縱向運動的數量。本質上,IN和OUT事件之間的所有單元格都合并成一個單元格。比較圖5中的梯形分解和圖6中的Boustrophedon分解。請注意,Boustrophedon分解的單元格數量更少。

擁有更少單元格的優勢在于可以最小化來回運動的boustrophedon運動的數量。例如,考慮兩個相鄰的梯形單元格,它們的寬度分別是機器人寬度的兩倍半。為了覆蓋每個梯形,機器人必須進行三次通過,總共六次縱向運動。使用Boustrophedon分解方法,這兩個單元格合并成一個單調多邊形單元格,需要五次通過才能覆蓋(圖4)。

該方法不是利用多邊形的結構來確定IN和OUT事件,而是依靠切片連通性的變化來確定事件的存在。通常,這被稱為關鍵點,關鍵點用于路線圖運動規劃技術,如Canny和Lin的"機會主義路徑規劃器"(OPP),它本身基于Canny的路線圖算法。現在,機器人可以在曲線甚至采樣環境中執行覆蓋(圖7)。

4 算法概述
Boustrophedon Cell分解方法與梯形分解方法相似。同樣,一個切片從左到右掃過一個由多邊形障礙物填充的有界平面環境。就像梯形分解一樣,在IN事件中,切片連通性增加,當前單元格關閉,兩個新單元格打開(圖8)。相反,在OUT事件中,切片連通性減少,兩個當前單元格關閉,一個新單元格打開(圖9)。

梯形分解和Boustrophedon分解方法之間的區別在于中間事件:在MIDDLE事件中,不打開也不關閉單元格,而是簡單地更新當前單元格。本質上,當切片的連通性發生變化時,單元格打開和關閉(圖6)。

在分解計算的同時,鄰接圖也被確定。同樣,每個單元格是圖中的一個節點,相鄰單元格的節點之間有一條邊。類似深度優先的圖搜索算法輸出一個路徑列表,表示對鄰接圖的窮舉遍歷。遍歷路徑列表構成了對鄰接圖的窮舉遍歷。

最后,使用上述路徑列表計算機器人實際走的路徑。當機器人進入一個"未清潔"的單元格時,規劃Boustrophedic運動,然后規劃到路徑列表中下一個單元格的路徑。當機器人進入一個"已清潔"的單元格時,它只是規劃一條穿過該單元格到路徑列表中下一個單元格的路徑。重復這兩個動作,直到到達路徑列表的末尾,即直到每個單元格都被清潔。

5 算法細節
本節包含在已知多邊形環境中實現Boustrophedon分解的細節。目前的工作包括使用傳感器在曲線環境中實現該算法。通過將障礙物放大機器人的半徑(機器人是圓形的)來計算配置空間障礙物。由此產生的廣義多邊形(線段和圓弧序列)然后被多邊形近似。

5.1 事件
在我們對Boustrophedon分解方法的實現中,我們用另外兩種類型的事件取代了中間事件:FLOOR和CEILING。FLOOR事件對應于多邊形障礙物頂部的頂點,CEILING事件對應于障礙物底部的頂點。這樣,FLOOR和CEILING事件分別對應于正在逐步生成的單元格的floor和ceiling(圖10)。

該算法的輸入是一個多邊形列表,其頂點按逆時針順序列出。該算法首先從多邊形列表創建一個事件列表。多邊形沒有特定的順序,但在我們的實現中,我們做了一個通用假設,即沒有兩個IN事件或兩個OUT事件具有相同的x坐標。

回想一下,事件是多邊形的一個頂點和一些附加信息;具體來說,event結構包含事件的位置、類型和指向與之關聯的邊(或多條邊)的指針。event結構最多有兩種類型的邊指針:floor指針和ceiling指針。IN事件的ceiling指針指向從事件發出的下一條邊,floor指針指向在事件終止的前一條邊(圖11)。相反,OUT事件的floor指針指向從它發出的下一條邊,ceiling指針指向在事件終止的邊。CEILING事件只有一個ceiling指針,指向從事件發出的邊;FLOOR事件只有一個floor指針,指向在事件終止的邊。

在考慮特定多邊形時,算法首先找到多邊形的IN事件。算法遍歷多邊形的頂點列表,直到遇到最左邊的頂點。這個頂點及其相關信息被插入到事件列表中。由于頂點是以逆時針方式排序的,下一個頂點序列是CEILING事件。回想一下,雖然這些頂點對應于多邊形的下側,但它們是CEILING事件,因為它們對應于緊接在多邊形下方的單元格的ceiling。

算法遍歷多邊形列表,插入每個頂點作為CEILING事件,直到算法遇到最右邊的頂點。這個頂點及其相關信息被插入到事件列表中作為OUT頂點。剩下的頂點對應于FLOOR事件。

當遇到事件時,將它們插入到按事件的x坐標排序的有序事件列表中。插入過程是O(n log n),其中n是多邊形環境中的總邊數(或頂點數)。

5.2 單元格
單元格可以用兩個列表表示:一個floor邊列表和一個ceiling邊列表,它們都界定單元格。因此,cell結構包含兩個指向邊列表的指針:一個floor指針和一個ceiling指針。cell結構還包含一個指向相鄰單元格的鏈表。最后,cell結構有兩個標志:visited和cleaned,它們在算法的后面使用。

Boustrophedon分解的單元格是以增量方式通過掃描線方法計算的。掃描環境類似于按順序訪問事件列表中的每個事件,因為事件列表已經排序。

第一個單元格是最左邊的單元格。在我們的實現中,假設在實際掃描過程開始之前(即,掃描從最左邊的IN事件左邊開始),最左邊的單元格被人為地打開。還假設環境的上方由一條邊界,下方由一條邊界。因此,第一個單元格的floor和ceiling指針指向這些邊界邊。

第一個真正的事件是IN事件。在IN事件處,確定切片與當前單元格的floor的交點和切片與當前單元格的ceiling的交點。用f和c表示這些點(圖8)。通常,當前單元格的floor和ceiling有多條邊,因此交點f和c是當前單元格最后一條floor邊和ceiling邊的端點。現在,確定了當前單元格的所有floor段和ceiling段,該單元格被認為是關閉的。

接下來,要打開兩個新單元格:底部單元格和頂部單元格。底部單元格的floor中第一條邊的起點是點f,底部單元格的ceiling中第一條邊的起點是事件。底部單元格的floor指針設置為先前關閉的單元格的floor指針,底部單元格的ceiling指針設置為打開事件的ceiling指針。相反,對于頂部單元格,floor中第一條邊的起點是事件,而ceiling中第一條邊的起點是點c。在這里,新的floor指針設置為事件的floor指針,新的ceiling指針設置為先前關閉的單元格的ceiling指針。

當遇到FLOOR事件時,更新當前單元格的floor指針。具體來說,與事件相關的floor邊被添加到當前單元格的floor邊列表中。類似地,當遇到CEILING事件時,與事件相關的ceiling邊被添加到ceiling邊列表中。

最后,當遇到OUT事件時,兩個單元格關閉,一個新單元格打開。再次,讓底部單元格和頂部單元格表示在OUT事件處關閉的兩個單元格,新單元格表示在IN事件處打開的單元格。設f為當前切片與底部單元格的floor列表中當前邊的交點,c為當前切片與頂部單元格的ceiling列表中當前邊的交點。點f是底部單元格的floor列表中最后一段的端點,事件位置是底部單元格的ceiling列表中最后一段的端點。同樣,事件位置是頂部單元格的floor列表中最后一段的端點,c是頂部單元格的ceiling列表中最后一段的端點。一旦確定了底部和頂部單元格的所有floor段和ceiling段,底部和頂部單元格就關閉了(圖9)。

接下來,要打開一個新單元格。第一條floor段的起點是f,第一條ceiling段的起點是c。新單元格的floor指針設置為前一個底部單元格的floor指針,新單元格的ceiling指針設置為前一個頂部單元格的ceiling指針。

單元格鄰接列表也是增量構建的。回想一下,每個單元格都有一個指向相鄰單元格列表的指針,該指針在IN和OUT事件中更新。目標是將相鄰單元格插入到鄰接列表中,使得相鄰單元格圍繞當前單元格按逆時針順序排列。在IN事件處,當前單元格被分成兩個新單元格:底部和頂部。首先,頂部單元格的指針被插入到當前單元格的鄰接列表的前面,然后底部單元格的指針被插入到新鄰接列表的前面。結果是

neighbor_list = bottom -> top -> old_neighbor_list

在OUT事件處,底部和頂部單元格合并成一個新單元格。首先,頂部單元格的指針被插入到新單元格的鄰接列表的末尾,然后底部單元格的指針被插入到鄰接列表的末尾。結果是

neighbor_list = old_neighbor_list -> top -> bottom

這個過程產生了一個鄰接列表,其元素是相鄰單元格,從當前或新單元格的右下方開始,按逆時針方向排列。

在訪問了事件列表中的所有事件后,所有單元格及其鄰接關系都被計算出來;實際上,Boustrophedon分解及其鄰接圖已經確定。

5.3 覆蓋
有了分解和鄰接圖,機器人現在可以規劃一條覆蓋環境的路徑。這分兩步完成:在鄰接圖中找到一條訪問每個節點的路徑,然后在每個單元格(即節點)內計算顯式的機器人運動。

在通用圖中確定訪問每個節點的最優路徑是經典的旅行商問題,這是一個NP完全問題。使用類似深度優先搜索的算法計算路徑列表,路徑列表表示對鄰接圖的窮舉遍歷。

1. 從分解中的任意單元格開始。將其插入路徑列表。將其標記為已訪問。
2. 轉到當前單元格的鄰接列表中第一個未訪問的單元格(即,轉到第一個逆時針未訪問的單元格)。將此單元格插入路徑列表的開頭,并將其標記為已訪問。
3. 重復此過程(即,轉到步驟2),直到遇到所有鄰居都已訪問的單元格。
4. 在這一點上,回溯,直到遇到具有未訪問鄰居的單元格。通過向前遍歷路徑列表來實現此回溯,將訪問的每個元素插入路徑列表的前面,直到遇到具有未訪問鄰居的元素。將此元素插入路徑列表的前面,然后重復上述過程(即,轉到步驟2)。
5. 如果在回溯過程中沒有找到具有未訪問鄰居的單元格,則鄰接圖中的所有單元格都已被訪問。

使用路徑列表,機器人的運動是通過兩步過程計算的。首先,如果單元格未被清潔,則將該單元格標記為已清潔,并為該單元格計算實際的Boustrophedon(來回)運動。通常,Boustrophedon運動的步長(即兩條平行線段之間的距離)大約是機器人的寬度。其次,確定到路徑列表中下一個單元格的路徑。如果單元格已經被清潔,則規劃到路徑列表中下一個單元格的路徑。

6 仿真和實驗
圖12包含兩個障礙物的地板平面圖。圖13和14包含地板覆蓋算法的中間結果。在圖13中,兩個單元格已經被覆蓋,在圖14中,除兩個單元格外,所有單元格都被覆蓋。最終的覆蓋結果可以在圖15中看到。

從圖15可以看出,這種方法在障礙物邊緣與Boustrophedon來回路徑形成銳角時存在一些問題。為了部分緩解這個問題,當機器人穿過已清潔的單元格時,它靠近障礙物的邊界行進。未來的實現將包括一個額外的通道,其中每個障礙物都被特別環繞。對于真空吸塵等應用,這種額外的方法是合理的,因為大多數真空吸塵應用在環境邊界附近需要不同的吸塵機制。

該算法還在鋪有地毯的環境中的Nomadic Technologies移動機器人基座上運行,環境中有紙板障礙物,由上述仿真表示。該實現在小環境中有效,但在較大的環境中存在一些航位推算問題。特別是,并非所有線條都完全平行。這種方法可以從Demeter項目中使用的基于視覺的技術中受益。此外,我們的實驗表明,這種方法對初始條件極其敏感,因此未來的工作必須使這個過程對初始條件的微小變化具有魯棒性。

7 結論和未來工作
本文描述了一種新型的地板覆蓋算法,該算法是完備的。也就是說,從理論上講,機器人保證遵循一條路徑,使得機器人經過環境中的每個點。該算法基于一種稱為Boustrophedon Cell分解的新型精確Cell分解方法。Boustrophedon的意思是"牛的方式";Boustrophedon運動是來回牛樣的運動。機器人可以很容易地在Boustrophedon分解的每個單元格中規劃Boustrophedon運動。一旦每個單元格被覆蓋,整個環境就被覆蓋了。

移動機器人上的實驗結果驗證了這種方法,并指出了未來工作的一些途徑。由于側向步長的離散化,這種方法有時會跳過障礙物邊界附近的環境部分。如果機器人的側向步長較短,則這些未覆蓋的區域會減少。這里有一個時間/覆蓋的權衡。盡管如此,在主要覆蓋完成后,一個簡單的障礙物跟隨算法將緩解這個問題。這樣的解決方案與正常的真空吸塵一致,其中地板靠近墻壁的部分需要用真空吸塵器額外通過一遍。

近期研究還包括通過允許定義更大(因此更少)的單元格來改進Boustrophedon Cell分解。例如,在圖6中,底部的三個單元格可以合并成一個單元格,其中可以規劃Boustrophedon運動。此外,由于單元格在掃描線的連通性發生變化時打開或關閉,因此該算法可以很容易地修改為具有曲線障礙物的環境。

此外,還需要考慮優化問題。第一個問題涉及開發度量標準,用于評估鄰接圖的啟發式圖搜索。這些度量包括:路徑長度、重新覆蓋的地板空間面積、時間等。另一個優化問題涉及確定掃描線的角度;某些環境可能更適合水平掃描線。

另一個問題涉及材料去除。在真空吸塵器的情況下,這一點并不重要。然而,在除雪的情況下,除雪機器人可能必須規劃最佳路徑,將雪轉移到覆蓋現場。這暗示了使用多個機器人:一個機器人從地面上清除雪,另一個機器人將雪轉移到中央傾倒區。

這項工作的長期目標是基于傳感器的地板覆蓋,即僅從視線傳感器信息確定覆蓋路徑。即使機器人可以獲得世界的全部知識,基于傳感器的地板覆蓋也是有用的,但輸入機器人太麻煩了。例如,如果每個用戶都必須將房屋CAD模型(如果存在)編程到機器人中,自動真空吸塵器就不會成為一個有市場的產品。基于傳感器的方法將基于Rimon和Canny的路線圖工作,該工作使用關鍵點來保證路線圖的連通性。