探析基于三角网追踪的机器人路径规划

《探析基于三角网追踪的机器人路径规划》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国石油大学（华东）硕士学位论文基于三角网追踪的机器人路径规划姓名：王欣申请学位级别：硕士专业：计算机应用技术指导教师：郑秋梅;宫法明20090401摘要基于Voronoi图的路径规划方法计算复杂度高，安全性差，本文提出一种基于三角网追踪解决机器人路径规划的方法，通过三角网的值点追踪策略结合Dijkatra算法生成一条机器人最优路径。该方法无需随障碍物的移动而重构三角网格，可根据障碍物的大小选取特征值对路径进行优化。仿真结果表明，该方法有效地降低了计算复杂度，提高了路径的安全性。按每个障碍物横切面的外接圆将障碍物量化为半径不同

2、的圆，圆心放入点集，利用Delaunay三角剖分法生成三角网。在三角网格中，依据每条边上两顶点的特征值确定一个值点。三角网的值点追踪就是按照某种算法寻找一条路径，能够经过包括起始点在内的所有边上的值点。值点追踪线进入网格时应正确选择初始边，一种方法以距离起始点最近的值点所在的边作为初始边，如果有两值点距离初始点相等且最近，优先考虑距离初始点较近的一条边作为初始边。另一种方法使用传统的动态规划方法进行初始边的选择，此方法可解决两个值点距离初始点相等且初始点距离值点所在的两条边亦相等的情况。追踪线进入网格后，应选择网格的另两条边上

3、的值点作为出口。追踪下一个值点的方法有两种：一种方法是为了较为准确的确定一条机器人行走的稳定路径，采用传统的Dijkstra算法。另一种方法是在精度要求不高的条件下，取另外两条边上的值点中距离目标点较近的一个作为下一个要追踪的值点。实验结果表明，基于三角网追踪的机器人路径规划算法在保证拐角点数目的同时，降低了算法的计算复杂度，提高了路径规划的安全性，满足实时路径规划的需求。关键词：机器人路径规划，Delaunay三角网，值点追踪，Voronoi图PathPlanningofMobileRobotBasedonTriangula

4、tionTracing(ComputerApplicationTechnology)WangXin(ComputerApplicationTeclmology)DirectedbyProfessorZhengQiumeiandAssociateProfessorGongFamingAbstractApathplanningmethodofmobilerobotbasedontriangulationtracingisproposedforthepurposeofdealingwithhi曲complicationandlows

5、ecurityduringtraditionalpathplanningmethodbasedonVoronoidiagram．Aoptimizationpathofrobotisproducedbyvalue—pointstracingstrategyoftriangulation，whichcombinedwithDijkatraalgorithm．Thismethodneedn’ttorestorethetriangulationalong嘶mthemotionofobstacles，andoptimizesthepat

6、hbyselectingfeaturevalues，whichdecidedinthesizeofobstacles．Simulationresultshowsthatthemethodreducedcalculationcomplexityandenhancedthesecurityofthepatheffectively．Quantifytheobstficlesintocircleswithdifferentradius，accordingtocircumcircleofeachobstacles’cross—secti

7、on,putthecentersofcircleintopointset,andconstructetrianglationbyDelaunaytrianglepartitionmethod．Determineavalue-pointaccordingtoeigenvalueoftwovertexoneachedge．Triangulationvalue-pointstracingmeansfmdapathbysomekindofalgorithm，andgothroughvalue-pointsonalledges，incl

8、udinginitialpoillt．Chooseinitialedgecorrectlywhenvalue-pointstracinglinegointotriangulation．Onemethodisthatmakingtheedgeonwhichthevalue-po