連續空間最短路徑

Question

我需要一個最短路徑算法來控制現實生活中的機器人。

可以說我有在基質中，其中1是一個障礙，0是自由空間的形式對環境的地圖。如果我使用傳統的最短路徑算法，如A *，那麼這將給我一個曼哈頓距離最短路徑。所以沒有實際的最短路徑。這個問題出現了，因爲我想不出一種懲罰運動的方式，即對角線比兩條直線更好。我可以嘗試一種啓發式方法，使A *先嚐試歐幾里得之間的最短路徑，但實際上並沒有使歐幾里得最短路徑成爲更好的路徑。

有誰知道一種獲得連續空間最短路徑的方法嗎？它不必是實際的最佳路徑，而是比直線和90度角更好的路徑。

我有一個想法： 從起點作圓圈。 增加圓的半徑，直到圓上的一點靠近牆壁或目標。圓的邊上的所有點都被設置爲子節點，並且懲罰圓的半徑。因爲沒有理由對它們進行測試，因此圓圈內所有未開放的點將被關閉。以歐氏最短路徑作爲啓發式以A *方式重複此操作，直到達到目標狀態。使機器人從一點到另一點成直線。

這應該給我更接近我正在尋找的東西。一組不同角度的直線。當然，這將是一個連續彎曲的線條更好...

Answer 1

我實現了一個連續的空間路徑規劃算法，並在博客它here。它使用A *獲得初始估計值，並使用簡單的gradient descent算法對其進行最終確定（並針對尖銳轉彎和機器人在目的地的方位進行編程）。

比方說從A *離散路徑具有n 「航點」（座標上的網格）。只要路徑不通過阻塞的網格單元，第一個和最後一個就不能移動，但其他的可以移動。要被最小化的功能通過將航點垂直於其當前方向的參數n - 2進行參數化。