Time Optimal Ergodic Search
作者: Dayi Dong, Henry Berger, Ian Abraham · RSS 2023
授權條款
- 開放取用
- 論文: CC BY 4.0
以下內容皆依據論文全文，依其 CC BY 4.0 授權條款使用；圖表已標示作者。
一句話摘要
在遍歷度量上限 γ 的約束下最小化搜尋時間：一個參數決定涵蓋的徹底程度，由最佳化器挑選軌跡的時長。
為何重要
在搜救或測勘飛行中，操作者可以指定一次掃描必須多徹底，並得到符合要求的最快軌跡，而不必猜測時長。速度上限與障礙物屏障等約束都放在同一個最佳化問題中，規劃出的時間套用到實體四旋翼上時，誤差在 1.5 s 以內。
問題
遍歷搜尋所規劃的連續軌跡，會讓在每個區域停留的時間與該區域的資訊量成正比，但現有方法事先固定了規劃時域，使用者因此無法在搜尋徹底程度與時間之間取捨。同時最小化時間與遍歷度量是一個不適定問題，因為軌跡只有在時間趨近無限大時才會完全遍歷。
提出的方法
遍歷度量成為最短時間問題中的不等式約束 E ≤ γ，因此 γ 決定涵蓋要多粗或多細，而終端時間 tf 則是決策變數。作者使用「擴展遍歷狀態」，以龐特里亞金極大值原理證明局部最佳性條件，再於實務上以 N 個節點上的直接轉錄（Δt = tf/N）搭配自行開發的擴增拉格朗日求解器來求解。障礙物則以離散的控制屏障函數約束處理。
關鍵見解
- 將遍歷性視為上限而非目標，使最短時間搜尋成為適定問題；當 γ → 0 時，最佳時間會無限增長，與遍歷理論相符
- 在有四個峰值的資訊地圖上，將 γ 降低兩個數量級（從 0.1 降到 0.001），最佳時間約增加一倍（從 9.86 s 增至 19.59 s），而即使是粗略的規劃，仍然造訪了每一個峰值
- 依時間正規化的控制量在 γ 範圍的中段較高，此時軌跡必須在涵蓋與時間之間取捨，高於兩端的情況
- 平滑的初始猜測（線性內插）能得到一致的解；含雜訊或隨機的初始軌跡則會落入遍歷程度相同但時間較長的局部極小值
主要結果
- 以 2 維質點進行均勻涵蓋：改變 γ 可得到 5–10 s 的軌跡，其涵蓋效果相當於固定時域 10 s 的遍歷軌跡（E = 0.007）
- 非均勻資訊地圖：γ = 0.1 時最佳時間為 9.86 s，γ = 0.001 時為 19.59 s
- γ = 0.05 時的敏感度：將初始 tf 從 4 s 改為 8 s，最佳時間為 4.97 ± 0.23 s；將節點數 N 從 50 改為 600，最佳時間為 5.45 ± 0.39 s
- 使用控制屏障函數的雜亂 2 維環境：最佳時間從 γ = 0.2 時的 7.79 s 到 γ = 0.002 時的 11.85 s，屏障約束讓軌跡遠離每一個障礙物
- γ = 0.1、0.05 與 0.01 的無人機實驗：實際飛行時間與最佳化時間相差在 1.5 s 以內；圖 1 的軌跡在 13.5 s 內涵蓋了雜亂區域
- 求解器也為處在隨機橢球障礙物之間的非線性 3 維飛行器模型產生了均勻涵蓋軌跡
限制
- 作者表示，由於遍歷度量高度非線性且非凸，所得的解僅為局部最佳
- 作者發現龐特里亞金最佳性條件在長時域下數值不穩定，因此實際使用的求解器是一種直接轉錄方法
- 規劃為離線進行，且障礙物為已知；作者將面對未知障礙物與環境不確定性的即時規劃列為未來工作
- 結果取決於初始軌跡與 N；當 γ 非常小、所需時間變得非常大時，求解器便不再傳回解
- 作者指出運算成本會隨探索空間的維度增加
對領域的影響
榮獲 RSS 2023 最佳論文獎。作者在 github.com/ialab-yale/time_optimal_ergodic_search 釋出程式碼，並提供一個多媒體展示頁面。
摘要
能在時間與搜尋徹底程度之間取得平衡的機器人，有潛力在搜救等應用中提供分秒必爭的協助。以遍歷涵蓋為基礎的搜尋方法近來的進展，已讓機器人能在固定時間內完整探索並搜尋一個區域。然而，針對時間與自主遍歷搜尋的品質進行最佳化，至今尚未有人展示。本文探討時間最佳遍歷搜尋問題的解，以實現快速且具適應性的機器人搜尋與探索。我們將此問題表述為帶有遍歷不等式約束的最短時間問題，其上限用來調節並平衡搜尋的粒度與時間。我們利用龐特里亞金（Pontryagin）最佳性條件以解析方式給出問題的解，並透過直接轉錄最佳化方法進行數值展示。我們在模擬中，以及在雜亂環境中的無人機實驗裡，展示了此方法產生時間最佳遍歷搜尋軌跡的成效。結果顯示避障能輕易整合進我們的表述中，我們並進行消融研究，探討參數對最佳化時間的影響，以及搜尋時的軌跡敏感度。
連結
- arXiv 2305.11643: https://arxiv.org/abs/2305.11643
- PDF: https://arxiv.org/pdf/2305.11643v1
- 程式碼: https://github.com/ialab-yale/time_optimal_ergodic_search
- 專案頁面: https://sites.google.com/view/time-optimal-ergodic-search