基于混合密度的改进逆向D＊算法在机器人未知环境导航中的应用.pdf

《基于混合密度的改进逆向D＊算法在机器人未知环境导航中的应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3l卷第7期甘肃科技V0l_31No．72015年4月GansuScienceandTechnologyApr．2015基于混合密度的改进逆向D水算法在机器人未知环境导航中的应用张啸宇1一．王挺，姚辰2，徐梁，沈滢f1．沈阳建筑大学信息与控制工程学院．辽宁沈阳710049；2．中科院沈阳自动化研究所，辽宁沈阳710049)摘要：智能机器人在现代社会中应用越来越广泛。未知环境中移动机器人只具有较少的先验知识，其导航涉及对环境的认知．对导航决策的优化，还有知识的表示与获取等方面。在未知环境下运行，需要合理的解决环境建模和全局规划所必需的大计算量与智能机器人实时控制之间的矛盾。为了

2、提高路径规划效率，本文进行了逆向D路径规划算法f11的分析和改进。利用激光测距仪LMS51l感知复杂环境信息，建立实时局部栅格地图。采用改进的逆向D算法．以滚动方式规划出中间目标节点到达当前位置的局部路径。机器人沿着局部路径行驶到这个中间目标节点后．再搜索下一个中间目标节点，滚动进行规划。直至机器人达到最终目标节点。在未到达中间目标节点的移动过程中遇到未知动态障碍机器人会实时重新规划．实现未知环境的自主安全运动。用C++在VS2010上测试算法并实际应用到机器人的实地测试。结果统计分析表明该方法具有可行性、有效性和实时性．规划效率明显提升。关键词：未知环境；实时导航；改进逆向D

3、算法；混合密度；加权曼哈顿距离中图分类号：TN962成是以其参考点为中心的“点”机器人1．标准逆向D术算法介绍2)设置机器人从起点start(x．y~1到目标点Goal1．1基本思想运动过程中所经历的目标势能最小值Emin。D算法是针对部分信息已知的环境中路径规自由栅格坐标点y的势能函数为划问题提出的。它是动态的A算法．首先离线应用E(1)=X／(xi-x~f+(yi-yf(1)A，．c算法建立目标距离势场。机器人向目标距离减小则在滚动优化过程中．机器人要以其当前位置的方向前进，当遇到动态障碍时．从机器人当前的Ryr)为中心，向外搜索目标势能小于Emin—A的位置规划一条能够到

4、达小于被阻挡路径上的目标中间栅格节点L，(A>O，是为了确保L(xY)势能小距离势场位置．然后机器人沿着修改后的路径绕过于Emin的常数项1称该位置为脱离当前势能陷阱区动态障碍。D算法在小规模环境区域规划中比较域的“脱离(1eavepoint)”而此栅格节点L应该满有效．但在较大规模环境下直接规划起点到终点的足．路径，往往造成很大的计算代价。为了不再计算初E(L,)=X／(x,-xs)％(y,-y~2

5、其中，被搜索通过搜索距离目标估计代价最小的中间目标：节点点I的估价函数／【)=s4i)+hq)。与D算法不同的作为“脱离点”．来满足机器人滚动优化路径的需是，g(i)是从机器人当前位置R到搜索栅格节点I要，提出了逆向D算法。的实际距离代价，即机器人距离，(1是搜索栅格节1．2原理步骤点I到目标节点Goal的估计代价．采用节点I到目采用以机器人为中心的扩展方法．在扩展：过程标节点的欧氏距离，()=Ef)即势能函数。中检测满足“脱离点”的条件4)在被搜索的区域里，机器人距离g()被记录1)采用栅格法对机器人行进中的感知信息建在栅格位图中，当搜索到满足上述条件的中间目标立局部环境地图

6、，对障碍物栅格进行预扩张．：考虑点L后，从L出发，按照机器人距离)减小的梯度机器人的通行半径以保证机器人和障碍物有一定方向，可以回溯到当前机器人位置R。而该回溯历程的安全避碰距离。经过预扩张后。机器人可以：被看的逆向过程就是从机器人当前位置R到达中间目12甘肃科技第31卷标L的路径划的路径点离开障碍边缘．并且使路径序列更为光5)机器人从起点出发．通过不断地采用A方滑和利于之后的优化和冗余路径点删除以及智能法搜索中间目标L来实现滚动的动态路径规划机器人的实时路径跟踪。在算法中h(i)=dexE(i)或h由于以上描述的方法搜索方向与D算法相(i)=dexm，一般靠近障碍时如在1．O

7、+3x1．0／9左右．反，即搜索到中间目标点L后从L出发．按照机器不会使变化过大而影响到规划．从而实现改进人距离g()减小的梯度方向，可以回溯到当前机器效果人位置R．而该回溯历程的逆向过程就是从机器人2．1．3目标密度当前位置R到达中间目标L的路径．因此称其为逆自定义概念．用di表示．定义为初始值十被搜索向D算法。点()／终点到边界最大距离。其中dg=nu~(终点到地图4个顶点的距离)。初始所有栅格点d均设置2改进逆向D术算法与实时环境地图为0．5．取距离终点最远di=O．1与距离终点最近=