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/