我正在为一个机器人项目做前端工作(一辆“自主”的汽车,它使用一些传感器和一张从SVG文件生成的地图进行自我定位)。在
为了使机器人可控,我们必须在机器人当前位置和目标之间生成路径。我用了最简单的算法:A*。在
我得到了一些奇怪的结果:汽车倾向于以45度的倍数行驶,还有一个特别恼人的问题:一些生成的路径非常嘈杂!在
在这种情况下,请参见橙色矩形附近的噪波路径:
有没有办法避免那些奇怪/嘈杂的结果?我们最终要建立一个最小的航向角。(汽车可以在不移动的情况下转弯,因此我们不需要任何路径“平滑”)。在
以下是我的A*实现:
def search(self, begin, goal):
if goal.x not in range(self.width) or goal.y not in range(self.height):
print "Goal is out of bound"
return []
elif not self.grid[begin.y][begin.x].reachable:
print "Beginning is unreachable"
return []
elif not self.grid[goal.y][goal.x].reachable:
print "Goal is unreachable"
return []
else:
self.cl = set()
self.ol = set()
curCell = begin
self.ol.add(curCell)
while len(self.ol) > 0:
# We choose the cell in the open list having the minimum score as our current cell
curCell = min(self.ol, key = lambda x : x.f)
# We add the current cell to the closed list
self.ol.remove(curCell)
self.cl.add(curCell)
# We check the cell's (reachable) neighbours :
neighbours = self.neighbours(curCell)
for cell in neighbours:
# If the goal is a neighbour cell :
if cell == goal:
cell.parent = curCell
self.path = cell.path()
self.display()
self.clear()
return self.path
elif cell not in self.cl:
# We process the cells that are not in the closed list
# (processing <-> calculating the "F" score)
cell.process(curCell, goal)
self.ol.add(cell)
编辑1:根据Popular需求,分数计算函数(过程)如下:
^{pr2}$编辑下面是neighbors方法(根据用户1884905的回答更新):
def neighbours(self, cell, radius = 1, unreachables = False, diagonal = True):
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 ) and (diagonal or (x == cell.x or y == cell.y)) :
neighbours.add(self.grid[y][x])
return neighbours
(这看起来很复杂,但它只给出了一个单元的8个邻域(包括对角邻域);它也可以采用与1不同的半径,因为它用于其他特性)
或邻接距离(取决于计算结果)
def manhattanDistance(self, cell):
return abs(self.x - cell.x) + abs(self.y - cell.y)
def diagonalDistance(self, cell):
xDist = abs(self.x - cell.x)
yDist = abs(self.y - cell.y)
if xDist > yDist:
return 1.4 * yDist + (xDist - yDist)
else:
return 1.4 * xDist + (yDist - xDist)
似乎这个实现是不正确的,因为它正在移动到距离目标最近(就像乌鸦一样)的被检查的单元格中还没有的,而它应该尝试并在找到障碍物时撤销路径以找到最佳障碍物。请看维基百科上的nice animation来了解这个想法。在
这里的问题是关于如何计算
cell.f
,也许你在做微积分时没有加上当前单元格的分数,一般来说A*应该采取步骤marked in red here并生成类似这样的次优路径。在由于空间被划分为离散的单元,当连续世界中的最佳路径(总是乌鸦在飞)正好在两个离散的移动之间时,它会尽可能地用这个奇怪的路径来近似它。在
我认为有两种方法:
cell.f
的信息)。在在无法了解您是如何实现
neighbour
和distance
函数的情况下,我仍然可以很好地猜测出什么问题:如果允许对角线遍历,则不应使用曼哈顿距离。
目标函数中的曼哈顿距离应该是距离目标最短距离的度量。(事实并非如此,如果你能沿对角线穿过积木。)
解决这个问题最简单的方法是将曼哈顿距离保持为目标函数,并将邻居的定义更改为只包括四个左右上下相邻的单元。在
编辑
您的代码仍有问题。以下伪代码取自wikipedia。我已经在重要的地方做了记号,你得检查一下。您必须确保i)如果您找到更好的解决方案,您正在更新开放集中的节点;ii)始终考虑到以前的行驶距离。在
相关问题 更多 >
编程相关推荐