機器人/導航/軌跡規劃

軌跡規劃

軌跡規劃是指在一段時間內從點 A 移動到點 B 同時避免碰撞。這可以用離散和連續方法計算。軌跡規劃是機器人領域的一個主要領域，因為它為自動駕駛車輛鋪平了道路。

軌跡規劃有時被稱為運動規劃，錯誤地被稱為路徑規劃。軌跡規劃不同於路徑規劃，因為它是由時間引數化的。本質上，軌跡規劃包含路徑規劃，以及根據速度、時間和運動學規劃如何移動。

問題約束

完整約束

完整約束是機器人可控自由度與機器人總自由度之間的關係。如果可控自由度的數量大於或等於機器人的總自由度，則該機器人被稱為完整約束的。使用完整約束的機器人，許多移動更容易，返回到過去的姿態也更容易。

汽車是非完整約束的，因為它沒有辦法橫向移動。這使得某些運動，如平行泊車，變得困難。完整約束車輛的例子是使用麥克納姆輪的車輛，例如新的 Segway RMP。

動態環境

在動態環境中，例如現實世界中，許多可能的碰撞物體並非靜止的。這使得軌跡規劃更加困難，因為時間在不斷變化，物體也在移動。機器人不能簡單地倒退回時間，因為它可能只是從靜止的碰撞中退回。除此之外，由於地形，許多選擇是完全不可逆的，例如從懸崖上掉下來。

概念

軌跡規劃的概念

軌跡規劃給出一個從起始配置 S 到目標配置 G 的路徑，在 2D 或 3D 空間中避免碰撞。

配置是描述機器人位置的姿態。配置空間 C 是所有配置的集合。例如，在二維空間中，機器人的配置將由座標 (x, y) 和角度 θ 描述。而在三維空間中，機器人的配置將由座標 (x, y, z) 和角度 (α, β, γ) 描述。

自由空間 C_free 是所有無碰撞配置的集合。計算 C_free 的形狀效率不高，但是，計算給定配置是否無碰撞，只需使用來自感測器的運動學和碰撞檢測即可。

目標空間是自由空間的線性子空間，我們希望機器人到達那裡。在全域性運動規劃中，目標空間可以透過機器人的感測器觀察到。然而，在區域性運動規劃中，機器人無法在某些狀態下觀察目標空間。為了解決這個問題，機器人假設了幾個位於可觀察區域（機器人周圍）的虛擬目標空間。虛擬目標空間被稱為子目標。

規劃演算法

人工勢場

人工勢場的例子

人工勢場規劃在對映上放置值，目標具有最低（最高）值，根據距離目標的距離增加（下降）值。障礙物被定義為具有極高（低）值。然後機器人只需移動到與其相鄰的最低（最高）勢值，這應該會引導它到達目標。然而，這種技術經常陷入區域性最小值。可以使用某些技術來避免這種情況，例如波前勢場規劃。人工勢場可以透過類似於靜電勢場的直接方程來實現，也可以透過一組語言規則來驅動。

基於取樣的規劃

路徑圖方法是一種基於取樣的規劃方法。首先，在 C 中對 N 個配置進行取樣作為里程碑。然後，在所有里程碑之間形成一條直線 PQ，只要直線 PQ 完全位於 C_free 中。然後可以使用圖搜尋演算法來找到從起點到目標的路徑。隨著 N 的增長，可以找到更好的解決方案，但這也增加了計算時間。

基於網格的規劃

基於網格的規劃的例子

基於網格的規劃在對映上覆蓋一個網格。然後，每個配置都對應一個網格畫素。機器人可以從一個網格畫素移動到任何相鄰的網格畫素，只要該網格畫素位於 C_free 中。然後可以使用 A* 等搜尋演算法來找到從起點到目標的路徑。這種方法的一個潛在權衡是，使用較低解析度的網格（更大的畫素），搜尋速度會更快，但是它可能會錯過 C_free 中狹窄空間的路徑。此外，隨著網格解析度的增加，記憶體使用量呈指數級增長，因此，在較大的區域中，可能需要使用其他路徑規劃演算法。

基於獎勵的規劃

基於獎勵的演算法假設機器人處於每個狀態（位置和內部狀態包括方向）都可以選擇不同的動作（運動）。然而，每個動作的結果並不確定。換句話說，結果（位移）部分是隨機的，部分是機器人控制的。當機器人到達目標時，它會獲得正獎勵；如果與障礙物發生碰撞，它會獲得負獎勵。這些演算法試圖找到一條路徑，最大化累積的未來獎勵。 馬爾可夫決策過程 (MDP) 是一種流行的數學框架，它被用於許多基於獎勵的演算法中。MDP 相對於其他基於獎勵的演算法的優勢在於它會生成最佳路徑。MDP 的缺點是它限制了機器人從有限的動作集中進行選擇；因此，路徑並不平滑（類似於基於網格的方法）。模糊馬爾可夫決策過程 (FDMP) 是 MDP 的擴充套件，它使用模糊推理系統 生成平滑路徑。