A*方向离散化

Question

我有一个有障碍的空间，我希望能找到一条途径。我能做的是将空间离散成一个网格，并使用A* (或D*或其他任何东西)来找到通过它的路径。现在，我希望向算法中添加方向。因此，节点位置现在变成了3d矢量(x，y，phi)。仅当一个节点属于一个圆弧时，才能从一个节点切换到另一个节点(两个位置都在一个圆上，并沿切线定向)。我如何对空间进行离散化，使角度不会爆炸，因为通过遍历图形，可能的角度集变得有限？谢谢。

Answer 1

据我所知，你的挑战不是离散化坐标，而是离散化标题。我不得不在网格世界中做同样的事情，允许在八个方向上移动，即水平，垂直和对角。您的离散化空间应该与问题域相匹配。供您参考：

• 4-directions：使用在edges
• 8-directions上移动方形网格使用在边缘和vertices
• 6-directions上移动的方形网格使用在edges
• 12-directions上移动的六边形网格使用在边缘和点之间移动的六边形网格
• ...诸若此类。

为了实际获得离散化的标题，我声明了一个名为Direction的enum

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

• Representing网格:带A*的http://www.redblobgames.com/pathfinding/grids/algorithms.html

• Pathfinding：http://theory.stanford.edu/~amitp/GameProgramming/

Answer 2

通过确保phi被认为是模2pi，即对于k的任何整数值，phi = phi + 2pi*k，可以防止角度爆炸。

在类似C的语法中，您可能最终会使用fmod更新phi。

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

其中deltaphi是您引入的角度的变化(以弧度为单位)。

最常见的方法是将角度phi的值约束为n离散角度之一，这也具有避免精度/舍入问题的优点。假设您知道phi只能接受一个实数值，那么您可以将其视为整数，并在必要时将该值映射到实数。

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

其中，角度增量的变化是(2*增量*pi)/n弧度。

然而，找到一个好的离散化只是解决方案的一部分-它定义了配置空间的表示，但正如您所指出的，您还需要考虑什么是有效的转换。

将角度集成到规划中的最简单方法是要求旋转和平移是不同的(任何时候都可以进行其中一种，但不能同时进行)，或者是可组合的(始终进行平移，然后在到达时立即旋转)。

在转弯的同时向前和/或向后移动引入了更复杂的内容，而且往往不能很好地处理离散网格-它往往需要您正在使用的车辆的某些模型。最常见的是简单的非完整模型-只向前的汽车(Dubins的汽车)或具有向前/反向的汽车(里兹·谢普汽车)-你指的是圆的切线，我猜这就是你想要的。Dubins-Curves或类似的库可用于构建可与A* (或D*)规划器组合的可能路径的库。

Mihail Pivtoraiko，Ross A. Knepper和Alonzo Kelly的Differentially Constrained Mobile Robot Motion Planning in State Lattices有一些惊人的图像。