机器人避障问题的最短路径分析

1、机器人避障问题的最短路径分析摘要本论文研究了机器人避障最短路径和最短时间路径的问题。主要讨论了在一个区域中存在12个障碍物，由出发点到达目标点以及由出发点经过若干目标点最终到达出发点的两种情况。采用传统的避障方法切线图法。建立了线圆结构，这样任何路径，我们都可以将路径划分为若干个这种线圆结构来求解。对于途中经过节点再到达目标点的状况，我们采用在转弯点和节点都采用最小转弯半径，以节点为切点的形式。然后建立了最优化模型，利用MATLAB软件对方案进行求解。问题一：把路径分解成若干个线圆结构来求解，然后把可能的最短路径采用穷举法列举出来，最终得出最短路径： 最短路径为：471.0 最短路径为：869

2、.5 最短路径为：1093.3对于 我们将A、B、C看作切点，同样采用线圆结构计算。 最短路径为：2827.1问题二：考虑避障路径和转弯速度，我们建立时间与路径之间的模型，用MATLAB软件求出最优解。当转弯半径为11.5的时候，可以得出最短时间为：T=94.3关键词 最优化模型 避障路径 线圆结构 切线图法一、问题重述本文是求一个机器人在800×800的平面场景图中避开障碍物，建立从原点O(0, 0)点处出发达到终点的最短路径和最短时间路径的模型。即求：1、OA、OB、OC和OABCO的最短路径。2、OA的最短时间路径。 机器人在行走时的要求是：1、它只能在该平面场景范围内活动2、

3、图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物（障碍物的分布如图1）3、障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）。4、规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。5、为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞。机器人直线行走的最大速度为个单位/秒。机器人转弯时，最大转弯速度为，其中是转弯半径。已知场景图中4个点O(0, 0)，A(300

4、, 300)，B(100, 700)，C(700, 640)。图中各个点的坐标见下表。 图1编号障碍物名称左下顶点坐标其它特性描述1正方形(300, 400)边长2002圆形圆心坐标(550, 450)，半径703平行四边形(360, 240)底边长140，左上顶点坐标(400, 330)4三角形(280, 100)上顶点坐标(345, 210)，右下顶点坐标(410, 100)5正方形(80, 60)边长1506三角形(60, 300)上顶点坐标(150, 435)，右下顶点坐标(235, 300)7长方形(0, 470)长220，宽608平行四边形(150, 600)底边长90，左上顶点坐

5、标(180, 680)9长方形(370, 680)长60，宽12010正方形(540, 600)边长13011正方形(640, 520)边长8012长方形(500, 140)长300，宽60 二、模型假设1、把机器人抽象成质点。2、机器人直线行走都是以最大速度做匀速运动。3、机器人转弯时同样以最大允许速度做匀速运动。3、 符号说明 符号符号说明 每一个线圆结构起点到终点的长度每一个线圆结构起点到圆心的长度每一个线圆结构终点到圆心的长度转弯半径（即题上的）转弯圆心角转弯圆心坐标A到Z各个切点，节点的坐标 每个弧长的长度第i段直线段的长度第j段圆弧的长度第i段直线段所用的时间第j段圆弧所用的时间d

6、障碍物上的任意点与行走路径之间的最短距离四、模型分析与准备一、最短路径和最短时间路径的分析 （1）问题一：要求从出发，沿,和的行走路线按照一定规则，绕过障碍物到达目标点的最短路径。在求，时。我们将所有的障碍物扩大10个单位，在障碍物的顶点处，就是以10为半径圆弧。我们采用拉绳子的方法寻找所有可能的最短路径。然后利用线圆结构的方式求解。即列举法。（例如求解O到A的最短路径，我们就可以连接和之间的一段绳子，以障碍5左上角的拐角处的圆弧为支撑拉紧，那么这段绳子的长度便是到的一条可能的最短路径）。在求时，在过点、处我们采用最小半转弯的方式，使机器人经过这些过点时，都是按圆弧通过。其他情况就是按线圆结构

7、的方式进行求解。 （2）问题二、要求从O点出发到达A点的最短时间路径问题，采用穷举法和CAD画图可以得出最短时间路径。二、在模型的建立中会大量用到线圆结构来计算，证明起点到终点之间最短的路径就是我们所用的线圆结构。证明：如图所示的线圆结构,和圆弧之和为最短避障路径。 假设在平面中有和两点，中间有一个半圆形的障碍物，证明从到的最路径为圆弧和线段、的和。 图2平面上连接两点最短的路径是通过这两点的直线段，但是连接两点的线段被障碍物遮挡，所以设法尝试绕过障碍物的折线路径。在y轴上取一点，若y适当大，当折线与障碍物相切时，是这种折线路径中最短的。由于满足的角满足,所以易知弧度小于的长，即证明到了线圆结

