精心整理机器人避障问题摘要本文研究了在一个800800⨯平面场景里，机器人通过直线和圆弧转弯，绕过障碍物，到达目标点的问题，解决了到达目标点路径最短，以及到达A 点时间最短的问题。

文章将路径划分为若干个这种线圆结构来求解。

对于途中经过节点的再到达目标点的状况，我们采用了在拐点和节点最小转弯半径的形式.O A →O →B O →C O →A →B 10个单位为50=v对场景图中4(1)(2)1.出发，分别做圆的切线，直到终点。

对于经过路径中的目标点的问题，我们采用最小转弯模式，建立优化模型，最终求的最短路径。

2．问题二要求从起始点到达A 点所用的时间最短，从题意以及生活经验可得，拐弯半径越大，所用时间越短，拐弯半径越小，所用时间越大。

半径最小不低于10，取最大值时机器人应刚好未碰到4、6三角形，可通过几何解法计算出来，并对时间进行优化处理。

三、模型假设假设机器人可以抽象成点来处理假设机器人的能源充足，且在整个行走过程中无故障发生四,符号说明】5（为起点，，OA圆弧的切点，角度1OO A ∠=,11OO M ∠=,11AO N ∠=，111M O N θ∠=.设这段路程机器人的总路程为L. 解法如下：如上图可得有以下关系：1 AOO ∆在中：在11Rt OO M ∆：222arccos(2b c a bcα+-=在11Rt AO N 中：所以：从而可得：结果如下：机器人行走路线1OM =1N A 弧11M N =224.7221；b=237.6973c=O 同理了解比较可得，O 从上面绕到到目标点A 的距离最短，最短路径为471.0372。

→2.O B→有多条路径，可以从O到正方形5的右下角直接到8的右上角，再绕到B。

1）O B2）可以从O到正方形5的右下角直接到8的右下角，再绕到8的左下角，绕到B。

3）可以从O到正方形5的左下角到左上角绕过6的右下角再8的右上角绕到B。

4）可以从O到正方形5的左下角到左上角绕过6的右下角再8的右下角，再绕到8的左下角，绕到B。

5）可以从O到三角形6的左下角再到三角形6的上顶点，绕到矩形7右下角，到矩形7右上角，再到8的右上角，绕到B。

6）可以从到8图2第二、第三、→只不过增加了路径的长度和情况。

经上面分析发现，机器人行走路线与出发点到目标与上面两种情况类似，O C点连线段越近，越趋于最短路。

于是，我们着重看了以下几种情况：1）可以从O到三角形4右下角绕到矩形12左上角，到正方形11右下角，到11右上角，再绕到C。

2）可以从O到正方形5左上角绕到3左上角，到圆2，到11右下角，到11右上角，再绕到C。

O→→在这个过程中，机器人不仅要绕过障碍物，还要经过A B C、、三点，以A点为例，在经过A点时，机器人要转弯，转弯圆弧要经过A，圆弧以10为半径。

在此，要用到准备知识2.二、最短时间路径根据题目和经验判断，拐弯越大速度越快，也就是拐弯时半径可以增大，但不能碰到上面的三角形。

所以对半径有范围要求。

最大半径的确定：图(150,435) G，(235,300)M由此能够计算出GM的直线方程，D的纵坐标为290，由直线方程可以判断出D的横坐标。

D那么AD6.1n边算法6.21线。

于是我们对模型做了以下修正：1、检验切线两个端点是否在障碍物内部。

2、检验切线是否障碍物的对角线相交。

3、检验圆弧所对应的圆心，即障碍物的顶点到切线的距离是否小于1。

如果以上三种情况满足其一，我们规定对应这段切线的顶点为M（M为无穷大）。

4、另外还有如下图所示的一种特殊情况：两个大小相同在同一水平或者竖直位置上，不考虑切线满足1、2、3的状况它们由2条内公切线，8条外公切线，但是有6条外公切线是重复的。

因此我们作如下规定:如果某条切线与某段圆弧相切，且切点不在切线的端点上，则该切线为不合法。

权值矩阵中表示它的顶点也为M 。

转化成如7.21所示的形式。

假设转化过后有m 条合法切线，那么就有m 个顶点，设这些点的权值i E （1i m ≤≤），即第i 条合法曲线的长度。

j D 为边的权值，即第j 条弧的长度。

3）然后把路径图转化成如图6.21所示，按照求得权值矩阵给图中的顶点及边长赋值。

4）最后依据Dijkstra 算法求得最短路径。

七、模型评价一、模型优点1、运用多个方案对路径进行优化，在相对优化之中取得最优解。

2、模型优化后用解析几何进行求解，精确度较高。

3、3、模型简单易懂，便于实际检验及应用。

45、12[1][2]4][5][6][7]年 出版社《数附录1>>x1=0;>>y1=0;>>x2=80;>>y2=210;>>x3=300;>>y3=300;>>a=((x2-x1)^2+(y2-y1)^2)^(1/2);>>b=((x3-x2)^2+(y3-y2)^2)^(1/2);>>c=((x1-x3)^2+(y1-y3)^2)^(1/2);>>a,b,ca=224.7221b=237.6973c=424.2641>>q=acos((b^2+a^2-c^2)/(2*b*a))q=2.3231>>R=10;>>r=acos(R/a);>>s=acos(R/b);L=471.0372附录2>>%1为%6为X1=0;Y1=0;X2=60;Y2=300;X3=150;Y3=435;X4=220;Y4=470;X5=220;Y5=530;X6=150;Y6=600;X7=100;Y7=700;r=10;h=acos(r/a);q=acos((a^2+b^2-c^2)/(2*a*b));%OCD度数t1=2*pi-q-h-1/2*pid=[((X4-X3)^2+(Y4-Y3)^2)^(1/2)]/2;%DE/2的长u=(d^2-r^2)^(1/2);%MH(MP/2)的长J=2*ui=acos(r/d);e=((X4-X2)^2+(Y4-Y2)^2)^(1/2);%CE的长p=acos(((2*d)^2+b^2-e^2)/(2*(2*d)*b));t2=2*pi-p-i-1/2*pif=((X5-X3)^2+(Y5-Y3)^2)^(1/2);%FD的长g=((X5-X4)^2+(Y5-Y4)^2)^(1/2)%FE的长z=acos(((2*d)^2+g^2-f^2)/(2*d*2*g));h=acos(r/d);t3=2*pi-z-h-1/2*pii=((X5-X6)^2+(Y6-Y5)^2)^(1/2);%GF的长j=((X4-X6)^2+(Y6-Y4)^2)^(1/2);%GE的长y=acos(r/i);x=acos((i^2+g^2-j^2)/(2*i*g));t4=2*pi-y-x-1/2*pil=2*((i/2)^2-r^2)^(1/2)%SW的长b=162.2498t1=0.4233J=75.6637t2=0.7776g=60t3=1.3656t4=0.8866l=96.9536t5=1.2267I=111.3553H=305.7777L=816.6798附录3>>%1为O(0，0)2为D3为E4为F5为G6为H7为CX1=0;Y1=0;X2=180;Y2=210;X3=400;Y3=330;X4=550;Y4=450;X5=720;Y5=520;X6=720;Y6=600;X7=700;Y7=640;r=10;r2=80;i=((X6-X5)^2+(Y6-Y5)^2)^(1/2)%HG的长k=((X6-X4)^2+(Y6-Y5)^2)^(1/2);%HF的长q7=acos((j^2+i^2-k^2)/(2*j*i));t4=2*pi-q7-1/2*pi-1/2*pim=((X7-X6)^2+(Y7-Y6)^2)^(1/2);%CH的长n=((X7-X5)^2+(Y7-Y5)^2)^(1/2);%CG的长p=(m^2-r^2)^(1/2)%CT的长q8=acos((m^2+i^2-n^2)/(2*m*i));q9=acos(r/m);t5=2*pi-q8-q9-1/2*pi精心整理页脚内容L=d+t1+b+t2+g+t3+j+t4+i+t5+p b=250.5993d=276.4055t1=0.3990g=249.7999t2=0.2797t3=1.7187i=80t4=1.7382p=43.5890t5=0.6892L=>>。