建模机器人避路障问题.docx

机器人避障问题摘要：本文根据题目要求,主要研究了在一个区域内有障碍物的最短路径问题.依题意我们可以认为最短路径一定是由线和最小圆弧组成,圆心在障碍物的顶点.对于问题一首先讨论由O到A的距离,为了到达目标点,我们建立了圆线模型.将路线分为两部分：一部分是平面上的自然最短路径〔即直线段〕,另一部分是限定区域的部分边界的半径至少十个单位以外的圆弧,得到其路径长度为,并用MATLAB程序解得最短路径471.0372对于O到B的距离问题,为了到达目标点,我们需要建立圆与点圆模型,其中由于圆与圆之间的不同的位置关系,又可以分为同向相切与异向相切,同向相切时 ,异向相切时.由MATLAB程序解得最短路径869.8523.对于O到C,与前者的区别是障碍物大圆视为半径较大的转折弧,为了到达目标点,依旧建立圆圆结构与线圆结构模型,经MATLAB程序解得最短路径为1011.3.对于OABCO的路径问题,除了用了上述提到的圆圆,线圆结构外,还建立了圆心偏移的模型〔即点ABC在相对应的弧上〕,A点偏以后的坐标为〔290.9,304.1〕,B点偏以后的坐标为〔108.23,694.32〕,C点偏以后的坐标为〔707.26,633.12〕,将OABCO分为两部分,一部分为OABCN〔730,520〕的距离,另一部分为由N回到O的距离,两部分结果之和即为所求路径.OABCN的距离1.7691e+003,N到O为880.7744,总长为2649,6744对于问题二,我们将路线问题转化为规划问题,求的最短时间,目标函数为由LINGO有最短时间为94.22822,切点坐标〔69.80,211.98〕〔77.75,220.14〕圆心〔82.14,207.92〕.关键词:最短路径最优化模型避障路径规划问题线圆结构一 问题重述机器人从原点O出发且他只能在图中所给出的800*800正方平面场景范围内活动.且平面场景范围内的12个不同形状的区域是机器人不能与之发生碰撞的障碍物.在平面场景中,障碍物外指定一点为机器人要到达的目标点〔要求目标点与障碍物的距离至少超过10个单位〕.规定机器人的行走路径由直线段和圆弧组成,其中圆弧是机器人转弯路径.机器人不能折线转弯,转弯路径由与直线路径相切的一段圆弧组成,也可以由两个或多个相切的圆弧路径组成,但每个圆弧的半径最小为10个单位.为了不与障碍物发生碰撞,同时要求机器人行走线路与障碍物间的最近距离为10个单位,否则机器人将无法完成行走.机器人直线行走的最大速度为个单位/秒.机器人转弯时,最大转弯速度为,其中是转弯半径.请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型.对4个点O<0, 0>,A<300, 300>,B<100, 700>,C<700, 640>,具体计算：<1> 机器人从O<0, 0>出发,O→A、O→B、O→C和O→A→B→C→O的最短路径.<2> 机器人从O <0, 0>出发,到达A的最短时间路径. 800×800平面场景图二问题分析1、问题一中要求定点机器人按照一定的行走规则绕过障碍物到达目标点的最短路径,由于机器人不能折线拐弯,所以拐弯处必然是一圆弧,我们采用线圆结构的方法建立模型,用这种方法寻找可能的最短路径,然后采用穷举法列出O到目标点的最短路径.这其中我们不能仅仅考虑是经过障碍物拐点的问题〔例如由OABCO路径的计算>,也应该考虑经过路径中的目标点处转弯的问题,这是简单的线圆结构就不能解决这种问题,我们在拐点与途中目标点处采用最小转弯半径的形式,使机器人能够沿直线通过途中的目标点,然后建立优化模型对此问题进行优化,最终求得最短路径.2、问题二中涉与到机器人的速度问题,这样就不能以最短路径来进行计算,因为拐弯速度与直线速度不相同,这时就需要在加入速度因素,来求得最佳结果.三模型假设1 假设机器人能够抽象成点来处理.2 假设机器人在直线上或弧上均匀速行走.四 符号说明符号符号含义L出发点到目标点的路径长度r转弯半径R经过障碍物圆2处的转弯半径五 模型的建立与求解我们容易得知,起点到目标点无论中间障碍物有多少,最短路径都应该是若干个线圆结构组成.在本题中存在障碍物的状况,我们易知,在求两点之间的最短路径中的拐弯半径我们应该按照最小的转弯半径来计算才能达到最优,所以我们理解为在拐点处的危险区域是一个半径为10的圆弧.以下图为例,1〕 点圆模型 如上图,设A〔错误！未找到引用源.为起点,B〔错误！未找到引用源.为目标点,C〔错误！未找到引用源.和D〔错误！未找到引用源.分别为机器人经过拐点分别于隔离危险线拐角小圆弧的切点,圆心为O〔错误！未找到引用源.,圆的半径为r,AB的长度为a,AO的长度为b,BO的长度为c,角度=错误！未找到引用源., =错误！未找到引用源., =错误！未找到引用源.,.求A错误！未找到引用源.B的长度,设为L.解法如下：如上图可得有以下关系：：在：在中：所以：从而可得：我们就可以这样认为,起点到目标点无论中间障碍物有多少,最短路径都应该是若干个点圆结构所组成.在本题中存在障碍物的状况,且障碍物在拐点处的危险区域是一个半径为10的圆弧,所以结合上述结论,我们易知,求两点之间的最短路径中的转弯半径我们应该按照最小的转弯半径来算才能达到最优.2〕线圆模型 而对于下图两种情况我们不能直接采用线圆的结构来解决,需要做简单的变换. 情况一〔同向〕：这里我们依然设圆心坐标分别为和,半径均为r,这样我们可以得到：此段路径就是由两段狐与两段直线的组合加圆心距的总长.这样我们就可以利用1〕中的方法,先求A到E,再求D到B,最后减去DE的长度,这样分两段就可以求解.同理如果有更多的转弯,我们同样可以按照此种方法分解.情况二〔反向〕： 我们假设两圆心坐标分别为和,半径均为r,M点坐标为,那么我们很容易可以求得:M点坐标利用M将图上分解成两个线圆结构,利用上述方法进行计算,易得出结果.3〕圆心偏移模型在处理ＯＡＢＣ路径中,由于需要使ＡＢＣ处在路径上,所以寻找所对应弧的圆心,建立模型如图所示,E为O1O2的中点,图中的E为题中的ABC,O1为各点所在弧的圆心,利用LINGO找出使点落在最短路径上所对应的圆心,利用此圆心为拐点,用上述的方法进行计算.问题一一、 以下给出了机器人到个目标点的可能路径的最短路径：如下图就是机器人由O到目标点的最短路线 1〕O到目标点A的最短路径求解,通过计算,机器人从障碍物5的上方走的最短路径大于机器人从障碍物5下方走的最优路径,机器人行走的最优路线的可能性已经列出,附录中给出两种方案的求解结果. 最小结果对应的行走路路线乃是黑线所示,就是O到A的最短路径471.0372. 2〕O到目标点B的最短路径求解,我们在附录中给出三种路径的求解过程,分别为：〔1〕由O路过障碍物5,8到达B,如图中虚线所示（2） 由O路过障碍物6的上端,到7,8最后到达B点,如图中黑实线所示〔3〕由O路过障碍物6的下端,到7,8最后到达B点,图中间隔线所示.附录中给出三种方案的结果,最终比较得到最短路径为路径〔2〕即图中黑实线所示路径长度为869.8523.3） O到目标点C的最短路径求解,我们在附录中给出三种路径的求解过程,分别为：〔1〕由O路过障碍物5的上端,3,2,11到达C,黑线所示；〔2〕由O路过障碍物5的下端,到3,2,11最后到达C点,如图中虚线所示. 由附录中给出的结果,最终比较得到最短路径为路径〔1〕,图中黑实线所示,路径长度为1.0113e+003.4〕OABCO的最短路径求解,通过计算OA,OC,OB,我们容易得出OABCO的最短路径如下图所标,求解过程有两部分组成,先计算由O到N点的距离,再求N到O点的距离,最终结果为二者之和,结果为2649,6744.问题二设目标函数为由LINGO可得出所求,最短时间为94.22822,切点坐标〔69.80,211.98〕〔77.75,220.14〕圆心〔82.14,207.92〕.六、模型评价一、模型优点 1、模型优化后用解析几何,三角形中各个之间的关系进行求解,精确度较高.2、模型简单易懂,便于实际检验与应用.3、二、模型缺陷 1、此模型适于全局规划,获得精确解却失去了效率.2、在障碍物较多时,且形状不规则时,模型需要进一步改进. 3、在程序设计时,较复杂,需要繁琐的编辑过程.七、参考文献[1]韩新社 ,高等数学 ,合肥 ： 中国科学技术大学 2009.7[2]姜启源,数学模型［Ｍ］,：高等教育,2003.[3]谢金星 薛毅 ,优化建模与LINGO ,：清华大学,20##[4]刘来福 曾文艺 ,数学模型与数学建模, ：师范大学 2003.八、附录附录一：问题一中用matlab解一 OA长度求解1〕%求解一次转弯所经路线总长1 %O：初始点 E:转弯圆弧圆心 A:到达点 function result=zongchangOE=sqrt<-E<1>>^2+-E<2>>^2>;AE=sqrt<-E<1>>^2+-E<2>>^2>;OA=sqrt<-A<1>>^2+-A<2>>^2>;alpha1=acos</<2*AE*OE>>;alpha2=acos;alpha3=acos;alpha4=2*pi-alpha1-alpha2-alpha3;%alpha4为转弯圆心角result=sqrt+sqrt+r*alpha4;将〔0,0〕,〔80,210〕,〔300,300〕代入求得长度为ans = 471.03722 %O：初始点 F:转弯圆弧圆心 A:到达点 function result=zongchangOE=sqrt<-F<1>>^2+-F<2>>^2>;AF=sqrt<-F<1>>^2+-F<2>>^2>;OA=sqrt<-A<1>>^2+-A<2>>^2>;alpha1=acos</<2*AF*OF>>;alpha2=acos;alpha3=acos;alpha4=2*pi-alpha1-alpha2-alpha3;%alpha4为转弯圆心角result=sqrt+sqrt+r*alpha4;将〔0,0〕,〔230,60〕,〔300,300〕代入求得长度为ans = 498.42592〕计算OB路径1%O：初始点 E,F,G,H,D :转弯圆弧圆心 M,N：为距离中点 B:到达点 function result=zongchangOE=sqrt<-E<1>>^2+-E<2>>^2>;OF=sqrt<-F<1>>^2+-F<2>>^2>;EF=sqrt<-F<1>>^2+-F<2>>^2>;MF=sqrt<-F<1>>^2+-F<2>>^2>;ME=sqrt<-E<1>>^2+