机器人避障问题的解题分析(建模集训)

1、机器人避障问题的解题分析摘要：本文对2012年全国大学生数学建模竞赛D题机器人避障问题进行了全面分析，对最短路的设计进行了理论分析和证明，建立了机器人避障最短路径的几何模型，对最短时间路径问题通过建立非线性规划模型，有效地解决了转弯半径、圆弧圆心位置和行走时间等问题。关键词：机器人避障；最短路径；Dijkstra算法；几何模型；非线性规划模型1引言随着科学技术的进步和计算机技术的发展，机器人的应用越来越广泛，在机器人的应用中如何使机器人在其工作范围内为完成一项特定的任务寻找一条安全高效的行走路径，是人工智能领域的一个重要问题。本文主要针对在一个场景中的各种静态障碍物，研究机器人绕过障碍物到达指定目的地的最短路径问题和最短时间问题。本文以2012年“高教社”杯全国大学生数学建模竞赛D题“机器人避障问题”为例进行研究。假设机器人的工作范围为800X800的平面正方形区域（如图1）,其中有12个不同形状的静态障碍物，障碍物的数学描述（如表1）:表1编R障碍物名称左卜顶点坐标其它特性描述1止方形(300,400)边长2002圆形圆心坐标（550,450）,半径703平行四边形(360,240)

2、底边长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,左上顶点坐标（180,680）9长方形(370,680)长60,宽12010止方形(540,600)边长13011止方形(640,520)边长8012长方形(500,140)长300,宽60在原点0（0,0）点处有一个机器人，它只能在该平面场景范围内活动，机器人不能与障碍物发生碰撞，障碍物外指定一点为机器人要到达的目标点。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。机器人直线行走的最大速

3、度为V05个单位/秒。机器人转弯时，最大转弯速度为,、v0Vv().1000.12(是转弯1e,C(700, 640),下面我们半径）。如果超过该速度，机器人将发生侧翻，无法完成行走。场景图中有4个目标点0(0,0),A(300,300),B(100,700)将研究机器人从0（0,0）出发，求8AO-B、85口O-ZBO勺最短路径，以及机器人从0（0,0）出发，到达A的最短时间路径问题。2静态避障问题中机器人行走最短路径的分析行走路径的设计在本例中障碍物有4种不同形状：矩形、平行四边形、三角形和圆形。考虑到机器人本身的形状和大小，为研究方便起见，将机器人视为一个点。机器人与障碍物之间的距离至少为10个单位，因此可以先用包络线画出机器人行走的危险区域（如图2）,包络线内是机器人的禁入区。图2障碍物包络图对障碍物的一个角点来说，其禁入区的边界应由两条直线和一条圆弧组成，两条直线分别平行于角点的两条边，间距为10个单位，圆弧是以障碍物角点为圆心，半径为10个单位的四分之一圆弧。可以证明具有圆形限定区域的最短路径由两部分组成，一部分是平面上的自然最短路径（直线段），另一部分是限定区域的部分边界

4、（即绳子拉到最紧时的圆弧部分）：这两部分是相切的，互相连接（如图3所示）。由A绕过半圆形障碍物到达B点的路径有多条，其中最短路径为AEFB（E、F为切点），其他路径与AB直线围成的区域都覆盖这一路径与AB直线围成的区域，由此证明1。圆弧半径r为何值，才能使由此可以确定机器人的行走路径应为线圆结构，那么是否是转弯半径越小，行走路径就越短呢为此需要求在已知两个固定点和圆弧圆心坐标的情况下,机器人的行走路径最短。如图4,C Xi,yi ,dAC已知两个固定点 A a1,b1 ,B a2,b2 ,圆心OX2，y2 ,设半彳仝为r ,圆弧CD所对的圆心角为BD222XiaiyibiX2 a2Y22b2将路径函数L对r求导，得L,yi arctan 一Xibia1arctan因为x1a11ylb1,arctan y1Xibim,n ,可以求得两切点坐标B的路径长度为L,yi bi,y2b2arctan arctan XiaiX2a2y2b2x2 a2y b20, x2 a2,y2 b2,arctanx2 a20,所以L 0.机器人的行走路径0,则函数L为单调递增函数，因此当圆弧半径r逐渐增加时,会

5、增大,r逐渐降低时，机器人的行走路径会减小2,本题规定转弯半径最小为10个单位,所以在路径设定时应将转弯半径设定为最小值10个单位。根据以上分析，对于静态障碍物机器人的行走路径应遵循以下三个原则：原则一：机器人的行走路径为线圆结构，由两条切线和一段圆弧组成；原则二：每个路口至多发生一次转弯，并以障碍物顶点为转弯圆弧的中心；原则三：机器人转弯圆弧半径为最小允许半径10个单位。最短路径的选择从起点到达目标点有多条路径，根据Dijkstra算法可以找出从起点到达每一个目标点的最短路径。本文采用带权的有向图表示机器人的行走路径，途中节点为障碍物的角点，边表示障碍物之间的联系，权表示线路的长度（节点之间的直线距离）。从顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径就是所求最短路径，Dijkstra算法就是按路径的长度递增次序产生最短路径的算法3。下面以OB为例，确定OB的最短路径。如图5所示，根据障碍物的形状和位置，本文给出了机器人从0（0,0）出发避过障碍物到达目标B点的4条较优路径。8006004002002004006UU800画出OB的非循环网络图（如图6）：

6、图6运用Dijkstra算法算出OB的最短路径，最短路算法如下：1、起点。记为B0,终点B记为Bn；2、从网络白终点Bn开始，令它的标号n为零，并用方框记录在图6中；3、计算结点Bi的标号i,设结点Bj已标号，结点Bi指向Bj,则Bi的标号可按算式：iminil(i,j)求出，其中i是Bi的标号，li,j是结点Bi与Bj之间的直j线距离；4、重复上述计算，直到求得起点氏的标号0为止，此标号0即为最短路的长度；5、确定最短路径，从起点开始，顺网络的箭线前进，若有几条箭线，则选取箭线所指标号最小且?t足条件jklj,k,kj1的结点为最短路径所经过的结点。在图6中，最短路径为：OB3B5B6B7B8B.应用上述算法可得到从。点出发，分别到达各目标点的最短路径：80060040020U200400600800A的最短路径为:OA2A（如图7）8u0600400EDO&UU800图8C的最短路径为:（如图8）ABCO的最短路径为：OAABlB2BB3c103c4c5cC8c7OiO2O3O3最短路径计算模型单个目标点的最短路径根据前面制定的行走路径原则，起点到目标点无论中间障碍物有多少，最短路

7、径都应该是若干个线圆结构所组成，圆弧中心为障碍物的顶点，半径为机器人转弯最小半径10个单位。观察这四条路径，发现所有行走路径都可归结为以下三种类型：类型一图10线圆结构1如图10,设。(X1,y1)为起点，A(X2,y2)为目标点，c和D分别为直线与转弯圆弧的切点，障碍物的顶点M(x3,y3)(即转弯圆弧的圆心)，圆的半径为r,OA的长度为a,OM的长度为b,AM的长度为c,OMA,OMc,AMD,cMD设OA的长度为L,则LOcADcD,由图10可得以下关系：a,(X2X1)2(y2y1)2b.(X3X1)2陋y1)2cJX3X2)2(yy2)2在OMA中：1222bcaarccos()2bc在RtOMc中：rarccos-b在RtAMD中：rarccosc所以：2从而可得：Lb2r2c2r2r这个模型运算简洁，只需将起点、目标点和障碍物顶点坐标输入模型，MATLAB就能很快计算出来4,计算程序见附录1。类型二：对于图11这种线圆结构，需要做简单的变换，才能求出AB的路径长度。图11线圆结构2假设两圆心坐标分别为O(x1,y1)和O(x2,y2),M点为两圆心连线和两圆公切线的交点，