8、构为最短避障路径。线圆结构的长度： 设， 为起始点，为目标点，。求OA，设为L。 ： ： 因为所以： 从而可得： 六、模型的建立与求解 假设机器人从起点R到到目标点，由图2知路径一定是由圆弧和线段组成，设有m条线段，n条圆弧。那么最短路程：用此模型就可以对起点到目标点之间的路径进行优化求解。 时间模型： 问题一：1、由以上模型采用穷举法知从的路径线路通过简化有如下两种情况，分别为，如图3：已知O(0，0)，D(80，210)，A(300，300) 图3 用MATLAB软件算得：OA的路径为：471.0372所以：OA的最短路径为图3其结果为：471.0372 2、通过穷举法分析知采用如下图6所

9、示路线可以可以算出OB的长度。 设D到M点的坐标分别为（）i= 1.10； Q1到Q5表示为绕过的各个障碍物的圆心设坐标为（）j=11.15； 表示各直线相交的夹角； 类似的采用以上的算法可以得到如下直线的长度： 图6 则：夹角为 所以OB所走路线的,弧线长度为： 每个线圆结构起点到终点，起点到圆心，圆心到终点的距离： （j=1,2,3,4,5）故，OB的最短路径的目标函数为: 通过软件计算知 :的最短路径是869.4332 3、在通过分析知OC的最短路径为图5所示，通过visio画图得到如下图所示：设其中j为1到4的整数，。A.B.J.I.D.K.E.F.G.H的坐标分别为（）其中i为5到1

10、4的整数，M().各个点之间的关系：J点坐标 K点坐标 G点坐标 F点坐标我们将O到C分成五个线圆结构，根据上述模型分析可以得到：:所以:所以通过MATIAB软件编程可以算出：OC的最短路径为：1093.301 图5 4、通过分析可知OABCO的最短路径为如下图7所示： 图7因为OABCO的路线简化成由16个线圆结构组成的 : FL： LB： KN： MQ： Qt： SV： VY： XT： Tq：为了简化模型，我们假设A、B、C点为切点。因为OA和OC在前面已经计算了最短值所以 综上所述可得各个点的坐标：OC的坐标为： 圆弧圆心 (230，60) (410，100) (500,200) (72

11、0,520) （720,600） 切点 （422，90） （428.7，94.5) (492，206） （727.6，514） （730,520） （730,600） (727.8，606.3)OB的坐标为： 圆心 （60,300） (150,435) (220,470) （220,530） （150,600） 切点（50.13，301.06） （51.7，305.5） （141.7，439.6） （230,530) （150,444.03） （222.1，460.2） （140.7,596.3） （230,470） (225.5，538.3) （144.5，591.6） OA的坐标为：圆心（

12、80,210） 切点（70.5，213） （76.6，219.4）的坐标圆弧切点（70.5,213.1） （76.6，219） （291.07,297.78） （297.25,309.08）（229.25,532.9） （225.5,538.35） （144.5,591.64） （140.7,596.35）（105.7,685.4） （115.6,699） （270.6,689.9） （272,689.8）（366.7 ，670.3） (533.9 ，738.3) （699.4 ，642.3） （369.3 ，670） （539.6 ，740） （429.3， 670） （539.5 ，740

13、） （435.1 ，671.8） （679.3 ，732.18）圆心（80， 210） （287.68 ，306.18） （220 ，530） （150,600）（115.02，639） （270,680） （369.3 ，680） （429.3 ，680） （539.5 ，730） （669.5 ，730） （709.2 ，644.5） 问题二：通过分析采用图9的路线可以得出最短时间路径如图所示： 图9是O到A的最短时间路径 其中C点，B点分别是直线与圆弧的两个切点：CB长度是d。 直线的斜率为，直线的斜率为。所以直线的方程：·····

14、83;·························(1)直线的方程：·······················

15、·······(2)将式子(1)和式子(2)连理求解可以得到圆心坐标。圆弧所对的圆心角为 由到角公式可知：···································&#

16、183;(3)因为,所以有两直线垂直那么其斜率相乘等于零。因此：············································

17、3;·(4) ················································

18、··(5)在中显然有····································(6)将式子(3)、(4)、(5)、(6)连理求解可以得到和由于转弯的的半径还受到障碍物5和障碍物6的影响，所以切点的半径有限制

19、范围，通过计算可限制切点的半径范围： 又因为D点必须在两条切线的内侧，所以我们通过 的斜率大于;的斜率小于来限制。即： 所以最短时间可以表示为：以上式子用MATLAB求解得到最短时间为：95.4332秒在上面的模型中是圆心固定算出半径是11.5，如果不固定圆心O1，那么圆心的范围就是一个以O点为圆心，1.5为半径的小圆内部的点。为了方便起见将圆心O1坐标的取值定在小圆的内切正方形里面。然后利用上面的模型加上（7）式的约束条件可以在这个小正方形里面找到最优解。 ···········&#

