A *方位離散化

Question

我有一個障礙空間，我希望找到一條通路。我能做的就是將空間離散成網格，並使用A *（或D *或其他）來查找通過它的路徑。我希望現在給算法添加方向。所以節點位置現在變成了一個3d向量（x，y，phi）。只有屬於一個圓弧（兩個位置都在圓上並且沿着切線方向），纔可以從一個節點轉到另一個節點。我如何離散化空間，使角度不會爆炸，通過遍歷圖表，這組可能的角度變得有限？ 謝謝。

Answer 1

通過確保phi被認爲是模2π，即對於任何k的整數值，phi = phi + 2pi * k，可以防止角度炸燬。

在C語言中，你可能最終用fmod更新phi。

phi = fmod(phi + deltaphi, 2*pi) 

其中deltaphi是你引入的角度變化（弧度）。

實現此目的的最常見方法是將角度phi的值限制爲採用其中一個離散角度，這也具有避免精度/舍入問題的優點。由於您知道phi只能採用n值之一，因此您可以將其視爲整數，並在必要時將值映射爲實數。

i = (i + deltai) % n 
phi = (2*i*pi)/n) 

在角度deltai變化爲（2 * deltai *π）/ n弧度的地方。

但是，找到一個好的離散化只是解決方案的一部分 - 它定義了一個配置空間的表示，但正如您已經指出的那樣，您還需要考慮什麼是有效的轉換。

將角度整合到規劃中最簡單的方法是要求旋轉和平移是截然不同的（在任何時候你可以做一個或另一個，但不能同時做），或者是可組合的（總是翻譯，然後到達瞬間旋轉）。

在你轉彎的同時向前和向後移動介紹更加複雜，並且對於離散格子往往不能很好地工作 - 它往往需要你正在使用的車輛模型。最常見的是簡單的非完整模型 - 只有前進的車（Dubins的車）或前進/後退的車（Reeds Shepp車） - 你對圓的切線的參考，我猜這就是你所要的後。 Dubins-Curves或類似的庫可以用來構建可以與A *（或D *）規劃器組合的可能路徑的庫。

Differentially Constrained Mobile Robot Motion Planning in State Lattices作者：Mihail Pivtoraiko，Ross A. Knepper和Alonzo Kelly有一些可能的驚人圖像。

Answer 2

據我所知，你的挑戰不是離散座標，而是離散標題。我必須在網格世界中做同樣的事情，允許在八個方向上移動，即水平，垂直和對角線。 您的離散空間應與問題域匹配。供大家參考：

• 4方向：採用正方形格子跨越邊緣運動
• 8方向跨越邊緣和頂點
• 6-使用正方形格子運動方向使用六邊形網格，邊界移動
• 12方向使用帶有moveme的六角形網格nt跨邊緣和點
• ...等等。

真正得到離散標題，我宣佈一個enum稱爲Direction：

public enum Direction { 
    North, 
    NorthEast, 
    East, 
    SouthEast, 
    South, 
    SouthWest, 
    West, 
    NorthWest; 

//additional code below... 
} 

可以通過先查找正確的航向的當前位置和目標位置之間計算的XY偏移：

int dx = currentPosition.x - goalPosition.x; 
int dy = currentPosition.y - goalPosition.y; 

這些被傳遞到getInstance(int,int)方法（下面）以獲得正確的Direction：

public static Direction getInstance(int dx, int dy) { 
    int count = Direction.values().length; 
    double rad = Math.atan2(dy, dx); // In radians 
    double degree = rad * (180/Math.PI) + 450; 

    return getInstance(((int) Math.round(((degree % 360)/(360/count)))) % count); 
} 

public static Direction getInstance(int i) { 
    return Direction.values()[i % Direction.count]; 
} 

實際上，這些方法會以度數爲單位計算標題，然後輪到最接近的Direction。然後，您可以實施一種移動/轉動Direction標題中的座席的方法，例如， agent.turnToward(Direction d)或agent.move(Direction d)。

其他資源：

• 六邊形網格：http://www.redblobgames.com/grids/hexagons/#distances
• 與圖形代表網格：http://www.redblobgames.com/pathfinding/grids/algorithms.html
• 尋路與A *：http://theory.stanford.edu/~amitp/GameProgramming/