黄健萌 吴宇雄 林谢昭

(福州大学机械工程及自动化学院， 福州 350116)

0 引言

随着移动机器人被广泛应用于农业等诸多领域，移动机器人导航技术逐渐成为研究热点。路径规划是移动机器人完成导航任务的核心技术之一，其目的是让机器人在充满障碍物的复杂环境中找到从起点到终点的最佳无碰撞路径[1]，通常是以规划出的路径最短作为优化目标。目前常用的路径规划方法有栅格法、人工势场法、可视图法等[2]，以及蚁群算法、粒子群算法等智能算法[3-4]。栅格法简单有效，是目前使用最广泛的一种方法。

栅格法中，Dijkstra算法[5]搜索时只考虑已花费成本，虽然能保证找到最短路径，但会扩展大量无用节点。BFS算法采用启发函数快速接近目标点，不考虑已花费成本，其效率高于Dijkstra，但不能保证找到最短路径。A*算法[6]兼顾了两者的优点，在考虑已花费成本的同时采用启发式搜索，并能保证找到最短路径。但A*算法规划的路径通常是一组曲折路径，仅是离散空间上的最优解，与连续空间上实际最优解有较大差距。“视野线”法[7-9]常被用来对A*算法规划的路径进行平滑后处理，但只在后处理时使用平滑方法往往无法使路径跨过障碍物，优化效果有限，平滑后的路径有时仍与最优解存在较大差距。为此，Theta*算法[10]提出了任意角度规划路径的新思路，该方法在A*算法的基础上，采取实时收缩父节点，即边搜索边平滑的策略，与采用后处理平滑的路径规划方法相比，能更好地接近最优解。……