Learning When to Quit: Meta-Reasoning for Motion Planning

作者: Yoonchang Sung, Leslie Pack Kaelbling, Tomás Lozano-Pérez · IROS 2021

授權條款

• 開放取用
• 論文: CC BY 4.0

以下內容皆依據論文全文，依其 CC BY 4.0 授權條款使用；圖表已標示作者。

一句話摘要

從過去的規劃器執行中學習何時停止隨時運動規劃器（RRT、PRM、Lazy PRM*），使路徑品質與規劃時間之間的取捨達到最大化。

為何重要

任何以 RRT 或 PRM 進行規劃的機器人都必須選定一個規劃時間預算，而固定時間或固定品質門檻不是浪費時間，就是犧牲路徑品質。此方法包覆一個未經修改的隨時規劃器，因此只要能取得來自目標環境分布的訓練問題，就能加在現有的 OMPL 式規劃器之上。

問題

隨時運動規劃器執行得越久，路徑就越短，但解的品質與計算時間之間並沒有被充分刻畫的關係，因此不清楚何時該停止規劃並開始移動。其效能曲線高度不平滑，因為當規劃器找到新的同倫類時，較短的路徑會以突然跳躍的方式出現，這排除了對未來品質做簡單線上外插的可能。

提出的方法

作者從來自同一分布的過去規劃問題的效能曲線中學習停止策略，最大化一個由使用者加權的效用 U(q, t) = wq − (1 − w)t。基於模型的變體在離散化的品質與時間上學習一個馬可夫決策過程，並以值迭代求解；兩個無模型變體（以手工設計特徵為輸入的前饋分類器，以及 RNN 序列到序列模型）模仿事後計算出的預言機（oracle）停止決策。一個 CNN 從 2D 工作範圍影像預測最佳路徑長度，讓難度不同的問題的效能曲線能夠正規化並相互比較。

關鍵見解

• 每次訓練執行的最佳停止時間都可以事後算出，這把策略學習問題轉化為監督式模仿學習，而非強化學習。
• 將路徑品質正規化需要未知的最佳路徑長度；以 CNN 從 2D 工作範圍影像預測此長度，可讓不同問題的效能曲線彼此可比，而不佳的正規化基準（從起點到目標的直線）會使效用大幅下降。
• 更豐富的歷史特徵（斜率、平坦度）讓基於模型的轉移模型準確得多，但其估計成本從數秒增加到超過一天，是維度詛咒的直接案例。
• RNN 從原始效用序列中自行學習時間特徵，在不同規劃器與效用權重下都給出最穩定的良好結果。

主要結果

• CNN 最佳路徑長度預測器在 200 個保留工作範圍上的精度：在三種環境分布中分別為 88.21%、96.23% 與 94.25%。
• 在這三種環境中，使用 CNN 正規化得到的效用為 0.58、0.65 與 0.66，相較之下，使用真實最佳長度時為 0.63、0.70 與 0.67，使用直線正規化時為 0.39、0.40 與 0.60。
• 轉移模型的保留損失從 1.84（無特徵）降至使用 (t, q) 時的 0.22 與使用 (t, q, slope) 時的 0.10，而估計時間則從 0.41 s 增加到 10.64 s 與 11,933.72 s。
• RRT* 在 w = 0.8 時：預言機效用 0.677，RNN 0.670，基於模型 0.663，分類器 0.658，而固定品質基準為 0.634，固定時間基準為 0.575。
• PRM* 在 w = 0.8 時：預言機 0.718，基於模型 0.702，RNN 0.698，分類器 0.697，固定品質 0.674，固定時間 0.662。
• 在 w = 0.2 時，固定品質基準變成負值（RRT 為 −0.283，PRM 為 −0.344，Lazy PRM* 為 −0.367），而學習方法仍維持正值。

限制

• CNN 最佳解預測器以 2D 工作範圍影像為輸入，使這些方法僅限於平面工作範圍的問題；文中建議可透過體素網格或點雲擴展到 3D，但並未實作。
• 假設新問題與訓練問題來自同一分布，且訓練需要在具代表性的問題上進行許多長時間的規劃器執行。
• 在較大規模的實驗中，為基於模型的方法加入歷史特徵在計算上不可行，因此只使用了 (q, q_prev, t)。
• 所有評估都在模擬中進行，使用 2D 工作範圍中的三自由度剛性機器人；未在實體機器人上測試。
• 只研究了線性效用 U(q, t) = wq − (1 − w)t。

對領域的影響

此論文入圍 IROS 2021 認知機器人最佳論文獎決選，被引用 14 次。論文未說明是否釋出程式碼或資料。

摘要

隨時運動規劃器在機器人領域中被廣泛使用。然而，其解的品質與計算時間之間的關係尚未被充分理解，因此何時該停止規劃並開始執行並不明確。在本文中，我們針對隨時運動規劃，探討在有限計算能力下決定何時停止思考的問題，即所謂的後設推理。我們提出資料驅動的學習方法，也就是基於模型與無模型的後設推理，它們適用於不同的環境分布，且不受所選用之隨時運動規劃器的影響。作為此框架的一部分，我們設計了一個基於卷積神經網路的最佳解預測器，可從給定的 2D 工作範圍影像預測最佳路徑長度。我們在模擬中對所提出方法的效能進行實證評估，並與基準方法比較。

連結

• arXiv 2103.04374: https://arxiv.org/abs/2103.04374
• DOI 10.1109/IROS51168.2021.9636864: https://doi.org/10.1109/IROS51168.2021.9636864
• PDF: https://arxiv.org/pdf/2103.04374v1