20、183;······································（7）上面式子的程序再加上（7）这个约束条件用MATLAB求解得到最短时间为：94.3秒.两个切点坐标 七、模型评价（一）优点：1.文章

21、中的计算过程皆运用数学软件求解，且求解过程简洁，使得出的数据更具有说服力；2.本文通过对问题的充分分析，在合理的假设情况下，建立了具有科学性的方程模型；3.运用本文模型求解相关问题时结果与实际情况基本相吻合；（二）缺点：问题（一）中其他几问的算法基本上同OA的算法一致，数据较大，在处理时存在一定的误差，但误差在允许的范围内，可以接受。八、模型检验与推广 本文是利用传统方法切线图法求解切线图法用障碍物的切线表示弧，此时移动机器人必须接近障碍物，在有误差的时候可能与障碍物有接触，但解决了障碍物不能是圆形的问题。我们可以采用基于遗传算法与人工神经网络的智能避障算法。九、参考文献1 2 阳明盛，熊西文

22、，林建华，MATLAB基础及数学软件，大连：大连理工大学出版社，2003年。3移动机器人避障方法综述 作者 牢常健， 吴成东， 李斌 科学院沈阳动化研究所机器人学田家重点实验室；中嗣科学院研究生院；东 北大学信息科学与工程学院十，附录附录一；为最短路线OA 的程序，是利用MATIAB求解的%0：初始点 D:转弯圆弧圆心 A:到达点 r:表示圆弧半径function result=zongchang1(r)O(1)=0;O(2)=0;A(1)=300;A(2)=300;D(1)=80;D(2)=210;OD = sqrt(O(1)-D(1)2+(O(2)-D(2)2);OA=sqrt(O(1)-

23、A(1)2+(O(2)-A(2)2);AD=sqrt(D(1)-A(1)2+(D(2)-A(2)2);alpha1=acos(OD2+AD2-OA2)/(2*OD*AD);alpha2 = acos(r/OD);alpha3 = acos(r/AD);alpha4=2*pi-alpha1-alpha2-alpha3;%alpha4为转弯圆心角OS1=sqrt(OD2-r2);%OS1,AS2均为圆弧切线%S2A=sqrt(AD2-r2);S1S2hu=r*alpha4;result=OS1+S1S2hu+S2A;endzongchang1(10)ans = 471.0372附录二；为最短路线O

24、B的程序，是利用MATIAB编程的O-F%求解一次转弯所经路线总长%0：初始点 Q1:转弯圆弧圆心 F:到达点 r:表示圆弧半径function result=zongchangob1(r)O(1)=0;O(2)=0;F(1)=141.675;F(2)=440.55;Q1(1)=60;Q1(2)=300;OQ1 = sqrt(O(1)-Q1(1)2+(O(2)-Q1(2)2);OF=sqrt(O(1)-F(1)2+(O(2)-F(2)2);FQ1=sqrt(Q1(1)-F(1)2+(Q1(2)-F(2)2);alpha1=acos(OQ12+FQ12-OF2)/(2*OQ1*FQ1);alph

25、a2 = acos(r/OQ1);alpha3 = acos(r/FQ1);alpha4=2*pi-alpha1-alpha2-alpha3;%alpha4为转弯圆心角OD=sqrt(OQ12-r2);%OD,FE均为圆弧切线%EF=sqrt(FQ12-r2);DEhu=r*alpha4;result=OD+DEhu+EF;end zongchangob1(10)F-P%求解一次转弯所经路线总长% E：初始点 Q2:转弯圆弧圆心 P:到达点 r:表示圆弧半径function result=zongchangob1(r)E(1)=51.675;E(2)=305.5;P(1)=185;P(2)=4

26、52.5;Q2(1)=150;Q2(2)=435;EQ2 = sqrt(E(1)-Q2(1)2+(E(2)-Q2(2)2);EP=sqrt(E(1)-P(1)2+(E(2)-P(2)2);PQ2=sqrt(Q2(1)-P(1)2+(Q2(2)-P(2)2);alpha1=acos(EQ22+PQ22-EP2)/(2*EQ2*PQ2);alpha2 = acos(r/EQ2);alpha3 = acos(r/PQ2);alpha4=2*pi-alpha1-alpha2-alpha3;%alpha4为转弯圆心角EF=sqrt(EQ22-r2);%EF,PG均为圆弧切线%PG=sqrt(PQ22-r

27、2);FGhu=r*alpha4;result=FGhu+PG;endP-J%求解一次转弯所经路线总长% P：初始点 Q3:转弯圆弧圆心 J:到达点 r:表示圆弧半径function result=zongchangob1(r)J(1)=230;J(2)=530;P(1)=185;P(2)=452.5;Q3(1)=220;Q3(2)=470;PQ3 = sqrt(P(1)-Q3(1)2+(P(2)-Q3(2)2);JP=sqrt(J(1)-P(1)2+(J(2)-P(2)2);JQ3=sqrt(Q3(1)-J(1)2+(Q3(2)-J(2)2);alpha1=acos(JQ32+PQ32-JP

28、2)/(2*JQ3*PQ3);alpha2 = acos(r/PQ3);alpha3 = acos(r/JQ3);alpha4=2*pi-alpha1-alpha2-alpha3;%alpha4为转弯圆心角JI=sqrt(JQ32-r2);%JI,PH均为圆弧切线%PH=sqrt(PQ32-r2);HIhu=r*alpha4;result=PH+HIhu+JI;endJ-q%求解一次转弯所经路线总长% P：初始点 Q3:转弯圆弧圆心 J:到达点 r:表示圆弧半径function result=zongchangob1(r)J(1)=230;J(2)=530;P(1)=185;P(2)=452.

29、5;Q3(1)=220;Q3(2)=470;PQ3 = sqrt(P(1)-Q3(1)2+(P(2)-Q3(2)2);JP=sqrt(J(1)-P(1)2+(J(2)-P(2)2);JQ3=sqrt(Q3(1)-J(1)2+(Q3(2)-J(2)2);alpha1=acos(JQ32+PQ32-JP2)/(2*JQ3*PQ3);alpha2 = acos(r/PQ3);alpha3 = acos(r/JQ3);alpha4=2*pi-alpha1-alpha2-alpha3;%alpha4为转弯圆心角JI=sqrt(JQ32-r2);%JI,PH均为圆弧切线%PH=sqrt(PQ32-r2);

30、HIhu=r*alpha4;result=PH+HIhu+JI;endq-B%求解一次转弯所经路线总长% q：初始点 Q5:转弯圆弧圆心 B:到达点 r:表示圆弧半径function result=zongchangob1(r)B(1)=100;B(2)=700;q(1)=185;q(2)=565;Q5(1)=150;Q5(2)=600;BQ5= sqrt(B(1)-Q5(1)2+(B(2)-Q5(2)2);Bq=sqrt(B(1)-q(1)2+(B(2)-q(2)2);qQ5=sqrt(Q5(1)-q(1)2+(Q5(2)-q(2)2);alpha1=acos(BQ52+qQ52-Bq2)/

31、(2*BQ5*qQ5);alpha2 = acos(r/qQ5);alpha3 = acos(r/BQ5);alpha4=2*pi-alpha1-alpha2-alpha3;%alpha4为转弯圆心角BM=sqrt(BQ52-r2);%BM,qL均为圆弧切线%qL=sqrt(qQ52-r2);LMhu=r*alpha4;result=qL+LMhu+BM;endfunction oc (a,b,c,d,e);sum5 = zongchangob0F(10)+zongchangobFP(10)+zongchangobPJ(10)+zongchangobJq(10)+zongchangobqB(1

32、0)869.4896附录三；为最短时间路线OA的程序（圆心固定时），是利用MATIAB编程的f>%是假设圆心固定所得出的模型%E：初始点 F:转弯圆弧圆心 G:到达点 for i=1:7000; r(i)=10+0.01*i;E(1)=0;E(2)=0;F(1)=80;F(2)=210;G(1)=300;G(2)=300;EF=sqrt(E(1)-F(1)2+(E(2)-F(2)2);%bEG=sqrt(E(1)-G(1)2+(E(2)-G(2)2);%aFG=sqrt(F(1)-G(1)2+(F(2)-G(2)2);%calpha1=acos(EF2+FG2-EG2)/(2*EF*FG

33、);% alpha1为起始点与圆心连线的夹角alpha2=acos(r(i)/EF);% alpha2为起点到圆心与切点连线的夹角alpha3=acos(r(i)/FG);% alpha3为起点到圆心与切点连线的夹角alpha4=2*pi-alpha1-alpha2-alpha3;%alpha4为转弯圆心角ES1=sqrt(EF2-r(i)2);%ES1,ES2均为圆弧切线%S2G=sqrt(FG2-r(i)2);S1S2hu=r(i)*alpha4;L(i)=ES1+S1S2hu+S2G;%总路程a(i)=ES1/5+S2G/5+S1S2hu*(1+exp(10-0.1*r(i)2)/5;%总时间endmintime=min(a) %最小时间k=find(a=mintime)r(k)%最小时间时候的半径L(