1.簡介
autoware開源的規(guī)劃方法，稱為“OpenPlanner”formobilerobot導航，由全局路徑規(guī)劃器，行為狀態(tài)生成器和本地規(guī)劃器組成。 OpenPlanner需要一個地圖和一個目標位置來計算全局路徑并在避開障礙物的同時執(zhí)行它。它還可以觸發(fā)行為，例如在交通燈處停止。在考慮地圖中注釋的交通成本之后，全球規(guī)劃人員生成用作參考的平滑全局路徑。本地規(guī)劃者生成平滑的，障礙物 - 自由軌跡，軌跡跟蹤器使用該軌跡來實現(xiàn)低水平控制。行為狀態(tài)生成器處理諸如路徑跟蹤，對象跟蹤，避障，緊急停止，停止標志停止和交通燈行為處理等情況。 OpenPlanner使用非完整的基于Ackerman轉向的移動機器人在模擬和現(xiàn)場實驗中進行評估。模擬和現(xiàn)場實驗的結果表明，OpenPlanner可以動態(tài)生成全球和本地路徑，在高度動態(tài)的環(huán)境中平穩(wěn)導航并實時可靠地運行。
在第2節(jié)中，我們調查了相關的最新工作。在第3節(jié)中，我們提供了OpenPlanner系統(tǒng)及其體系結構的概述。在第4節(jié)中，我們詳細解釋了系統(tǒng)全局路徑規(guī)劃方法，包括矢量圖的使用和結構。第5節(jié)討論了本地規(guī)劃器，第6節(jié)介紹了行為狀態(tài)生成和狀態(tài)機的設計。在第7節(jié)中，對實驗設置進行了描述，并對實驗結果進行了定量和定性評估。我們在第8節(jié)中提出了我們的結論。在附錄A中，我們討論了當前的實現(xiàn)以及OpenPlanner可以使用的各種平臺。我們還為用戶和開發(fā)人員提供有關擴展和參展的提示。算法列于附錄B.
2.相關研究
在機器人技術中，路徑規(guī)劃的任務是找到從起始位置到目標位置的無碰撞軌跡，并確定導航?jīng)Q策。 路徑規(guī)劃已被廣泛研究，從模擬環(huán)境中的簡單碰撞避免到包括車輛約束和不確定性的高級算法。 機器人導航的路徑規(guī)劃通常涉及全局和本地計劃的計算。 全局規(guī)劃人員通過滿足最佳函數(shù)來計算從當前位置到目標位置的路徑，通常使用距離約束，如Dijkstra [11]。 任務規(guī)劃人員通過決定何時啟動，停止，創(chuàng)建新計劃，切換到緊急狀態(tài)等。
全局規(guī)劃
一些全局路徑規(guī)劃器，例如A *、Anytime動態(tài)A * 和D *算法也使用重新規(guī)劃。還有拓撲方法，例如計算無碰撞路徑的Voronoi圖。這些技術基于使用傳感器信息更新的網(wǎng)格圖，稱為成本圖。這種技術可以用于越野導航和停車場等非結構性環(huán)境。另一種類型的全球平面環(huán)境網(wǎng)絡結構化的道路延伸數(shù)公里。對于這種尺寸的地圖，成本地圖變得不切實際，需要不同的環(huán)境呈現(xiàn)方法。在2007年DARPA城市挑戰(zhàn)賽中，這些團隊獲得了完整的文件（RNDF），斯坦福大學的團隊使用動態(tài)編程技術進行全局規(guī)劃，其中包括使用加速節(jié)點進行動態(tài)編程。顯然，這種結構化的環(huán)境信息使團隊能夠規(guī)劃全球路徑，包括換道，交叉路口，停車標志，交通燈和停車場。從那時起，RNDF已成為自主導航的必要條件。在[17]中，引入了針對自動駕駛的優(yōu)化的想RNDF，并且許多公司正在研究基于RNDF的精確地圖，稱為矢量地圖。雖然這些地圖的結構類似于開放街道地圖[8]，但它們更加精確，并包含額外的，定期更新的信息。
行為狀態(tài)機
除路徑規(guī)劃任務規(guī)劃之外的另一個重要規(guī)劃功能，也稱為行為規(guī)劃，通常使用狀態(tài)機來表示任務并應用管理這些任務之間轉換的規(guī)則。 在[18]中，研究人員改變了一個連續(xù)的驅動行為，并將其轉換為離散空間，然后利用搜索算法獲得最優(yōu)任務序列，以達到符號空間中的目標條件。
本地規(guī)劃
已經(jīng)提出了幾種類型的本地規(guī)劃者。潛在的現(xiàn)場方法將排斥力分配給障礙物和對無障礙空間的吸引力[14]。其他成功的避障算法在預測車輛的未來位置時考慮車輛約束[19]。全局動態(tài)窗口方法集成了全局路徑信息，并將其用于避障[20,21]。最近開發(fā)的計劃人員將人為因素考慮在內(nèi)，因此對乘客來說是舒適的[16,22]。此外，還引入了有效的局部規(guī)劃方法，即從車輛中心和運行平行于參考路徑開始多次推出[4,23]。通過線性采樣和優(yōu)化的服務器來滿足車輛運動學要求。對象跟蹤是人工規(guī)劃方法的重要組成部分，包括我們的方法。噪聲傳感器，錯誤的檢測算法和天氣條件會導致誤報和漏報檢測。本地規(guī)劃方法必須具有可靠的對象跟蹤功能，尤其是在戶外自主導航應用中。在[24]中，多重假設跟蹤（MHT）被用于實現(xiàn)多目標跟蹤，而另外的研究者則使用了概率濾波器，例如卡爾曼或粒子濾波器。
開放源碼
比較了 Open Motion Planning Library (OMPL) [25] and Navigation Stack [c] and Open-rdc 和本文的方法
OpenPlanner不需要成本映射，除非切換到自由空間規(guī)劃器;只需要一個矢量地圖?？偟膩碚f，Open Planner更適合遵守交通規(guī)則的自主機器人導航系統(tǒng)，它只需要一個矢量地圖和目標位置來進行全局規(guī)劃，并且只需要當前位置和檢測到的障礙物進行本地規(guī)劃和行動計劃。
3.系統(tǒng)概述
它包括一個全局規(guī)劃器，它從矢量（道路網(wǎng)絡）映射生成全局參考路徑。然后，系統(tǒng)使用該全局路徑從一組采樣的展開中生成無障礙的局部軌跡。在計劃器的中心，行為生成器使用預定義的交通規(guī)則和傳感器數(shù)據(jù)作為協(xié)調器，使用碰撞和交通規(guī)則成本計算，選擇最佳軌跡，重新計劃命令和速度配置。
全局規(guī)劃概述
全局規(guī)劃器處理路徑路由。 它將矢量圖，起始位置和目標位置作為輸入，然后使用動態(tài)編程找到最短或最低成本路徑[4]。 OpenPlanner使用的全局規(guī)劃器可以支持復雜的矢量地圖，但是這項研究使用的地圖非常簡單。 Tsukuba RWRC的整個地圖如圖2所示。我們使用交通規(guī)則和功能手動注釋地圖，例如交通燈和停車線，從開始到目標。 更多細節(jié)將在第4節(jié)中提供。
行為狀態(tài)機概述
OpenPlanner的行為狀態(tài)生成模塊充當系統(tǒng)的決策者。 它是一種有限狀態(tài)機，其中每個狀態(tài)代表一種交通情況。 狀態(tài)之間的轉換由使用當前交通信息和預定義的交通規(guī)則確定。 圖3顯示了OpenPlanner系統(tǒng)中當前可用的狀態(tài)。 更多細節(jié)在第6節(jié)中提供。
軌跡生成概述
本地路徑規(guī)劃器的輸入是全局參考路徑和當前位置。 然后生成若干候選軌跡作為推出，并且本地計劃者選擇具有最低集體成本的軌道。 圖4顯示了七種可能的展開軌跡，包括中心軌跡。 我們使用了[4]中提出的斯坦福方法的修改版本。 實現(xiàn)算法將在第5節(jié)中解釋。
4.全局規(guī)劃
OpenPlanner使用矢量地圖作為全局規(guī)劃的主要輸入，計算參考路徑作為本地規(guī)劃器生成 roll-out 軌跡的參考。 在本節(jié)中，我們將詳細介紹矢量地圖和全局規(guī)劃。
矢量地圖
用于自主車輛導航的最廣泛使用的方法之一是使用矢量地圖，有時稱為高定義地圖，以將它們與地理信息系統(tǒng)（GIS）應用中使用的地圖區(qū)分開，例如開放街道地圖[8]。矢量地圖包括自主導航模塊需要了解周圍環(huán)境的數(shù)據(jù)。表1顯示了矢量圖的一些常見組件以及每個組件在自動駕駛系統(tǒng)中的潛在用途。 OpenPlanner使用2.5D映射，這意味著它包含僅在需要時使用的高程信息。這允許增加計劃性能，因為大多數(shù)計劃是在2D中完成的，但是3D信息也可以在極少數(shù)情況下使用，例如在遇到非常陡峭的斜坡時。
在矢量圖中用高階多項式的表示車道中心將有助于我們插入具有所需密度的路點，但使用多項式曲線的缺點是計算開銷。 如果從文件加載一次映射沒有問題，但如果地圖從地圖服務器更新，則可能會減慢計劃過程。 出于這個原因，我們開發(fā)了一種有效的算法來調整車道中心線的密度，如附錄B中的表6所示。由于人為錯誤，人工創(chuàng)建的地圖的中心線不平滑，因此使用共軛梯度（CG）方法進行平滑處理[27] ]被被應用。
盡管Tsukuba RWRC地圖非常簡單（圖2），正如我們的名古屋大學校園測試地圖（圖5），OpenPlanner也支持道路網(wǎng)絡兼容的矢量地圖，如圖6所示。
全局規(guī)劃
根據(jù)駕駛環(huán)境，自主車輛計劃分為兩大類。第一種類型的規(guī)劃涉及非結構化環(huán)境，例如在停車場遇到的越野駕駛員，我們無法使用矢量地圖的地方。在這些情況下，最合適的映射類型是成本映射。第二種類型的環(huán)境涉及結構化環(huán)境，其中我們有明確定義的道路，交通車道，交叉路口等，以及交通設施，所有這些都可以被描述為傳感器地圖。路徑規(guī)劃的主要目標是找到最佳的路徑起始點，但是在結構環(huán)境中我們必須遵循交通規(guī)則，例如在車道中心行駛，向正確的方向行駛，在允許的情況下改變航行，并且在正確的航線上進行右轉或右轉。當使用動態(tài)編程找到最佳路徑時，我們會追蹤從車輛當前位置到目標的可能路線。在路線追蹤過程中，我們構建了一條可能的路徑樹，這些路徑遵循現(xiàn)有規(guī)則，直到車輛到達目標，如圖7（a）所示。一旦我們到達目標，我們追蹤從目標到起始位置的路線，用本地規(guī)劃者生成局部軌跡所需的所有信息來注釋路徑，如圖7（b）所示。當?shù)匾?guī)劃人員需要了解交通方向，車道變換位置，停車位置，位置以及速度限制。為復雜矢量圖生成的樣本全局路徑如圖4和圖5所示。如圖8和9所示，后者包括換道。在圖5中，我們顯示了其中一個測試環(huán)境的全局路徑，它只是代表圖5中的如圖所示。附錄B中的表7和表8顯示了用于找到全局路徑的算法。
5.本地規(guī)劃
局部軌跡規(guī)劃器是一組生成平滑軌跡的功能，可以通過路徑跟蹤算法跟蹤，例如Pure Pursuit [28]。 對于OpenPlanner，我們采用了推出 roll-out 生成方法（圖4），其中行為生成器可以隨時要求計劃以生成新的，平滑的 roll-out 軌跡。 重新計劃將在下一小節(jié)中詳細討論。
roll-out 生成
roll-out生成需要實時執(zhí)行，因為這是所有本地規(guī)劃能夠實時工作的基本要求。因此，目標處理時間最長為0.1秒，因此控制器可以快速響應速度變化。roll-out生成算法的輸入是當前位置，規(guī)劃距離，roll-out數(shù)量和全局路徑的下一部分。輸出是n個平滑軌跡，從車輛中心向最大規(guī)劃距離延伸。
roll-out的推出分為三個部分，如圖10所示。 與車輛最接近的部分是car tip邊緣，即從機器人中心到橫向采樣點的距離，其長度決定了在軌跡之間切換時的轉向平滑度。 下一部分稱為roll-in，即從car tip邊緣到平行橫向采樣點的距離，其長度與車輛的速度成比例。車輛行駛越快，該部分應該越長，以產(chǎn)生平穩(wěn)的變化。 距離車輛最遠的部分稱為 roll-out部分，其從roll-in外部界限延伸到局部軌跡的長度的末端。 直線橫向采樣是通過從全局路徑垂直移動固定距離來執(zhí)行的，這稱為滾動密度。
roll-out的推出包括三個主要步驟，其中第一個是使用車輛的當前位置和最大規(guī)劃距離從全局路徑中提取感興趣的部分。 第二步是采樣新的垂直路徑點，這些路徑點對應于全局路徑的提取部分。 采樣從car tip邊緣開始，橫向距離為零，然后逐漸增加，以達到使用roll-out部分末端的每條軌跡計算的滾出密度。 第三步是使用共軛梯度來平滑每個采樣軌跡，這是非線性優(yōu)化技術的最小連續(xù)性，是從采樣的步驟中得出的。 這也改善了曲率，從而導致平滑轉向。
使用分段插值來調整軌跡頂點（路徑點）的密度，如附錄B中的表6所示。許多參數(shù)插值技術對輸出噪聲非常敏感并且傳播到輸出（例如，三次樣條可以導致輸出中的任意大振蕩與輸入相互串聯(lián)）[29]。 因此，我們使用分段插值和共軛梯度平滑的組合來生成更平滑的軌跡。 由此產(chǎn)生的軌跡通常在運動學上是可行的，因為我們使用矢量圖，因此我們假設所有車道都是動力學可行的。 圖11顯示了推出生成的步驟，并在附錄B的表9中說明了實現(xiàn)。
成本計算
障礙物避免過程的輸入是roll-outs軌跡和檢測到的障礙物，輸出是選定的軌跡。 我們使用附加成本函數(shù)來評估每個軌跡，計算三個不同的標準化成本測量，優(yōu)先成本，碰撞成本和過渡成本，其中最小的選擇。
使用Autoware [a]中的另一個模塊實現(xiàn)障礙物檢測，該模塊輸出兩種類型的障礙物表示，邊界框和點云數(shù)據(jù)集群。障礙物表示對于準確性和性能都是必不可少的，并且通過使用邊界框，我們可以顯著提高障礙物檢測性能，但卻犧牲了準確性。使用點云數(shù)據(jù)可以極大地提高檢測精度，但會大大降低性能。我們通過僅使用來自點云數(shù)據(jù)集群的輪廓點的樣本來解決這種權衡問題，每個障礙物最多16個點。
輪廓點的最大數(shù)量是局部規(guī)劃器的參數(shù)之一，并且通過增加該數(shù)量，我們可以實現(xiàn)更精確的表示，這導致更準確的避障。圖12示出了使用8個輪廓點的障礙物檢測的示例。輪廓表示分三個階段計算：首先，我們將xy平面劃分為n個扇區(qū);其次，我們找到每個點與中心點之間的距離和角度，并使用角度將點指定給扇區(qū);第三，我們選擇最終的輪廓點，它們是距離每個扇區(qū)中心最大距離的點。
CenterCost
中心成本限制車輛始終沿著車道的中心行駛，并且使用與該車道中心軌跡的絕對距離來計算每個roll-outs軌跡。
TransitionCost
過渡成本限制車輛跳躍，這有助于更平穩(wěn)的轉向。 使用roll-outs之間的歸一化垂直距離以及當前選擇的軌跡來計算該成本。
CollisionCost
碰撞成本分兩個階段計算，以提高性能。在第一階段，我們通過測量從障礙物輪廓點到每個生成的軌跡的距離來測試每個軌跡。由于所有的軌跡都是平行于中心的進一步切割，因此不應該特別適用于其他方面。使用“圓內(nèi)點”測試來實現(xiàn)障礙物測試，其中每個輪廓邊緣提供測試點，圓心是路點，并且每個圓的半徑是車輛寬度的一半加上誤差的檢測余量。第二階段的碰撞計算是檢查檢測到的障礙物與 roll-in 滾入限制之后產(chǎn)生的軌跡之間的距離。在滾入限制之后，所有生成的軌跡都是平行的，因此我們不需要將預測的碰撞成本與預測相對應。我們計算從檢測到的障礙物的輪廓點到中心軌跡的距離，然后使用從每個軌跡到中心軌跡的有符號距離來找到碰撞的前期軌跡。圖13顯示了彩色編碼的中心成本。圖14示出了在存在障礙物時歸一化的總成本。
6.行為狀態(tài)機
在交通路燈處停車，決定改變車道，停車并在停車標志處等待并屈服于行人的情況很難通過一種算法來處理。 與其他交通規(guī)則一樣，這些事件本質上是明確的，但規(guī)則因國家而異。 此外，可以隨時添加或禁用特殊的交通規(guī)則或目標。 在本研究中，我們使用術語“行為狀態(tài)”來表示所有這些事件響應，以及引用這些狀態(tài)之間的轉換規(guī)則。 圖3顯示了在Tsukuba Real World Robot Challenge期間用于OpenPlanner的行為狀態(tài)。 表2顯示了每個狀態(tài)的轉換規(guī)則。
控制狀態(tài)之間的轉換有幾個參數(shù)。每次迭代都確定性地計算這些參數(shù)。從理論上講，概率方法應該可以實現(xiàn)更平滑的轉換，但是在廣泛的應用程序中實現(xiàn)和維護它會更慢，更復雜。該問題的一個解決方案是引入定時器和計數(shù)器。例如，當障礙物移動到非常接近閾值時，行為發(fā)生器將在Swerve和Follow狀態(tài)之間快速來回切換。計數(shù)器或計時器可以打破這個循環(huán)。計數(shù)器將產(chǎn)生更好結果的另一種情況是當交通信號燈變?yōu)榧t色或綠色并且光檢測器不足以處理變化時。在這種情況下，需要多次接收信號以確保信號的可靠性并切換到下一狀態(tài)。因此，在每個行為的初始化過程中，只有最小的過渡時間，這樣一個國家將繼續(xù)自我執(zhí)行，除非在相應的時間條件下達到最佳狀態(tài)。
7.實驗
實驗平臺如圖16所示，在[30]中使用相同的平臺。 它是一種改裝的移動踏板車，因此可以通過計算機進行控制。 它包括一個HDL32 Velodyne LIDAR傳感器，用于定位和對象檢測。 除了3DLIDAR之外，我們使用三個2D LIDAR進行路緣和近障礙探測。 在軟件部分，我們有多個ROS節(jié)點用于本地化，障礙物檢測，控制，全局規(guī)劃，本地規(guī)劃和路徑跟蹤。 在附錄A中，我們提供了有關ROS用戶的OpenPlanner的技術信息。 表3顯示了使用的參數(shù)配置模擬和現(xiàn)場實驗。
