機器人/導航/避障

避障與碰撞檢測相比，是在檢測到可能發生碰撞後採取的行動。可能的碰撞將取決於物體和機器人的形狀和大小，以及物體和機器人的位置和運動預測。當試圖避開障礙物時，需要面對許多決定。可用的決策取決於機器人可以採取的避開障礙物的路徑。這些路徑可以由機器人意識到障礙物後決定，也可以在已知所有障礙物的位置的情況下，在載入地圖後決定。找到“正確”的路徑可能很麻煩，這取決於使用的演算法及其相關粒度。

基本思想

如果機器人的路徑上有物體，請避開它。

本質上，這是避障的基本思想。然而，對於人類來說很簡單的事情，在計算機世界中卻非常複雜。哪個演算法在避開障礙物方面最有效？哪個演算法最不復雜、最有效？哪個演算法可以有效地利用機器人的全部功能？這些都是你在尋找有效的避障演算法時應該問自己的問題。

示例演算法

檔案：Figure1.GIF

使用 Player/Stage 使用的示例演算法

在右邊的圖中，一個簡單的“坦克驅動”機器人被展示出來，它正在前往三個預先確定的路標。機器人的演算法是本節開頭給出的簡單單行程式碼的尊貴版本

1. 如果有剩餘路標，則轉向最近的路標。
   1. 如果沒有剩餘路標，則停止。
   2. 向最近的路標移動。
2. 如果有東西擋道
   1. 繞過它。
   2. 每 1.5 個車身長度後，轉到步驟 1。
3. 如果機器人到達了路標
   1. 從列表中刪除已到達的路標。
   2. 轉到步驟 1。

儘管該演算法對於一個過於簡化的地圖（其中所有障礙物都是簡單的幾何形狀）效果良好，但在更復雜的場景中，它可能無法發揮作用。例如，將路標巢狀在 U 形障礙物的中間會導致該演算法永遠不會結束。

主要問題

隨著機器人在我們日常生活中的重要性越來越大，避障（特別是處理人類安全問題）越來越受到關注也就不足為奇了。這些問題不容忽視。已經有一起與機器人相關的死亡事件。

除了安全之外，還會產生其他問題

• 避障演算法複雜性
• 計算機能力
• 感測器精度/吞吐量
• 感測器資料解釋

當然，隨著避障演算法的演算法複雜性增加，所需的計算機能力也會增加。一些研究人員甚至發現，使用多個處理器並行（並行處理）來“分而治之”這些問題是有益的。

感測器精度和吞吐量對成功避障的影響越來越小。然而，這並不意味著它不存在。在設計避障機器人的過程中，可以做出一些權衡，這可能會損害感測器在機器人行為方面的有效性。

檢測與避障

碰撞檢測只是對機器人已知區域進行調查並檢測到可能發生碰撞（或沒有發生碰撞）的行為。為了讓機器人避開碰撞，必須首先檢測到碰撞。如果沒有碰撞檢測，似乎沒有理由進行避障，因為機器人範圍內沒有任何東西需要避開。

避障是機器人採取的規避即將發生的碰撞的行動計劃。如前所述，如果沒有碰撞需要避開，就沒有必要進行避障。

避障演算法

四叉樹

使用四叉樹可以實現一個簡單的避障演算法。這裡使用的一種近似技術使用了一種名為四叉樹的資料結構。四叉樹類似於二叉樹，不同之處在於四叉樹每個父節點有四個子節點，而不是隻有兩個。

每個子節點由機器人周圍景觀的“自上而下”影像中的一個畫素方塊表示。每個方塊只是對問題“該方塊內部是否有發生碰撞的可能性？”的二進位制答案。如果答案是肯定的，則避開該方塊，否則，則記下該方塊可以安全行駛。如下面的圖所示。

檔案：Figure3.PNG

使用方塊近似三角形。

優點

使用該演算法的一個優點是，可以相當容易地進行撤退——透過向上爬樹並嘗試不同的方法。當然，在所有障礙物都已找到的情況下，可以使用簡單的距離演算法輕鬆地建立最小路徑。

缺點

使用該演算法的一個缺點是，由於每個畫素方塊的粒度，障礙物可能非常接近，以至於機器人可能不會注意到它實際上可以穿過一個間隙。

參考文獻

• Player/Stage Wiki 頁面