数学建模-机器人避障问题

2014高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）．我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题．我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出．我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性．如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理．我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）．我们参赛选择的题号是（从A/B/C/D中选择一项填写）：A我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)：（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名．以上内容请仔细核对，提交后将不再允许做任何修改．如填写错误，论文可能被取消评奖资格．）日期：2014年9月15日赛区评阅编号（由赛区组委会评阅前进行编号）：2014高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1机器人避障问题摘要本文针对机器人如何在平面区域内避过障碍物到达知道目标使行程最短和用时最短问题进行研究，其间运用穷取法，弹性拉绳法，针对最短路径和最短用时问题建立了非线性规划模型，解决了如何在平面区域内避过障碍物到达知道目标使行程最短和用时最短问题．针对最短路径问题，在明确机器人不能与障碍物碰撞且与障碍物距离不能小于10个单位后，先将整个区域分为安全区域和危险区域两部分，机器人在安全区域内行走可能避过一个或多个障碍物，为了确定机器人在安全区域内行走时避过每个障碍物的具体路径，以仅一个障碍物和两个障碍物的避让问题为例，建立基本线圆组合结构模型，求解确定圆弧圆心坐标和半径，利用直线段与圆弧相切条件确定切点坐标，结果证明机器人在沿障碍物顶点危险区临界圆弧行走时路径最短，由此推广到多障碍物的避让问题，建立最短路径线圆组合结构模型，利用MATLAB软件求解，求的机器人从O点到A点最短路径分别为471.0372个单位，从O点到B点最短路径分别为864.9988个单位，从O点到C点最短路径分别为1095个单位，从O点到A点然后到B点，再从B点到C点的最短路径是2756个单位．针对最短用时路径问题，在问题一求出的最短路模型的基础上，增加速度条件，根据转弯半径和速度的关系，进行路线优化，建立以最短时间为目标的非线性规划模型，通过LINGO编程最终得到最短时间为88.60340秒，圆弧的圆心为（200，82.8），圆弧半径为144.2828个单位．本模型是根据具体问题确定目标函数和约束条件的非线性规划模型，较好的解决了如何在平面区域内避过障碍物到达知道目标使行程最短和用时最短的复杂问题，而且模型中采用大量的基础知识进行推到求解，简单易懂，具有一般性，适用于很多路径问题．关键词：穷取法弹性拉绳法非线性规划2一、问题的重述在一个800×800的平面场景图，原点O(0,0)点处有一个机器人，它只能在该平面场景范围内活动．图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物．障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）．规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径．机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位．为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走．机器人直线行走的最大速度为50v个单位/秒．机器人转弯时，最大转弯速度为21.01001)(evvv，其中是转弯半径．如果超过该速度，机器人将发生侧翻，无法完成行走．请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型．对场景图中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的最短时间路径．注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间．二、问题的分析2.1概述这是一个多约束规划问题，求的是区域内机器人如何从一点到另一点使行程最短或用时最短的路径避障问题．问题的特点在于稳定性强，最优路径固定，难点在于障碍物数量多，而且形状不一致，解题的关键是要如何确定机器人具体的转向时刻和转向坐标，才能使使行程最短或用时最短．2.2最短路径问题具体问题以给出的约束条件为前提，求解区域内机器人从给定的一点到另一点的最短行程的值，以及机器人行走的每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标，显然这是一个在一定约束条件下求最优解的问题．限制条件机器人行走过程中要避开区域内的12个障碍物，不能与之碰撞，否则将不能继续行走．从题面可以看出障碍物均匀的分布在区域内，而且已经给出障碍物的具3体形状和坐标．基于机器人的性能限制，其行走的过程要同时满足以下3个条件：a．约束条件主要有机器人与障碍物的最小距离要大于10个单位；b．机器人不能折线转弯，行走的路径只能有直线和圆弧组成，或者可以由两个或多个相切的圆弧路径组成；c．圆弧的半径必须大于10个单位，否则会与障碍物相撞．具体分析将所有区域分成可行区域和不可行区域两部分，分别命名为安全区域和危险区域，求出安全区域和危险区域的点集，那么只需保证机器人在安全区域内行走，即机器人行走的轨迹点与危险区域点集内的任一点的距离大于10时，就不会出现碰撞的情况，避免碰撞的问题得以解决．机器人的行走的具体轨迹只能是直线或者圆弧，求解目标是轨迹总长，那么每段直线和圆弧的起始点和终止点坐标，以及圆弧的圆心坐标自然都是解题的关键因素．2.3最短时间路径问题具体问题以前面的限制条件为前提，增加速度条件的限制，求解区域内机器人从给定的一点到另一点用时最短的时间值，以及机器人行走的每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标．显然这同样是一个在一定约束条件下求最优解的问题．限制条件机器人直线行走的最大速度为v=5个单位/秒，机器人转弯时的最大转弯速度为21.01001)(evvv，其中是转弯半径．具体分析最短时间路径问题与最短路径问题的情况并不一样，最短路径问题只是简单的求解路径最短，而最短时间路径问题要兼顾路径长度和速度两个方面，路径越短，速度越大，则机器人行走的总时间越短．整个行走过程中机器人有两个速度，分别是直行速度和转弯速度，直行速度是一定的，而转弯速度由直行速度和转弯弧行的半径共同决定，显然这是一个非线性规划问题，相关约束有速度，圆弧半径等．三、模型的假设1、机器人在直线切入弧线时的速度是瞬间变化完成的，不存在中间速度2、机器人转向圆弧的的长度都比较短，机器人行走路径的长度主要由直行部分决定．3、机器人转弯时不存在两圆内切的情况4、机器人如果直行可以到达目的地，那只能直线行走，不可以随意转弯．四、符号的说明),(00yxD：只有考虑一个障碍物时机器人行走的起始点；),(11yxE：只有考虑一个障碍物时机器人行走的终点坐标；4),(yxH：只有考虑一个障碍物时与圆弧相切的两条直线的延长线的交点DE：起始点),(00yxD和终点),(11yxE的距离DH：),(00yxD与转向点),(yxH的距离EH：终点),(11yxE和转向点),(yxH的距离d：),(yxH到直线DE的距离il：障碍物为三角形是三角形的三个点构成的三条直线的方程（i=1，2，3）f：),(00yxD与转向点),(yxH的距离与终点),(11yxE和转向点),(yxH的距离的和值；2121,,,IIHH：两个障碍物时的两个切点；21,OO：两个障碍物时两段圆弧的圆心；r：2H到直线12IH的距离；1HL：点H到切点1H的距离；HIL:H到I的路线长度.五、模型的建立与求解5.1建模前的准备5.1.1划分危险区域由于机器人行进过程中与障碍物有最小距离的限制，因此我们先画出包络障碍物的危险区，对于有圆形障碍物来说，危险区还是一个圆，对于有顶点的障碍物来说禁区拐角处为一个圆弧，具体如图（5-1）所示：5图（5-1）5.1.2转弯弧圆心在顶点路径最短取定机器人行走的起始点和终点,当线段DE穿过跨越障碍物或者其周围10单位的区域时，则说明机器人需要进行转向，轨迹的总长为转折点前后的直线加上弧长的总长．如果没有穿过，说明机器人不需要转向，轨迹的总长为DE两点间的距离．因为不需要转向的情况比较简单，这里主要研究需要转向的情况．当只需跨越一个障碍物时，影响轨迹的总长因素主要是转折点，当转折点（即切点）使转折点前后的直线加上弧长的总长最短时，即得轨迹的总长最短．而对于大多数的避障情况，轨迹的总长主要有直线部分组成，圆弧的长度只占总长的一小部分，为了方便研究，姑且忽略圆弧部分，假设机器人可以进行折线转向，取与圆弧相切的两条直线的延长线的交点（即转向点）作为研究对象，下面对只有一个障碍物的情况进行研究．要跨越一个障碍物，机器人可以从障碍物的两边走过，任取一边为机器人选定的方向．取机器人行走的起始点),(00yxD和终点),(11yxE，与圆弧相切的两条直线的延长线的交点即转向点),(yxH，得到的示意图（5-2）如下：6DFGO1H图（5-2）那么，起始点),(00yxD和终点),(11yxE的距离为：201201)()(yyxxDE起点),(00yxD与转向点),(yxH的距离为：2020)()(yyxxDH终点),(11yxE和转向点),(yxH的距离为：2121)()(yyxxEH使EHDH最短DE的方程：010010xxxxyyyy，即0)()()()(0010101001xyyyxxxyyyxx转向点),(yxH到直线DE的距离公式为：2102010010101001)()(|)()()()(|yyxxxyyyxxxyyyxxd障碍物为三角形，由三角形的三个点构成的三条直线的一般方程分别为：2l：0222cybxa1l：0111cybxa3l：0333cybxa以DH与EH之和最少为目标函数，得到以下规划模型：min212120201)()()()(yyxxyyxxEHDHf70)()(|)()()()(|10||10||10||..2102010010101001232333322222222121111yyxxxyyyxxxyyyxxbacybxabacybxabacybxats模型中前三个约束分别是保证转向点与障碍物的距离大于10个单位，第四个约束是因为轨迹并非一条直线，转向点不在直线DE上．显然，当f取最少值时，以下式子当且只有一个成立：10||2121111bacybxa，10||2222222bacybxa,10||2323333bacybxa．从而证明，当机器人避过障碍物行走的轨迹最短时，轨迹总是经过障碍物危险区的圆弧．5.1.3障碍物为一个的情况机器人从起点到终点假设在没有障碍物的情况下是