论文部分内容阅读
摘要：移动机器人技术是机器人技术的重要组成部分，也是人工智能的重要体现。本文总结了移动机器人智能化发展过程中面临的挑战，描述了机器人与环境的关系，重点论述路径规划关键技术。为进一步开展机器人技术的研究和设计奠定了基础。
关键词：路径规划；A*算法；D*算法；智能算法
0.引言
移动机器人集机械、电子、计算机、传感测控等多项技术为一体，是机械电子工程领域多学科互相结合、互相渗透的产物。移动机器人技术的研究水平，反映了一个国家诸多相关技术学科的综合发展水平，是一个国家综合科技实力的集中体现；移动机器人技术的研究还反过来作用于与它相关的各个学科，作为与它相关的诸多学科的研究载体和实验平台，移动机器人技术的进步对一个国家的整体科技实力的增长将起着重要的推进作用。
路径规划技术是移动机器人研究中的一项关键技术，其中全局路径规划是根据先验知识（如给定地图），在某些约束条件下，规划出一条从起点到终点的无碰路径。全局路径规划是移动机器人系统所有智能行为的基础，在整个移动机器人技术体系中占有重要地位。
1.路径规划
路径规划技术是移动机器人领域中的核心问题之一，也是机器人学中研究人工智能问题的一个重要方面。下面综述路径规划重要算法。
1.1 Dijkstra算法
Dijkstra 算法是由EW.Dijkstra提出的用在带权有向图上的最优路径算法。利用 Dijkstra 算法可以在有向图中从某一个指定点找到到其他任意一个点的最短路径。该算法的搜索步骤是：对每个顶点x指定一个数d（x），表示的是从起点 s 到当前顶点 x 的最短路径长度。开始时， d （ s）=0， d （x）=∞，y为已标注的最后一个顶点，首先对 s 标注。对于每个未标注的顶点 x， d （x）为如下式所示。
（1）
其中 a （ y，x）是 y，x 之间的弧长。对具有 d （x）最小值的未标注点进行标注，同时将 y 值定为 x。如果顶点 t 已标注，则算法终止。即已经找到了一条从 s 到 t 的最短路径。若 t 未标注，则继续上面的遍历。
其最大特点就是以起始点为中心向外层层扩展，直到扩展到终点为止。但由于它遍历计算的节点很多，所以效率低。
1.2 A*算法
A*算法是由 Nilsson 提出的一种搜索算法。其主要的思想是对目标点进行循环搜索，以获得机器人的轨迹。它通过对状态空间中每个搜索位置进行评估，得到最好的位置，再根据这个最好位置进行搜索，直到找到目标点。这种方法可以省略大量不必要的搜索，提高了效率。
A*算法是一种在静态路网中的路径规划方法[1]，A*算法最基本的寻路表达式为： f （ n）= g（n）+h（n），其中f （n）是当前节点 n 到终点的估价函数，g （n）为整个搜索空间里起始点到当前节点n的距离代价值， h （n）是从当前点n到下一搜索点估价最好的路线，与程序相对应，为求得算法的最优解，也就是说能够确保找出最优的路径，其关键条件在于选取 h （n）的值，这时将会存两种情况，当 h （ n）<=n时，会使得搜索时，可搜索的点数增加，从而使得搜索的范围增大，增加了系统负担，这样固然可以得到最优解，但是效率将会明显降低，另一种情况，与之相反，减少搜索的点数，这样系统效率固然上升了，但这样有可能会忽略了某些优点，导致最终不能得到最优的解。
1.3 D*算法
在A*算法的基础上，Stentz提出了一种动态路径规划算法，即D*算法，能够有效地利用己有的规划计算信息[2]。
D*算法捜索得到的优化路径的好坏与算法代价估计函数的选取有着紧密的联系，一个较优的代价估计函数能够使D*算法捜索到较优的路径，而一个不合适的代价估计函数会极大地影响D*算法的性能，极大降低路径的可靠性和稳定性，在较为复杂的环境中甚至找不到优化路径。
在利用D*捜索算法进行路径规划的过程中，如果机器人在前进过程中遇到障碍物，算法能够利用前次规划的信息重新捜索路径，避免了对相同数据的重复计算，提高了二次路径规划的效率，因此D*算法能够较好地应用于动态环境下的路径规划。但是，D*算法存在捜索空间较大的缺陷，尤其是在比较复杂的环境下，算法的搜索空间将大大増加，并且时间复杂度随着地图维数的増加呈指数级增长，因此，极大地降低了路径规划的速度。
1.4 智能算法
人工智能路径规划技术是将现代人工智能技术应用于移动机器人的路径规划中，如人工神经网络、进化计算、模糊逻辑与信息融合等，其中蚁群算法是较好应用于组合优化问题的智能优化算法，该算法及其派生算法在机器人路径规划研究领域已得到应用[3-6]，在蚁群算法较好解决旅行商问题（TSP） 的基础上，许多学者进一步将蚁群优化算法引入到水下机器人（UV） 的路径规划研究中。由于模糊逻辑和信息融合技术在不确定性信息处理方面有极好的表现，且移动机器人传感器采集的环境信息存在不确定性和不完整性，使得模糊邏辑和信息融合技术在移动机器人路径规划中有较好的应用。
2.结束语
本文针对移动机器人路径规划关键技术进行了综述，旨在为进一步开展机器人技术的研究和设计奠定基础。
参考文献：
[1]吴超帅.改进A*算法及其在ASR移动机器人路径规划中的应用[D].湘潭大学，2012.
[2]李凯业.基于改进分层D*搜索算法的室内路径规划问题研究[D].合肥工业大学，2015.
[3]鲍庆勇，李舜酩，沈峘，门秀花.自主移动机器人局部路径规划综述[J].传感器与微系统，2009，09：1-4+11.
[4]王俊.移动机器人的定位方法研究[D].东北大学，2010.
[5]朱大奇，颜明重.移动机器人路径规划技术综述[J].控制与决策，2010，07：961-967.
[6]许长岚.移动机器人设计及其全局路径规划[D].大连理工大学，2006.
作者简介：
1.瞿亦潇，女，1996.10，山东人，单位：上海工程技术大学本科生，研究方向：智能信息处理.
2.游晓明，女，1963.12，湖北省黄石市人，博士，教授，研究领域为智能信息处理理论及应用、模式识别和人工智能、分布式并行智能处理及应用。
通讯作者：游晓明
基金项目：上海工程技术大学课程改革与建设项目（No.y201702002，17XJG004，cs1702001）；上海高校本科重点教学改革项目（A1-0601-18-01137）
关键词：路径规划；A*算法；D*算法；智能算法
0.引言
移动机器人集机械、电子、计算机、传感测控等多项技术为一体，是机械电子工程领域多学科互相结合、互相渗透的产物。移动机器人技术的研究水平，反映了一个国家诸多相关技术学科的综合发展水平，是一个国家综合科技实力的集中体现；移动机器人技术的研究还反过来作用于与它相关的各个学科，作为与它相关的诸多学科的研究载体和实验平台，移动机器人技术的进步对一个国家的整体科技实力的增长将起着重要的推进作用。
路径规划技术是移动机器人研究中的一项关键技术，其中全局路径规划是根据先验知识（如给定地图），在某些约束条件下，规划出一条从起点到终点的无碰路径。全局路径规划是移动机器人系统所有智能行为的基础，在整个移动机器人技术体系中占有重要地位。
1.路径规划
路径规划技术是移动机器人领域中的核心问题之一，也是机器人学中研究人工智能问题的一个重要方面。下面综述路径规划重要算法。
1.1 Dijkstra算法
Dijkstra 算法是由EW.Dijkstra提出的用在带权有向图上的最优路径算法。利用 Dijkstra 算法可以在有向图中从某一个指定点找到到其他任意一个点的最短路径。该算法的搜索步骤是：对每个顶点x指定一个数d（x），表示的是从起点 s 到当前顶点 x 的最短路径长度。开始时， d （ s）=0， d （x）=∞，y为已标注的最后一个顶点，首先对 s 标注。对于每个未标注的顶点 x， d （x）为如下式所示。
（1）
其中 a （ y，x）是 y，x 之间的弧长。对具有 d （x）最小值的未标注点进行标注，同时将 y 值定为 x。如果顶点 t 已标注，则算法终止。即已经找到了一条从 s 到 t 的最短路径。若 t 未标注，则继续上面的遍历。
其最大特点就是以起始点为中心向外层层扩展，直到扩展到终点为止。但由于它遍历计算的节点很多，所以效率低。
1.2 A*算法
A*算法是由 Nilsson 提出的一种搜索算法。其主要的思想是对目标点进行循环搜索，以获得机器人的轨迹。它通过对状态空间中每个搜索位置进行评估，得到最好的位置，再根据这个最好位置进行搜索，直到找到目标点。这种方法可以省略大量不必要的搜索，提高了效率。
A*算法是一种在静态路网中的路径规划方法[1]，A*算法最基本的寻路表达式为： f （ n）= g（n）+h（n），其中f （n）是当前节点 n 到终点的估价函数，g （n）为整个搜索空间里起始点到当前节点n的距离代价值， h （n）是从当前点n到下一搜索点估价最好的路线，与程序相对应，为求得算法的最优解，也就是说能够确保找出最优的路径，其关键条件在于选取 h （n）的值，这时将会存两种情况，当 h （ n）<=n时，会使得搜索时，可搜索的点数增加，从而使得搜索的范围增大，增加了系统负担，这样固然可以得到最优解，但是效率将会明显降低，另一种情况，与之相反，减少搜索的点数，这样系统效率固然上升了，但这样有可能会忽略了某些优点，导致最终不能得到最优的解。
1.3 D*算法
在A*算法的基础上，Stentz提出了一种动态路径规划算法，即D*算法，能够有效地利用己有的规划计算信息[2]。
D*算法捜索得到的优化路径的好坏与算法代价估计函数的选取有着紧密的联系，一个较优的代价估计函数能够使D*算法捜索到较优的路径，而一个不合适的代价估计函数会极大地影响D*算法的性能，极大降低路径的可靠性和稳定性，在较为复杂的环境中甚至找不到优化路径。
在利用D*捜索算法进行路径规划的过程中，如果机器人在前进过程中遇到障碍物，算法能够利用前次规划的信息重新捜索路径，避免了对相同数据的重复计算，提高了二次路径规划的效率，因此D*算法能够较好地应用于动态环境下的路径规划。但是，D*算法存在捜索空间较大的缺陷，尤其是在比较复杂的环境下，算法的搜索空间将大大増加，并且时间复杂度随着地图维数的増加呈指数级增长，因此，极大地降低了路径规划的速度。
1.4 智能算法
人工智能路径规划技术是将现代人工智能技术应用于移动机器人的路径规划中，如人工神经网络、进化计算、模糊逻辑与信息融合等，其中蚁群算法是较好应用于组合优化问题的智能优化算法，该算法及其派生算法在机器人路径规划研究领域已得到应用[3-6]，在蚁群算法较好解决旅行商问题（TSP） 的基础上，许多学者进一步将蚁群优化算法引入到水下机器人（UV） 的路径规划研究中。由于模糊逻辑和信息融合技术在不确定性信息处理方面有极好的表现，且移动机器人传感器采集的环境信息存在不确定性和不完整性，使得模糊邏辑和信息融合技术在移动机器人路径规划中有较好的应用。
2.结束语
本文针对移动机器人路径规划关键技术进行了综述，旨在为进一步开展机器人技术的研究和设计奠定基础。
参考文献：
[1]吴超帅.改进A*算法及其在ASR移动机器人路径规划中的应用[D].湘潭大学，2012.
[2]李凯业.基于改进分层D*搜索算法的室内路径规划问题研究[D].合肥工业大学，2015.
[3]鲍庆勇，李舜酩，沈峘，门秀花.自主移动机器人局部路径规划综述[J].传感器与微系统，2009，09：1-4+11.
[4]王俊.移动机器人的定位方法研究[D].东北大学，2010.
[5]朱大奇，颜明重.移动机器人路径规划技术综述[J].控制与决策，2010，07：961-967.
[6]许长岚.移动机器人设计及其全局路径规划[D].大连理工大学，2006.
作者简介：
1.瞿亦潇，女，1996.10，山东人，单位：上海工程技术大学本科生，研究方向：智能信息处理.
2.游晓明，女，1963.12，湖北省黄石市人，博士，教授，研究领域为智能信息处理理论及应用、模式识别和人工智能、分布式并行智能处理及应用。
通讯作者：游晓明
基金项目：上海工程技术大学课程改革与建设项目（No.y201702002，17XJG004，cs1702001）；上海高校本科重点教学改革项目（A1-0601-18-01137）