8、坐标为M(X3,心),那么很容易可以求得X3y3X1X22%丫22这样就可以利用类型一中的方法，先求A到M的长度，再求M到B的长度，分两段就可以求解。同理如果有更多的转弯，同样可以按照此种方法分解。类型三r.1图12线圆结构3如图12,如果两圆弧的公切线平行于两圆圆心连线，求AB的路径长度。设各点坐标分别为起点A(x1,y1),目标点B(x2,y2),障碍物顶点O(x3,y3)，障碍物顶点O(x4,y5),半径为r,a,b,c,d,e分别是AO,OO,AO,BO,BO的长度，AOO1,AOC1,COD1,BOO2,BOF2,EOF2设AB的长度为L,则LACCDOOEFFB解法如下：由图12,可以得到以下关系：a=.(x4x1)2(y4y1)2,b=(Mx3)2(y4y3)2,c=,(x3x1)2(y3y1)2,d,(x3x?)2也y?)2,e(x4x2)2(y4y2)2在AOO中，由余弦定理可得：.222bca1arccos2bc在RtAOC中，r1 =arccos-c一3所以：1112同理:,22,2bedr32 arccos；2=arccos;2222bee2LACCD|OO|EFFB，c2r2r1+b+r2+Je2r2c2,2222,2223cbar、1,3bedr22=.cr+r(arccosarccos-)br(arccosarccos-)er22bcc22bee运用MATLABS行计算，MATLAB十算程序见附录2.多个目标点的最短路径机器人从起点出发，依次经过指定的中间目标点最后到达终点，是多个目标点的最短路径问题。比如0ABeO的最短路径的计算。由于机器人的行走路线为线圆结构，不能折线转弯，因此中间目标点应位于某个半径为r的圆周上，这里

《机器人避障问题的解题分析(建模集训)》由会员re****.1分享，可在线阅读，更多相关《机器人避障问题的解题分析(建模集训)》请在金锄头文库上搜索。