如何避免机器人陷入局部极小值？

Question

我有一段时间忙于机器人的运动规划，有一段时间我想探索“势场”方法提供的机会的可能性。我的挑战是避免机器人在使用“势场”方法时陷入“局部最小值”。我没有使用“随机游走”的方法来避免机器人陷入困境，而是考虑是否有可能实现A*的变体，它可以作为一种精确的向导，以避免机器人陷入“局部最小值”。

有没有一些这样的经验，或者可以参考文献，它以一种比“随机游走”方法更有效的方式避免了局部最小值。

Answer 1

A*和潜在字段都是搜索策略。你正在经历的问题是，一些搜索策略比其他搜索策略更“贪婪”，而且通常情况下，过于贪婪的算法会陷入局部最小值。

有一些替代方案，贪婪(陷入局部最小值的主要原因)和多样性(尝试新的替代方案，在短期内似乎不是一个好的选择)之间的紧张关系被参数化。

几年前，我研究了一些关于蚂蚁算法(搜索Marco Dorigo，ACS，ACO)，他们有一系列的搜索算法，几乎可以应用于任何事情，它们可以控制你对搜索空间的贪婪和探索。在他们的一篇论文中，他们甚至比较了使用遗传算法、模拟退火等方法求解TSP (规范旅行商问题)的搜索性能。蚂蚁赢了。

我过去已经用遗传算法解决过TSP问题，如果你愿意的话，我还有delphi的源代码。

Answer 2

使用调和函数进行路径规划。调和函数是描述流体流动和其他自然现象的势函数。如果它们是使用边界条件正确设置的，则它们没有局部最小值。自90年代初以来，Rod Grupen and Chris Connolly就一直在使用这些工具。这些函数已经被证明是最优控制的一种特定形式，它最小化了碰撞概率。它们可以在低维空间中使用差分方程(即Gauss-seidel，连续超松弛等)有效地计算。