陆缘缘 崔衍

摘要：路径规划技术已经成为各大领域研究的话题，在生活中被广泛使用，具有很高的研究价值。而路径规划技术的主要核心在于路径规划算法。首先，对路径规划技术进行概述。其次，对常用的路径规划相关算法进行分析和总结，提出其所存在的缺点及问题。再着重对目前各种改进算法、混合算法的使用等方面进行分析，对其改进方向、使用场景等方面进行总结。最后，对路径规划算法所存在的问题进行提出，对下一步的改进与研究趋势进行展望。

关键词：路径规划技术; 算法; 混合算法

Abstract： Path planning technology has become a research topic in various fields， is widely used in life， and has high research value. The main core of the path planning technology is the path planning algorithm. First， an overview of path planning technology. Secondly， it analyzes and summarizes the commonly used path planning related algorithms， and puts forward their shortcomings and problems. Then focus on the analysis of the current various improved algorithms and the use of hybrid algorithms， and summarize their improvement directions and usage scenarios. Finally， the problems of the path planning algorithm are put forward， and the next improvement and research trends are prospected.

Key words： path planning technology; algorithm; hybrid algorithm

路径规划技术[1]目前在很多领域均有着广泛的应用，其主要内容是根据路径规划算法[2]来实现最优路径的搜索，所得路线即起始点到目标点之间的无障碍安全通路。路径规划算法包括传统算法和智能仿生算法，从传统的算法到之后的智能仿生算法根据路径规划算法各自的特点选择适合场景应用都已经取得了很大的进展。

文章主要从常见的路徑规划算法进行分析其优缺点;再通过对相关文献的学习，总结出A*算法、Dijkstra算法、蚁群算法、粒子群算法等改进;最后对路径规划算法改进方向做出一些总结与展望。

1 路径规划算法综述

路径规划技术是一种应用于智能领域的新型支撑技术，其中的路径规划算法依据其实现原理的不同分为传统型路径规划算法和智能仿生学算法。近年来，路径规划已经是国内外学者研究的热点问题，目前在众多科技领域中已有很大的成就及突破。

路径规划技术在众多领域中都有着广泛的应用，在高科技领域中的具体应用场景有：自动引导车、智能搜救机器人、机场巡检机器人等;在军事领域中的具体场景有：无人水面艇避障、碰撞预测、海上应急物流;在日常生活中的具体应用场景有：GPS导航、旅行商问题（TSP）、车辆路径规划问题（VRP）等;在网络通信中的具体应用场景有：路由选择问题等;在物流管理领域中的具体应用场景有：包裹分拣、快递配送路径选择等。

路径规划算法的实现主要是通过高级语言编写而完成的，主要分为传统算法和智能仿生算法，其常用的人为算法包括：A*算法、Dijkstra算法、Floyd算法;智能仿生算法包括：遗传算法、蚁群算法、模拟退火算法等。从传统算法、智能仿生算法发展到传统算法与仿生算法结合的算法都体现出路径规划技术的发展。

2 常见人工算法及其优缺点

Dijkstra算法[3]：该算法从起点遍历到其他各节点计算其距离直到目标节点的最短路径。该算法的主要特点是确保每一次的迭代路径均是最短的。该算法鲁棒性好但其搜索效率低。

A*算法[4]：该算法从起点开始，检查其从起点开始，遍历起点周围邻近的点，然后再遍历已经遍历过的点邻近的点，逐步的向外扩散，直到找到终点。该算法准确性高、性能好，但可能出现目标不可达而浪费性能的现象。

Floyd算法[5]：该算法引用的是动态规划思想，在两顶点间插入一个或以上的中转点，比较经过和未经过中转点的距离哪个更短。其主要用于求一条带权值有向图的任意两点间的最短路径。该算法实现简单，但实现复杂度高。

3 常用智能仿生算法及其优缺点

蚁群算法[6]：该算法思想来自对蚁群觅食行为的探索，每个蚂蚁觅食时都会在走过的道路上留下一定浓度的信息素，相同时间内最短的路径上由于蚂蚁遍历的次数多而信息素浓度高，加上后来的蚂蚁在选择路径时会以信息素浓度为依据，起到正反馈作用，因此信息素浓度高的最短路径很快就会被发现，进而找到蚁群从蚁巢开始经过若干个觅食地所寻找出一条近距离且无障碍的可行路径。该算法鲁棒性强、信息正反馈性、自适应性、有并行性和可扩展性，但可能出现前期搜索效率低、易收敛、易陷入局部最优解等问题。

遗传算法[7]：该算法是一种模拟达尔文遗传选择和自然淘汰的生物进化过程中的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是按照基因遗传学原理而实现的一种迭代过程的搜索算法。其中采用随机方式搜索，利用交叉变异的操作提供多样性来适应不同情形。该算法全局搜索力强并可以有效处理复杂的最优解问题，但所占空间大、运行效率低、运算周期较长。