资源描述：
《多层栅格邻域的路径规划算法研究(未录用)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、多层栅格邻域的路径规划算法研究刘乐柱摘要：本文通过在随机地图上进行路径规划，研究多层栅格邻域A*算法（MSA*）的计算性能和邻域栅格层数对其的影响。数值试验中，由A*至8层MSA*分别进行路径规划，并对路径规划结果进行比较分析。数值试验结果表明多层A*算法可以改善A*算法的规划路径，但同时也会增加计算时间。对计算时间和规划路径综合考虑，文中建议在实际路径规划问題中可以选用4-MSA*算法。关键词：随机地图；路径规划；A*算法；多层A*算法中图分类号：TP391.9文献标志码:A文章编号：doi:StudyofPathPlanningBasedonMulti-StepsA*Algor
2、ithmLiuLezhuAbstract:Thispaperstudiesthecomputationperformanceofmulti-stepsA*algorithm(MSA*)andtheinfluenceoflayersofneighborgridsthroughpathplanningontherandommaps・Insimulation,thealgorithmsfromA*to8-MSA*wereusedtopathplan,andtheresultswerecomparedandanalyzed・NumericalexperimentspresentMSA*ca
3、nimprovetheplanningpath,howeverincreasethecomputationtimessimultaneously.Considerwithcomputationtimeandplanningpath,thepapersuggestsusing4-MSA*fortheproblemsofpracticalpathplanning・Keywords:Randommap;Pathplanning;A*algorithm;Multi-stepsA*0引言路径规划是移动机器人H主导航的关键技术Z—，移动机器人路径规划是指在存冇障碍物的工作环境屮，利用一定的算法
4、或某些优化准则使机器人能从起始点绕开障碍物到达H标点，在此过程中尽最优化机器人运动轨迹⑴叽A*算法是一种典型的启发式搜索算法⑷，就早由Nilsson151等人提出。A*算法在路径规划研究中得到广泛应用和发展，考虑真实环境中各种因索的影响，徃评价函数屮加入描述真实环境的各种参量，使规划路径更加真实可靠。例如吴天羿等⑹考虑坡度及路而粗糙度等因索的影响对越野车路径规划研究；Guinness等人⑺研究了浮冰水域船舶路径规划问题。为了避免规划路径屮出现过多非自然转向，研究者捉出不同的平滑处理方法，如搜索方向一致策略⑵、三次B样条插值处理⑻等方法。但A*算法搜索方向的限制使规划路径中的转向角度
5、最小值是45。,经平滑处理后的规划路径仍存冇过多转向。MSA喺法通过搜索多层栅格邻域，增加搜索方向数，降低最小转向角度，使规划路径更加平滑门然，并且MSA*算法可以得到更加优化的路径。MSA*算法由Wu等人®提出并用丁•多忖标4D环境路径规划，文献［7］中也出现了MSA*算法思想使用了56个搜索方向。但均没冇对MSA水算法计算性能做详细分析。木文结介随机地图通过数值试验研究MSA*算法的性能和邻域栅格层数川对其的影响。数值试验结果肯定了MSA*算法的优越性，为实际应用中选择MSA水算法提供依据。1路径规划L1随机地图文中仿真试验所用二维地图通过计算机程序随机生成，随机地图上均匀分
6、布大小不同的【员I形.等边三角形、长方形障碍物。假定随机地图的尺寸为胪乩下血简述随机地图生成算法。图I障碍物形状及其特征虽示意图随机地图上障碍物总数为N,各个障碍物通过中心坐标（力丹）、度量障碍物人小的特征量.旋转角度等标记并绘制丁•随机地图中。障碍物大小特征量如图1所示。对丁•第/个障碍物首先生成标记其位置的中心坐标,xc=Random[0,W]yc=Random©H]It中函数Random［min,max］农示随机牛•成一个均匀分布在区间
7、min,max］内的随机数。若障碍物，是圆形或等边三角形，则生成度虽人小的特征虽，r=Random[&r0+d]。若障碍物i是长方形，则生成
8、////(a)A*搜索方向/厂/♦//H•/J(b)A*算法可行路径(c)MSA*搜索方向r=Random[心“)+d]/;=Randomly,r0+d]'对于等边三角形和长方形障碍物，还需生成绕中心点旋转的旋转角度。对于等边三角形障碍物旋转角度e[0,2刃，则按式()心=Random[0,2龙]随机生成(考虑对称性，等边三和形障碍物旋转角度也可取0mxw[0,兀/3])。对于长方形障碍物旋转角度0xote
9、0,7[,则旋转角度按式0似=Random[0,tt]随
