我一直试图解决的问题是为有障碍物的dubins汽车(无向后运动，匀速)从给定位置到给定目标的路径查找。我尝试用一些简单的避障来实现无网格a*算法。我期望生成的路径直接朝着目标前进，并进行微小的调整，绕过它发现的障碍。然而，一旦障碍物被引入地图，路径似乎就会卡在算法成本函数的局部最低点。
我实现的成本函数如下：
f(x)=c(x)+g(x)
其中c(x)是总旅行成本，即从节点i-1移动到i的累积成本。此外，g(x)是从当前节点到最终目标的最优路径的成本，由于忽略障碍，该路径变为一条直线。
成本被用作最小堆中的优先级值，每次迭代都会弹出最小节点并生成子节点。当孩子们被生下来时，控制他们没有越界，没有被探访，也没有在障碍物内。如果这些控件返回false，则会将子控件添加到堆中。
我已经尝试将加权因子k*g(x)引入到路径成本中；激励"；算法向目标移动，而不是陷入困境。然而，这只是将最低点转移到了另一个位置，但仍然导致了卡住。
我将在下面包括我的A*算法的代码实现：
# Description: Pathfinding algorithm, iteratively generates new neighbouring
# nodes and selects the cheapest of these through utilizing a min heap.
# In: Car class object, a node as starting point.
# Out: The finishing node, with attached parent pointers.
def Astar(car, current):
minHeap = [] #initialize heap as list
h.heappush(minHeap, current) #push initial node onto heap
heapCount = 1 #add upon pushes to heap, subtract upon pop
# Iterate through nodes in priority queue
while not ((goal(car, current)) or heapCount == 0):
current = h.heappop(minHeap)
heapCount -= 1
for phi in [-m.pi/4, 0, m.pi/4]: #Full turns or straight are optimal, according to Pontryagins maximum principle
#calculate new values for each phi (steering angle)
xn, yn, thetan = step(car, current.x, current.y, current.theta, phi)
#control feasibility of position
if validCheck(car, xn, yn, current):
#calculate costs for these directives
costC = current.travelled + m.hypot(current.x - xn, current.y - yn) #cost of travel from start position
costG = m.hypot(car.xt - xn, car.yt - yn) #current optimal distance to goal
totalCost = costC + costG
#renew time stamp
newTime = current.time + 0.01
#create child from new data
child = Node(xn, yn, thetan, phi, totalCost, costC, newTime, current)
#push child onto heap
h.heappush(minHeap, child)
heapCount += 1
return current
注意car是一个包含某些属性的类：
- x0:foat:初始x位置[m]
- y0：浮动：初始y位置[m]
- xt:foat:目标x位置[m]
- yt:foat:目标y位置[m]
- xlb:foat:最小x位置[m]
- xub:foat:最大x位置[m]
- ylb:foat:最小y位置[m]
- yub:foat:最大y位置[m]
- obs:list：每个障碍的元组列表obs[i]
它还包括一个方法步骤，当给定转向角和以前的航向和位置时，该方法可以生成新的航向角和位置。
任何关于这个问题的建议或帮助，为什么会发生，以及我能做些什么来改进路径查找，都将不胜感激。
我还没有准备好解决方案，但有一个解释，也许还有一个提示你可以做什么。
分析
A*算法用于图搜索，与BFS等不知情策略相比，在给定适当的代价函数的情况下，可以大大减少搜索空间。但问题图的大小仍然很重要。
在您的代码中，我看到了0.01的时间增量，我读到这是一个提示，表明您正在执行从父节点到子节点的非常小的步骤。这当然是有道理的，最接近于一个平滑的，非量化的运动。但同时，它会导致问题图的巨大增长。
如果没有障碍，A*仍然可以优雅地处理这个巨大的图形。它将推迟与直线的所有偏差，因为它们的成本将高于直线上的节点。你的堆会增长(有一些调试输出显示它的大小…)，但大多数节点永远不会被进一步探索。
有了障碍，游戏发生了巨大变化。比方说，有一个障碍，因此产生的最佳路径比直线长1.00个单位。然后A*将探索所有无意义的路径，从起点到障碍物的线路上的某个地方开始，任意向左或向右转弯，直到这些路径达到1.00的额外长度。会有很多这样无用的道路，A*会陷入探索无稽之谈的困境。
建议
我会让A*在更高的级别上操作。
我猜你的障碍是多边形。因此，得到的总路径要么忽略障碍物，要么在其某个角落接触障碍物。接触点之间的元素将从具有某个航向的接触点开始，由最初的全转弯部分、然后是直转弯部分、最后一个全转弯部分组成，然后到达具有某些(不同)航向的下一个接触点(老实说，我不绝对确定这种转弯-直转弯模式是否真的涵盖所有可能的情况)。给定这样一个元素的起点和终点以及所需的终点，您可以使用一些几何图形来计算零件，顺便检查碰撞情况。
当你通过某个接触点时，你无法提前知道最佳航向，所以你必须检查所有可能的航向。
我会把这些元素作为A*探索的步骤。
所以，这就是我将A*应用于你的任务的方式：
-
要计算节点的子节点，对于所有其他多边形角点和该角点处的所有标题，计算从父角点到另一个角点的元素，从而得到给定的标题。检查这种元素在几何上是否可行，并且不会与某些障碍物碰撞。
-
作为成本函数，累积到目前为止行驶的长度，然后添加到目标的最短障碍物忽略路径。这可以是勾股式的直线距离，也可以是更精细的距离，考虑到从当前航向到面对目标的必要初始转弯。