数学建模机器人避障

2012高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何形式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导老师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果获其他公开的资料（包括网上查询到的自资料），必须俺不找规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严重遵守竞赛规则，以保证竞赛的公正性、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文一任何形式公开（包括进行网上公示，在书籍，期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：D题我们参赛报名号为（如果赛区设置报名号的话）：13277001所属学校（请填写完整的全名）：长江职业学院参赛队员（打印并签名）：1.何宝宝2.舒鑫鑫3.黎成硕指导老师或知道教师组：陶燕芳胡芬侯谦民日期：2012年9月7日赛区评阅编号（有赛区组委会评阅前进行编号）：2012高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1机器人避障问题的研究摘要本文主要研究了机器人在一定的区域中，且存在多个障碍物的情况下，由出发点到达目标点，以及由出发点经过途中的多个目标点最后回到出发点的两种情况。由于最短路径一定是由圆弧和与之相切的直线组成，因此我们将路径划分为若干个这种线圆结构来求解。问题一：对存在障碍物的两点之间，利用平面几何原理建立最短路程的模型，并用Matlab计算出两点之间可能存在的所有最短距离，然后整理这些距离，最后利用图论中的最短路的算法求得最优解。其次通过对几何原理的分析，同时结合CAD软件计算出机器人从起点出发经过多个目标点最后回到起点的最短路径。结果如下：O→A最短路径为：471.0372O→B最短路径为：853.1121O→C最短路径为：1130.281O→A→B→C→O最短路径为：1884.149问题二：对于问题二，我们讨论了较简单的一种情形，即当圆心固定，半径变化时。在这种情形下，我们利用解析几何法建立了时间与半径之间的函数关系，并使用两种方法对函数进行求解。（1）直接利用Matlab软件绘出了函数图形，并求出了最优解，即当ρ=11.5038时，时间取到最小值T=94.5649。（2）尝试用鱼群算法求出了函数的最优解，最优解为ρ=11.5042T=94.9106，由比较可知两种算法的结果非常接近。关键词：最短路径、穷举法、解析几何、最优化模型、鱼群算法、超越函数2一、问题重述表1是一个800×800的平面场景图，在原点O(0,0)点处有一个机器人，它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述如下表。表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，左上顶点坐标(180,680)9长方形(370,680)长60，宽12010正方形(540,600)边长13011正方形(640,520)边长8012长方形(500,140)长300，宽60在表1的平面场景中，障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。机器人直线行走的最大速度为=5个单位/秒。机器人转弯时，最大转弯速度为=(ρ)=.，其中ρ是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中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的最短时间路径。注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。3二、问题的分析问题一：要求求定点O（0,0）按照一定的行走规则绕过障碍物到达目标点的最短路径，我们先可以画出机器人行走的危险区域，这样的话，拐角处就是一个半径为10的圆弧。通过采用模拟作图的方法找出可能的最短路径（比如求O和A之间的最短路径，我们可以连接O和A之间的一段绳子，以拐角处的圆弧为支撑点拉紧，那么这段绳子的长度便是O到A的一条可能的最短路径），然后采用穷举法列出O到每个目标点的可能的最短路径。可以将原图中的几何图形单独拿出来转化为线圆模型，将机器人转弯圆弧以最小半径行走，并将直线距离转化为切点与已知点之间的距离。要求出最短路径需要求出起始点，拐点圆心，拐点圆心之间的中点和终点。根据CAD画图确定各个切点的坐标，再根据Matlab编程算出距离总长。最后比较其大小便可得出O到目标点的最短路径。问题二：此问要求在时间最短的情况下求从出发点到达A点的路径。此问我们讨论了较简单的情形，即当圆心固定在障碍物5的顶点上，而拐弯半径发生变动的情形。通过问题一的分析，我们将圆心选定在正方形的左上顶点(80,210)处。通过平面几何原理，我们建立了时间与半径的函数关系。随后，利用Matlab直接对函数进行作图分析并求出了最优解；同时，我们又选用鱼群算法对函数进行迭代，验证了最优解。三、模型的假设（1）假设机器人可以抽象成一个点。（2）假设机器人内部的控制系统没有出什么问题，能正常工作。（3）假设假设机器人能迅速反应加速到最大速度和减速到最小速度，蓄势时间可以忽略不计。（4）假设行走路线不受外界因素干扰，均为理想状态。四、符号的说明L路径的总长度𝑎𝑖圆心的横坐标𝑏𝑗圆心的纵坐标ρ转弯半径T最小总时间五、理论准备5.1理论与证明猜想：具有圆形限定区域的最短路径是由两部分组成的：一部分是平面上的自然最短路径（即直线段），另一部分是限定区域的部分边界，这两部分是相切的，互相连接的。证明：假设在平面中有A（a，0）和B（−a，0）两点，中间有一个半圆形的障碍物，证明从A到B的最路径为AEF̂B。4图1平面上连接两点最短的路径是通过这两点的直线段，但是连接两点的线段于障碍物相交，所以设法尝试折线路径。在y轴上取一点C（0，y），若y适当大，则折线ACB与障碍物不相交，折线ACB的长度为：|𝐴CB|=2√𝑎2+𝑦2显然|ACB|随着y的减小而减小，减小y→𝑦得，即C→𝐶,使得A𝐶与𝐶𝐵与障物相切，切点分别为E和F,显然A𝐶𝐵是这种折线路径中最短的。由于满足0α𝜋2角满足αtanα,所以易知弧度EF小于的长A𝐶𝐹，即EF̂ECF,从而𝐴𝐸+EF̂+FBA𝐶𝐵,记线段AE、弧度EF、线段FB为AEFB,那么AEFB比任何折线路径都短。下面在考察一条不穿过障碍物的任何一条路径，设其分别于OE和OF的延长线交与P、Q两点，记A和P之间的路径长度为AP̂，显然AP̂|AP|,又由AEEO,所以|AP|AE,从而AP̂AE,同理可得BQ̂BF。再来比较PQ之间路径长度PQ̂和圆弧EF的长度的大小。若PQ之间的路径可有极坐标方程ρ=ρ(θ),则有ρ10,可得：PQ̂=∫√𝜌2+𝜌2𝑑𝜃≥∫𝑑𝜃−𝜋3−EF̂结论：路径APQB的长度超过路径AEFB的长度，所以满足从A到B的最短路径为AEFB的路径。5.2模型的准备在上面的证明中，我们就可以这样认为，起点到目标点无论中间障碍物有多少，最短路径都应该是若干个线圆组成的结构。在本题中存在障碍物的状况，且障碍物在拐点处的危险区域是一个半径为10的圆弧。所以结合上述证明，我们得知，求两5点之间的最短路径中的转弯半径我们应该按照最小的转弯半径来算才能达到最优。图2如图2是将题目中原图的一个模型转化成上图所示，设A(𝑥,𝑦)为原图中的原点O也就是出发点,B(𝑥2,𝑦2)是图中的终点，C(𝑥3,𝑦3)和D(𝑥4,𝑦4)是机器人在转弯的时候在限制的危险区域内（半径为10的圆弧）的切点，圆心是O(𝑥5,𝑦5)，圆的半径为r，AB的长度是m，AO的长度为n，BO的长度为c，由于要求出角DOC所以，∠DOC=θ，∠AOB=α，∠AOC=β，∠BOD=γ于是有：{𝑎=√(𝑥2−𝑥)2+(𝑦2−𝑦)2𝑏=√(𝑥−𝑥5)2+(𝑦−𝑦5)2𝑐=√(𝑥2−𝑥５)2+(𝑦２−𝑦5)2在三角形AOB中α=arccosｎ2+ｃ2−ｍ22ｎｃ在直角三角形AOC中:β=arccosrn;在直角三角形BOD中：γ=arccosrc;6所以根据以上的公式关系可以求出：θ=2π−α−β−γ以及算出L=√𝑛2−𝑟2+√𝑐2−𝑟2+θr（ｍ，ｎ，ｃ可以根据障碍物的数据描述）求得。六、模型的建立和求解6.1问题一建模与求解6.1.1建模过程第一步：起点到目标点无论中间障碍物有多少，最短路径都应该是若干个线圆组成的结构。在本题中存在障碍物的状况，且障碍物在拐点处的危险区域是一个半径为10的圆弧，所以结合上述证明，我们得知，求两点之间的最短路径中的转弯半径应该按照最小的转弯半径来计算才能达到最优。第二步：画出可能存在的路线，解决的就是O到目标点A的最短路径问题。很显然的一个问题是机器人从m走的最短路径肯定是优于机器人从n走的最短路径，给出了三条可能的最短路径，我们可以分别计算出三条可能路径的最短路径的长度，然后进行比较，取最小者就o是到目标点B的最优路径。第三步：解决的是O到目标点C的最短路径问题。图中给出了两条可能路径的最短路径，我们同样可以分别计算出两条可能的最短路径，取最小者就是O到目标点C的最优路径。图36.1.2模型的求解（1）原点O到目标点A的最短路径为L=471.0372求解方法见(附录1)过程见(附录2)7（2）原点O到目标点B的可能路径有三条，即就有三条可能的最短路径。而机器人经过中间一条路径到达B,这条路径由三条线段和两段圆弧组成，直接用三中的解法是结不出来的。于是我们做了如下变换，先求出中间一条直线的中点设为F(180，370)，那么可以采用三中的解法，分别求O到F和F到B的最短路径，然后两段相加，便可求出O到B的最短路径。求解结果为L=853.1121(3)机器人经过最下边一条路径，同理这条路径由四条直线和三个圆弧组成，同样可以采取②中的变换，分三部分求解。综合①②③所述，O到目标点B的最短路径为L=853.1121。原点O到目标点C的可能路径由两条，和2中的方法一样，最终求解结果O到目标点C的最短路径为L=1130.281(4)从原点O→A→B→C→O就是O→A,A→B,B→C,C→O各段距离的最小路径值的和，解得L=1884.149路径起点坐标终点坐标圆弧圆心坐标圆弧半径O→A线段一(00)(70.5404215.4579)圆弧一(70.5404215.4579)(76.0221220.0597)(80,210)10线段二(70.5404