一种新的编码方法解决路径规划问题.pdf

《一种新的编码方法解决路径规划问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2011年第1期工业仪表与自动化装置·63·一种新的编码方法解决路径规划问题普措才仁(西北民族大学数学与计算机科学学院，兰州730030)摘要：提出了一种在极坐标环境下应用遗传算法求解机器人路径规划问题的方法。该方法采用简洁有效的路径染色体编码方法和快速的个体适应度计算方法，并对生成的初始路径点集进行提炼处理，以剔除其中含有的不必要拐点；仿真结果表明该方法可以解决大范围、多障碍环境的机器人路径规划问题。关键词：遗传算法；路径规划；极坐标中图分类号：TP242．2文献标志码：A文章编号：1000—

2、0682(2011)01—0063-03PathplanningmethodusingGA(GeneticAlgorithm)underpolarcoordinatesPucuocairen(CollegeofComputerScienceandInformationEngineering，NorthwestUnirersityforNationalities，Lanzhou730030，China)Abstract：Thispaperpresentsanovelmethodforrobotpa

3、thplanningusinggeneticalgorithm(GA)underpolarcoordinatesspace．Aconciseencodingapproachandaspeedycomputationoffitnessmeansareintroduced，andarefiningprocessisadoptedtoremovetheunnecessarypointsofpathmadebyGAalgorithm．Resultsofsimulationshowthatthispath

4、planningmethodcanbeusedtogeneratemovingpathinthecomplexandmulti—obstacleenvironmentforrobot．Keywords：geneticalgorithm(GA)；pathplanning；polarcoordinates范围做某种划分J。但是这些划分方法限制了染0引言色体的构造方式，因而经常丢失较优的路径。一般机器人的路径规划目的：根据机器人特性及其以路径起始点、中途点列、终止点等一系列点集作为周围环境状况，规划出

5、一条从已知的起始位置出发，基因进行染色体的编码，但一般进行交叉操作的父、绕过障碍物，到达预先规定的终止位置，并满足某些母代个体所表示的路径往往不在交叉位置相交，因优化指标的路径。此产生的子代个体经常是中途断裂的路径，必须进多年来，人们一直尝试应用遗传算法解决机器行人工修复。人路径规划问题_1，并取得一定的成功。一般做规划出的初始路径一般为很多折线段，影响机法是：在直角坐标空间中，以路径中的一系列中途点器人的前进速度，需对初始路径重新进行提炼，以删坐标位置作为染色体个体，并转换为二进制串，然后除不

6、必要的拐点。进行遗传操作。为了解决这些问题，该文尝试采用一种快速、简目前仍然有下列问题亟待解决：明的遗传算法，该法选用极坐标系作为规划坐标系，路径一般由一串节点的直角坐标(，Y)组成，力求快速有效地解决机器人路径规划问题。为了缩小节点坐标的范围，以减小遗传因子的搜索l问题的陈述空间，往往需要对规划区域进行初始化处理，即对大规划范围和坐标系的选取如图1所示。收稿日期：2010—06—240点为极坐标原点，P，为出发点，为目的基金项目：教育部人文社会科学研究一般项目(规划基金)资助地。图中阴影多边形

7、为规划场景内的地理阻隔或者(08JA740034)障碍物。路径规划目的就是计算出一系列路径节点作者简介：普措才仁，副教授，软件工程硕士，研究方向为计算机网络，人工智能，程序设计。P(i=1，2，⋯，)的位置。其中每个节点的位置用·64·工业仪表与自动化装置2011年第1期(P，0i)来表示。根据规划范围和障碍分布情况，如图2所示，定出边界(极角为0)和边界OA(极角为0)，同时确定极点边界内最近的障碍点z。考虑到机器人有时可能经过边界抵达目标，最大最小极角可分别取为Omin-5。和一十5。。极径

8、的最小值取llOZll(1—1／4)，最大值取P，llOPMll(1+1／10)。2．2适应度函数的求取，，jp必须首先考虑路径的避障能力，在此基础上再图1规划环境的描述做路径长度的比较，以确定路径个体的适应度函数。为了方便判定路径个体是否陷入障碍环境，可以将2路径规划的GA算法各个障碍近似用多边形表示，在进行适应度函数计算时，判断路径个体的各个折线段是否与障碍多边在大范围、多障碍环境下应用遗传算法解决路形的各边相交，如果与某一个的多边形的一个边相径规划问题，需要采用有效的编码方式和准确而计交，