基于改进A 星算法对自动导引小车路径规划研究*

王永成，杨明漾，张国辉

（郑州航空工业管理学院管理工程学院，郑州 450046）

0 引言

自动导引小车（Automatic Guided Vehicle）路径规划是AGV 作用在实际生产生活中的重要基础。有动态障碍物的路径规划是当前典型的路径规划问题，主要以最短路径和最短时间等为评价标准，从选定的起始点到目标点找出一条无碰撞的安全路径，路径规划问题可以称为避碰规划问题。AGV工作地图可以分为两种：静态地图和动态地图，本文主要研究动态地图中AGV 路径规划问题。

AGV 路径规划问题是一种约束优化问题，有许多专家学者在研究AGV 路径规划算法问题，使用的算法有概率路线图法（Probabilistic Roadmap，PRM）［1］、Dijkstra 算法［2］、A 星算法［3］、强化学习算法（Reinforcement Learning，RL）［4］、蚁群算法（Ant Colony Algorithm，ACA）［5］、遗传算法（Genetic Algorithms，GA）［6］、神经网络算法［7］、狼群算法（Wolf Colony Algorithm，WCA）［8］、粒子群算法（Particle Swarm Optimization，PSO）［9］、人工势场算法［10］、模糊逻辑算法［11］等。文献［12-19］也作了相关研究。

A 星算法是一种基于启发式的路径规划算法，也是静态环境中寻找最短路径最有效的直接搜索方法之一，相较于其他传统算法，具有更快的运算速度。

n 是路径上的一个节点，f（n）是从第n 个节点到终点的估计代价，g（n）是从第n 个节点到终点的实际代价，h（n）是从第n 个节点到终点的最佳路径的估计代价。在此算法中，估计代价h（n）越好，则运算速度与规划出的路径则最优，一般选用曼哈顿距离或欧几里得距离为估计代价。A 星算法是一种成熟且最有效的路径规划直接搜索方法，但A 星算法估计代价选取不好时，会出现运算时间长或路径不最优的问题。

1 基于改进A 星算法的AGV 路径动态规划

1.1 AGV 工作地图建模改进

路径规划地图建模中包含的元素主要有：AGV本身、静态障碍物以及动态移动障碍物。……