基于有效拐点和最短最小路径的蚁群路径规划方法

为了提高蚁群算法路径寻优的收敛精度和收敛速度，提出一种基于有效拐点的栅格图和基于最短距离最小步数路径（最短最小路径）的蚁群算法，用于搜索地面移动机器人从起点到终点的最短路径。在标准蚁群算法路径规划中,蚂蚁的搜索方式是有限方向有限邻域，本文采取无限邻域的搜索方式，可取捷径搜索任何可直通的栅格点，并提出有效拐点的概念，减小了单步搜索量。提出最短最小路径的概念，并用其取代欧氏距离作为启发值，提高了启发值的准确度和可靠性，同时用起点到终点的最短最小距离指导信息素更新，提高了蚁群算法迭代的质量。最后,在不同规模、不同障碍比例的栅格地图环境下进行实验，结果表明用最短最小路径距离取代欧氏距离的合理性，并验证了本文方法可以在降低计算量的同时，以更快的收敛速度搜索到距离更短、步数更少的路径。

Path Planning Method of Ant Colony Algorithm Based on Effective Turning Point and Shortest-minimum Path

In order to improve the convergence accuracy and speed of path optimization by ant colony algorithm, a grid map based on effective turning point and an ant colony algorithm based on the shortest distance and minimum number of steps path (shortest-minimum path) were proposed to search the shortest path from the beginning to the end. In the standard path planning of ant colony algorithm, the searching method of ants is finite neighbor with finite direction. A searching method with infinite neighbor and infinite directions was proposed, which can take a shortcut to any grid point that can be directly connected. The concept of effective turning point was put forward to reduce the single-step searching amount: firstly, based on the relationship between shortest path and obstacles, two windows were used to scan the whole map to find all the inflection points, and then a through-through tree was established from the end point to the starting point according to the hierarchical relationship, and only the points within the through-through tree were reserved as the effective inflection points. The concept of shortest-minimum path was proposed, which was used to replace Euclidean distance as heuristic value to improve the accuracy and reliability of heuristic value. At the same time, the shortest-minimum distance from the beginning to the end was used to guide the updating of pheromone and improve the quality of ant colony algorithm iteration. Finally, in the grid map environment with different scales and different proportions of obstacles, the rationality of using the shortest-minimum path distance to replace the Euclidean distance was proved through experiments, and it was verified that the method presented can search the path with shorter distance and fewer steps with faster convergence speed while reducing the calculation cost.