经典/启发式/改进启发式算法应用于机器人路径规划

路径规划是移动机器人导航规划中的一个十分重要且关键的研究课题。

移动的机器人总是在动态、复杂和不可控的环境中工作，比如对核电站的检查和变电站的检查。然而，复杂的动态工作环境要求移动的机器人能够调整其运动路线，以自主完成任务。使机器人能够实现自主移动的最关键因素之一是路径规划。

移动机器人路径规划技术，就是机器人在遵循一些优化指标(比如时间最短、路程最优和能耗最低等)前提下，在运行环境中规划出从起始点到目标点不发生碰撞的最优路径。

目前，移动的机器人路径规划的三大难题是环境建模、算法收敛速度和易陷入局部最优解。其中环境建模可以通过2D的栅格地图解决；而收敛速度和避免局部最优则涉及优化算法的设计或其他算法集成。

路径规划方法可以分为以下2种：

经典方法（如A*、Dijkstra算法），这类方法求解速度较快，但若存在多个最小值时，其不能保证得到最优解。

元启发式方法（即依托各类新型优化算法），此类方法简单灵活，能够跳出局部最优，受到许多学者的青睐。

本文作者将通过经典、元启发式算法求解机器人路径规划，并引入作者的原创改进算法进行对比分析。

00 文章目录

1 环境建模

2 优化算法

3 实验结果

4 源码获取​

01 环境建模

本文将移动机器人的环境设置为二维平面空间，使用栅格法建立环境模型。栅格法是地图建模中的一种经典方法，能直观地表达环境空间信息且信息数据易存储。在栅格地图中，障碍物的位置和大小是已知的，并且障碍物的大小和位置在机器人的运动过程中不会改变。

下图展示了2个二维栅格环境

分别表征了简单和复杂的工作环境栅格地图中，障碍物栅格为深色区域，可行栅格为浅色区域，每个栅格的8 个直接相邻的栅格为可直接通行栅格，机器人可在其中的可行栅格中根据一定规则选取下一前行栅格，相邻栅格间的距离用栅格中点之间的欧几里得距离表示。

[图:张军,张婷,于士坤.应用蚁群算法的全局路径规划改进[J].新乡学院学报,2023,40(06):25-28+51.]

假设机器人从起始点总共经过 M 步到达目标点，则目标函数为移动机器人的无碰路径长度 L，并使其长度达到最短:

式中，d(m)为欧式距离。

02 优化算法

本文中作者采用

经典算法：A*

启发式算法：WOA、PSO、GWO以及作者的原创改进算法AAMCWOA。

其具体原理这里不再阐述。

03 实验结果

在简单栅格地图中，运行程序结果如下：

其路径长度及运行时间如下：

在复杂栅格地图中，运行程序结果如下：

其路径长度及运行时间如下：

可以看到通过启发式算法较之经典方法进行路径规划，能有效跳出局部最优，但其计算复杂度较大。

04 源码获取

1.经典的A*算法应用于栅格路径规划获取：

见GZH：KAU的云实验台

其文件如下：

2.A*、GWO、WOA、PSO算法应用于栅格(简单/复杂)路径规划获取：

见GZH：KAU的云实验台

支持主程序一键运行，能够生成各算法运行结果（路径长度、运行时间）的excel表格

3.A*、GWO、WOA、PSO、AAMCWOA算法应用于栅格(简单/复杂)路径规划获取：

见GZH：KAU的云实验台

支持主程序一键运行，能够生成各算法运行结果（路径长度、运行时间）的excel表格

另：如果有伙伴有待解决的优化问题（各种领域都可），可以发我，我会选择性的更新利用优化算法解决这些问题的文章。

如果这篇文章对你有帮助或启发，可以点击右下角的赞/在看 (ง•̀_•́)ง(不点也行)