1

对于 A* 实现（为“汽车”机器人生成路径），我需要调整我的模型以考虑汽车的“宽度”，从而避开障碍物。

我得到的一个想法是将所有障碍物扩大汽车的宽度，这样所有离障碍物太近的单元格也将被标记为障碍物。

我尝试使用两种简单的算法来做到这一点，但它仍然太慢（尤其是在大网格上），因为它多次通过相同的单元格：

    unreachable = set()
    # I first add all the unreachables to a set to avoid 'propagation'
    for line in self.grid:
        for cell in line:
            if not cell.reachable:
                unreachable.add(cell)

    for cell in unreachable:
        # I set as unreachable all the cell's neighbours in a certain radius
        for nCell in self.neighbours( cell, int(radius/division) ):
            nCell.reachable = False

这是邻居的定义：

def neighbours(self, cell, radius = 1, unreachables = False):
    neighbours = set()
    for i in xrange(-radius, radius + 1):
        for j in xrange(-radius, radius + 1):
            x = cell.x + j
            y = cell.y + i
            if 0 <= y < self.height and 0 <= x < self.width and (self.grid[y][x].reachable or unreachables )) :
                neighbours.add(self.grid[y][x])

    return neighbours

是否有任何顺序算法（或 O(n.log(n))）可以做同样的事情？

4

2 回答 2

1

您正在寻找的是所谓的Minkowski sum，如果您的障碍物和汽车是凸的，则有一个线性算法来计算它。

于 2013-04-10T10:52:54.697 回答
0

我最终使用了卷积产品，我的“地图”（一个矩阵，其中“1”是障碍物，“0”是一个自由单元格）作为第一个操作数，以及一个汽车大小的矩阵，并且全部填充了“1”作为第二个操作数。

这两个矩阵的卷积乘积给出了一个矩阵，其中没有任何障碍物的细胞（即：附近没有任何障碍物）的值为“0”，而那些至少有他们附近的一个障碍物（即等于“1”的单元格）的值！= 0。

这是 Python 实现（使用 scipy 作为卷积产品）：

    # r: car's radius; 1 : Unreachable ; 0 : Reachable
    car = scipy.array( [[1 for i in xrange(r)] for j in xrange(r)] )
    # Converting my map to a binary matrix
    grid = scipy.array( [[0 if self.grid[i][j].reachable else 1 for j in xrange(self.width)] for i in xrange(self.height)] )

    result = scipy.signal.fftconvolve( grid, car, 'same' )

    # Updating the map with the result
    for i in xrange(self.height):
        for j in xrange(self.width):
            self.grid[i][j].reachable = int(result[i][j]) == 0
于 2013-04-24T11:55:38.107 回答