《数学建模论文-机器人避障最短路径模型》由会员分享，可在线阅读，更多相关《数学建模论文-机器人避障最短路径模型（17页珍藏版）》请在金锄头文库上搜索。
1、2012 高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料） ，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公
2、示，在书籍、期刊和其他媒体进行正式或非正式发表等） 。我们参赛选择的题号是（从 A/B/C/D 中选择一项填写）： D 我们的参赛报名号为（如果赛区设置报名号的话）： Y5203 所属学校（请填写完整的全名）： 西安航空职业技术学院 参赛队员 (打印并签名) ：1. 江厚翔 （组长） 2. 刘祥 3. 屈杰 指导教师或指导教师组负责人 (打印并签名)： 刘宝利 日期： 2012 年 9 月 10 日赛区评阅编号（由赛区组委会评阅前进行编号）：2012 高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全
3、国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：0机器人避障最短路径模型摘要避障最短路径和最短时间路径成为机器人大赛中获胜的关键，本文以研究避障最短路径和最短时间路径为出发点，首先简单推断求解了行走路径为圆弧段时的最小半径。其次，当已知圆和过圆外两点的切线段时，求出由切线段和切点出的圆弧组成的最短路径。则对于问题一：为了使复杂的移动机器人路径问题得到简化，并减少可行路径的计算量,建立图论模型，对此问题的环境，给其赋予权值，将避障路径问题转化为多阶段决策问题，再利用动态规划得到几条较短线路。由于上述方法未考虑到转弯问题，所以需要改进模型对其删选的路线在进行精
4、算。对可能遇到每种障碍物进行分析并建立相应的规划模型。最后，将复杂的线路问题简化为各种简单环境下的最短路径，从而将复杂的路径分割成 n 个最简单的模型，运用 Matlab 软件对其优化求解，最终得出最短路径分别为： 1）OA 的最短距离为 471.04 个单位2）OB 的最短距离为 860.08 个单位3）OC 的最短距离为 1090.54 个单位4）OABCO 的最短距离为 2708.26 个单位对于问题二：构造时间和行走路径中圆弧的半径之间的函数关系，对其求导，利用极值定理得到当半径 时，所走路径用时最短。.51r求得最短时间路径长度为 472.40关键字： 图论 动态规划 分割线路 Ma
5、tlab 软件1一. 问题重述图1是一个800800的平面场景图，在原点O(0, 0)点处有一个机器人，它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述如下表：编号 障碍物名称左下顶点坐标其它特性描述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)
6、 上顶点坐标(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个单位） 。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相
7、切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。机器人直线行走的最大速度为 个单位/秒。机器人转弯时，最大转弯速度50v为 ，其中 是转弯半径。如果超过该速度，机器人将发生侧21.0e)(vv翻，无法完成行走。请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中4个点O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具体计算：(1). 机器人从O(0, 0
8、)出发，OA、OB、OC和OABCO的最短路径。(2). 机器人从O (0, 0)出发，到达A的最短时间路径。注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及2机器人行走的总距离和总时间。问题一 :求机器人从O(0, 0)出发，OA、OB、OC和OABCO的最短路径。 第一步：对OA、OB、OC和OABCO的各种可能性路径进行粗算，即：将所经过的障碍物拐点和终点与起点用折线连接起来，形成有向图论，给其赋予权值，找出可能的最短路径。第二步：对第一步找出的几条可能最短路线采用拉绳子的方法排除第一步中存在的弊端（没有考虑到弧线路径） ，我们先可以用包络线画出机器人行走的危险区域，
9、这样的话，拐角处就是一个半径为10的四分之一圆弧，然后采用拉绳子的方法寻找最短路径（比如求O和A之间的最短路径，我们就可以连接O和A之间的一段绳子，以拐角处的圆弧为支撑拉紧，那么这段绳子的长度便是O到A的一条最短距离） 。从而找出最短的路线。第三步：用建立的模型对最短的路线进行求解，求出最短的路程值。问题二: 针对机器人从 OA 的最短时间路径， 我们建立求时间最短的路径模型。二.模型假设1. 假设机器人转弯时与地面垂直；2.假设机器人在转弯时的减速和加速都是瞬时的，时间可以忽略不计；3.假设机器人直线行走和曲线行走都为匀速;4.假设机器人抽象为一个点来处理；5. 假设机器人内部电量的变化不会
10、影响机器人的速度。三.符号说明1. ：表示机器人行走的路程总和；S2. ：表示第 个分割路径的长度；Lii3. ：表示转弯半径；r4. ：表示机器人在直线上行走的最大速度；v05 ：表示机器人在圆弧上的最大速度；6 :表示机器人所运动的时间；t7. 表示障碍物上任意一点到机器人的距离。k四.模型的建立4.1 模型准备4.1.1 确定行走路径中的某段为圆弧时的最小半径。3（1）两圆内切，即顶点相同：图 1由上图易知: AD+DEAG+GE,所以可得出当半径越小时路程越短，结合题意故拐弯求最短路程时半径应该取 10 个单位。 2两圆为同心圆： 图 2由图知: 当圆半径越小时，A 到 B 之间距离最
11、短，而题意最小安全半径为 10 个单位，故求最短路程问题，半径应取为 10 个单位。4.1.2 重要结论已知圆 O 和圆外两点 A，B,过 A,B 做圆的切线段，求由切线段和切点出的圆弧组成的最短路径。图 34求解过程分两种情况讨论，如下所示：（1）假设最短路径由两条切线和一段圆弧组成时。 。如图 3 ，设 A 为起点，B 为目标点， C 和 D 分别为机器人1,yx2,yx3,yx4,yx经过拐点分别于隔离危险线拐角小圆弧的切点，圆心为 O ，圆的半径为5,r，AB 的长度为 a，AO 的长度为 b，BO 的长度为 c，角度 = , = , ABOC= ， .求 AC,CD,BD 的总长度，
12、设为 L.BODC解法如下： 2121yx55b22c： AOB在 中 bca2arcos2在 ：RtCr在 中：tAOarcos所以： 2从而可得： 22Lbrcr5图 42）：假设最短路径为两段圆弧的内公切线组成。图 5我们假设两圆心坐标分别为 O 和 O ，半径为 r 和 ，M 点为yx1, yx2, R，那么我们容易可以求得：yx3,DMOEE6所以 EMODRrryx213213这样我们就可以利用二中的方法，先求 A 到 M，再求 M 到 B，这样分两段就可以求解。同理如果有更多的转弯，我们同样可以按照此种方法分解 。3）假设最短路径为两段圆弧外切线组成。图 6这里我们依然设圆心坐标
13、分别为 O 和 o , ， A ，yx1, 2,Cyx3,4, , ，AO 斜率为 ，BO 的斜率为 ，半径1CO2E3CDkk1为 r 和 。R所以可以推导出 ，2121yxooc22rR有角度关系可得 yOc2121aros213所以： Cx33cCo3sin由于 OA/OB ,可得：kxy2317再由图分析可得 与 即可推导出 这214214yxr xyk142y4,样我们就可以再次利用环境一的方法进行求解。4.2 模型的建立：4.2.1 对问题一：机器人从 O 点出发到达指定位置，将其路径划分为 n 个由圆弧和线段组成的简单模型即环境一,那么目标函数可以表示为： niiLSMi10.k
14、rts4.2.2 对问题二短时间模最型：所求单个路径: 22Lbrcr所以evvrt 21.00202化简为 vcrbrrt 01.022 2min 从而找出 的值，所经过的路线为最短时间路线。r五模型的求解5.1 问题一1）OA 如图，很显然从 O 到 A 就两条路径，直接可以通过最简单的模型求解方法对其进行求解，计算所得最小路径为 O 到 A 的最短路径。2) OB如图，经过粗算取出几条可能的最短路线，我们可以分别对其进行求解，计算所得最小路径为 O 到 B 的最短路径。3) OC如图，同 2）经过粗算取出几条可能的最短路线，接着分别对其进行求解，计算8所得最小路径为 O 到 C 的最小路径。4）OABCO分别对 AB,BC 按前三种方法求出其最短路径，接着由 1)找出的 OA 最短路径和由 3）找出的 OC 最短路径可以得到 OABCO 的最短路径。图中的路径即为 OABCO 的最短路径。求解过程A图 7对 路径粗算可得：路线一：AO493.62510路线二： 78510故可得路线一较短，因此对路线一进行精算。9图 8利用上模型可得 求解的精值为AO471.032求解过程B图 9对 路径粗算可得： BO10路线一： 817.255
