采样点路径规划：优化后的路径经常与障碍物发生碰撞

Question

在地图内随机生成n个采样点，在其中随机选择3个节点与起点和终点连接形成路径。
初始化：随机生成10条与障碍物不发生碰撞的初始路径
优化：利用智能优化算法分别对每条路径进行优化（利用智能优化算法的位置更新公式重新计算每个节点的坐标），但是新形成的路径经常会与障碍物发生碰撞
目标函数值是路径的长度，如果发生碰撞目标函数值则为路径长度+1000*n（n是与路径碰撞的障碍物个数）
目前我的解决办法是：如果不发生碰撞则保留路径，如果发生碰撞则不更新仍保留原始路径
目前存在的问题：
1、优化后路径发生碰撞的概率过高
2、我设计的目标函数在我的认知里是增加罚函数，但是按照我的更新方法罚函数好像没有起到作用，碰撞率依旧很高
请问有没有这方面比较了解的聪明努力学习家可以解答一下疑问，感谢大家

Answer 1

引自免费微信小程序：皆我百晓生

问题分析:

你的问题主要是在采样点路径规划中优化后的路径经常与障碍物发生碰撞，目前的解决办法是保留不发生碰撞的路径，但仍然存在两个问题：1) 优化后路径发生碰撞的概率过高；2) 目标函数中的罚函数似乎没有起到作用。

解决方案:

1. 碰撞检测算法: 你可以考虑使用更为准确的碰撞检测算法，例如使用线段与多边形的碰撞检测算法。可以将障碍物表示为一系列边界线段，然后检测路径与障碍物之间是否有交点。如果有交点则表示路径与障碍物发生碰撞。

2. 优化算法改进：

   • 遗传算法：可以尝试使用遗传算法进行路径优化。在更新路径时，需要使用交叉和变异运算符。在交叉运算中，可以选择两条路径中相同位置的节点之间进行交换。在变异运算中，可以随机选择一条路径中的节点进行随机移动。
   • 模拟退火算法：另一个优化算法是模拟退火算法。在每次迭代中，可以选择随机移动节点的方式来更新路径。模拟退火算法允许在优化过程中接受一些差解，从而可以更好地跳出局部最优解。

3. 目标函数设计改进：

   • 逐步增加罚项：可以考虑逐步增加目标函数中的罚项。例如，初始时将罚项系数设为0，优化一定次数后逐步增加罚项系数。这样可以让优化算法在初始阶段更加注重路径的长度优化，而在后续阶段更加注重碰撞的避免。
   • 罚项权衡：重新评估罚项的权衡程度。目标函数中的罚项值（1000*n）可能过于显著。你可以尝试不同的系数，例如减小罚项的权重，看看是否会对结果产生影响。

综上所述，你可以尝试改进碰撞检测算法、优化算法和目标函数设计来解决你的问题。