《高教社杯全国大学生数学建模竞赛d题国家二等奖论文》由会员分享，可在线阅读，更多相关《高教社杯全国大学生数学建模竞赛d题国家二等奖论文（26页珍藏版）》请在金锄头文库上搜索。
1、2012高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，
2、在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： D 我们的参赛报名号为（如果赛区设置报名号的话）： Y 0802 所属学校（请填写完整的全名）： 西安理工大学高等技术学院 参赛队员 (打印并签名) ：1. 熊* 2. 胡* 3. 杨* 指导教师或指导教师组负责人 (打印并签名)： 教练组 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：2012高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号
3、）：全国评阅编号（由全国组委会评阅前进行编号）：机器人避障问题摘要机器人避障问题主要考虑机器人的路径选择。本文问题是地图已知情况下，机器人从区域中一点到达另一点的避障最短路径和最短时间路径问题。利用几何学的路径规划算法对机器人避障问题建立几何模型，并使用matlab软件和mathematica软件求解，用图论知识进行分析得出局部最优路径，最终比较得出机器人避障的全局最优路径。 问题一：建立区域中一点到达任一点的避障最短路径和最短时间路径的数学模型，将具体问题分解成三种线圆结构，并运用图论知识中的方法、穷举法以及几何知识进行优化求出最短路径，最终比较得到各个路段机器人避障得最短路径。最短路程为，
4、经过的点坐标分别为：（以下圆弧的圆心都是所对应的图形各顶点，如对应的圆心为，且半径全为10） 的最短路程为，经过的点坐标分别为：的最短路程为1033.10，经过的点坐标分别为： 的最短路程为，同样也可写出经过点的坐标，在文章中6.1中列出。问题二: 根据拐弯半径反求速度，要求时间路径最短，即弧度少路程短，可以适当的变换拐点处的拐弯半径，使机器人能够沿直线通过途中目标点，由图论知识建立几何优化模型，对比分析求出最短时间的路径。的最少时间为98.10，其路程为501.6210。而问题一对于到的最短距离计算出时间路程。显然问题二采用的方法所用时间较少，但距离略大于问题一中选用的方法计算的路径长度。本
5、文中运用大量图论知识，表达清晰明了，建立的几何模型，运算简单方便，快速灵活。但几何路径只适用于障碍物少且形状简单的情形。对于障碍物多且形状复杂的问题，具有一定局限性，所以我们如果遇到障碍物较多的情形，我们会采用Dijkstra算法进行求解。关键词： 机器人避障 几何模型 最优路径图论 一问题提出在当今科技的发展下，众所周知机器人性能的提高是现在研究的热点。而行走机器人避障路径规划是智能机器人研究的方向。在一个800800的平面场景图，机器人在原点O(0, 0)处，并且只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述如表1：表1 障碍物信息
6、表编号障碍物名称左下顶点坐标其它特性描述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, 6
7、00)边长13011正方形(640, 520)边长8012长方形(500, 140)长300，宽60在图1所示平面场景中，在障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。且机器人直线行走的最大速度为个单位/秒。机器人转弯时，最大转弯
8、速度为，其中是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。根据机器人行走的这些限制，需要建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型，以及对场景图中4个点，具体计算机器人从出发，、和的最短路径以及机器人从出发，到达A的最短时间路径。并且要求给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。图1 800800平面场景图二问题分析移动机器人的路径规划指的是在有障碍物的工作环境中,寻找一条从给定起点到终点的运动路径,使移动机器人在运动过程中可以安全、无碰撞地绕过所有障碍物,而且所走的路径较短。移动机器人的路径规划分为地图
9、已知和地图未知两种情况，常用的路径规划方法有人工势场法、栅格法、可视图法、遗传算法、蚁群算法和粒子群算法等。但是为了计算简单，运用方便，本文建立区域中一点到达任一点的避障最短路径和最短时间路径的数学模型，然后采用基于几何学的路径规划算法，计算出每个出发点到目标点的最短距离。2.1问题一要使机器人避开障碍物由一点到达另一点，又规定机器人的行走路径由直线段和圆弧组成。那么起点到目标点无论中间障碍物有多少，最短路径都应该是若干个线圆结构所组成。在本题中障碍物在拐点处的危险区域是一个半径为10的圆弧，要求两点之间的最短路径中的转弯半径我们应该按照最小的转弯半径来算才能达到最优。据题知机器人直线行走的最
10、大速度为个单位/秒。机器人转弯时，最大转弯速度为，其中是转弯半径。用半径反求法求解出机器人每一次最大转弯的速度为2.5个单位/秒，依据路程与速度的关系建立时间最短优化模型。2.2问题二要求定点按照一定的行走规则绕过障碍物到达目标点的最短路径，机器人不能折线转弯，那么拐角处就是一个半径为10的四分之一圆弧，然后采用穷举法列出起点到每个目标点的可能路径的最短路径，然后比较其大小便可得出起点到目标点的最短路径。由于机器人直线行走与沿弧线拐弯时的速度不同，要得到最短的时间，需考虑行走的路线中直线尽可能长，弧线尽可能短，同时还需保证行走的路程最短，故可建立几何模型。三模型假设1. 机器人自身可以探测到一
11、定范围内的障碍物。2. 机器人行走路径由直线段和圆弧组成，其中圆弧式机器人转弯路径。3. 机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成。4. 机器人转弯每个圆弧的半径最小为10个单位。5. 机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，无法完成行走。6. 机器人可以抽象成质点来处理。四符号说明 路径的总长度 机器人行走总时间 第段切线的长度 第段圆弧的长度 转弯半径 障碍物上的任意点与行走路径之间的最短距离直线在转弯圆弧上的切点 两转弯圆弧的圆心连线中点 分别表示第1，12个障碍物 所有的障碍物字母表示的总称 每一路径经过障
12、碍物的拐点从左下角起，依次 经过圆弧的第一个切点 经过圆弧的第二个切点 五模型的建立5.1模型准备对题目给出的平面场景要找最短路径，按几何学路径规划算法，会遇到如下3种情况（见图2、图3、图4）需要考虑：图2 线单圆结构 图3 线双圆结构1 图4 线双圆结构25.1.1 定理1 具有圆形限定区域的最短路径是由两部分组成的：一部分是平面上的自然最短路径（即直线段），另一部分是限定区域的部分边界，这两部分是相切的并互相连接。（即问题分析中的拉绳子拉到最紧时的状况） 图5 证明：在图5平面中起点为和终点为，且，为圆心，半径为，证明从A到D的最短路径为 。如图可知，且由图明显可知，故，推广到平面中可知
13、AED是所有折线路线中最短的。若OB连线夹角为，则，由于满足的角，所以易知小于BEC的长度。那么是所有折线路径中最短的。说明了是满足条件A到B的最短路径。由此充分说明了图2、图3、图4三种结构中所要寻找的最短路径是直线和弧线的组合。5.1.2三种情况最短路径长度求解（1）如图3，设为起点，为目标点，和分别为机器人经过拐点分别于隔离危险线拐角小圆弧的切点，圆心为，圆的半径为，的长度为，的长度为，的长度为，角度，求的长度，设为。解法如下：如图2有以下关系：在中：在中：在中：所以： 从而可得： （2）而对于我们不能直接采用线圆的结构来解决，需要做简单的变换，如图3结够假设两圆圆心坐标分别为和，半径均为，点坐标为，那么我们很容易可以求得: 这样就可以利用（1）中的方法，先求A到D，再求D到G，这样分两段就可以求解。同理如果有更多的转弯，我们同样可以按照此种方法分解,以此类推从而问题得到了解答。（3）见图4设圆心坐标分别为和半径均为r，这样我们可以得到：那么直线方程为：因为公切线与平行，那么的直线方程可以表示为：这样就可以求解出切点坐标，复杂问题就可以转化为简单的线圆结构5.2
