Abstract:

Aiming at the problems of global path planning of robot in static environment, such as unable to find the shortest path, slow convergence speed, great blindness of path search and many inflection points, an improved bidirectional ant colony algorithm is proposed. Taking the grid map as the robot running environment, the effective vertices of obstacles are defined, coded and used. At the same time, combined with the two-way ant colony algorithm with the same effective vertices of obstacles as the encounter condition, the path search is carried out alternately in two directions, which can quickly find a shorter path and get fewer path inflection points. The introduction of improved state transition rules can speed up the search speed. An adjustable constant factor is introduced into the hair function, and each step is equivalent to one or more steps of the traditional algorithm when the effective vertex of the obstacle is taken as the node of path search. Dynamic adjustment of volatile coefficient and setting of pheromone concentration range can avoid falling into precocity. Compared with other algorithms, the feasibility, effectiveness and superiority of the improved algorithm are verified.

Key words: mobile robot, path planning, ant colony algorithm, bidirectional path search, effective vertex of obstacle

摘要：

针对机器人在静态环境下全局路径规划存在无法找到最短路径，收敛速度慢，路径搜索盲目性大，拐点多等问题，提出一种改进双向蚁群算法。以栅格地图为机器人运行环境，对障碍物有效顶点进行定义、编码和运用，同时结合以相同障碍物有效顶点为相遇条件的双向蚁群算法，双向交替进行路径搜索，能够快速地找到更短路径，得到的路径拐点更少。引入改进的状态转移规则，能够加快搜索速度。在启发函数中引入可调常数因子，在以障碍物有效顶点为路径搜索的节点，每走一步相当于传统算法的一步或多步行走。动态调整挥发系数并设置信息素浓度范围，能够避免陷入早熟。通过与其他算法仿真对比，验证了改进算法的可行性、有效性和优越性。

关键词: 移动机器人, 路径规划, 蚁群算法, 双向路径搜索, 障碍物有效顶点