数学建模机器人避障论文

.z承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开场后参赛队员不能以任何方式〔包括、电子、网上咨询等〕与队外的任何人〔包括指导教师〕研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料〔包括网上查到的资料〕，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们*重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是〔从A/B/C/D中选择一项填写〕： 我们的参赛报名号为〔如果赛区设置报名号的话〕：所属学校〔请填写完整的全名〕：参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期：年月日编号专用页赛区评阅编号〔由赛区组委会评阅前进展编号〕：赛区评阅记录〔可供赛区评阅时使用〕：评阅人评分备注全国统一编号〔由赛区组委会送交全国前编号〕：全国评阅编号〔由全国组委会评阅前进展编号〕：机器人避障问题摘要针对题中机器人避障最短路径问题，文章使用简化后建立的最短路径的数学模型来解决此类问题。对于问题1，我们matlab中自带函数graphshortestpath函数求解最短路径的数学模型。其主要思想是：首先先证明出两点之间的最短路径是由两条线段和以中间点为圆心的圆的一段圆弧组成，然后证明圆弧的半径为定值10。然后对模型简化使模型化为标准的最短路径模型，最后用graphshortestpath函数对模型求解。针对问题2，我们建立了优化模型。在问题1的根底上，我们对两种行走方案进展分析，根据转弯弧的半径变化对速度的影响我们锁定到一条路径，然后利用lingo对优化模型进展求解。关键词：graphshortestpath函数、最短路径、避障问题1、问题重述：在以下图中原点O(0,0)点处有一个机器人，它只能在该平面场景*围内活动。图中有12个区域是机器人不能与之发生碰撞的障碍物。在机器人的行走中，要求机器人行走路径只能是以下两种：由与直线路径相切的一段圆弧组成、由两个或多个相切的圆弧路径组成。不能沿着折线转弯。转弯的圆弧半径最小为10个单位，并且机器人与障碍物至少距离10个单位。在速度方面，机器人直线行走的最大速度为个单位/秒。机器人转弯的最大转弯速度为，其中是转弯半径。问题1：求机器人从O(0,0)出发，O→A、O→B、O→C和O→A→B→C→O的最短路径。问题2：求机器人从O(0,0)出发，到达A的最短时间路径。2、模型假设假设机器人抽象成点来分析假设机器人在改变路径时能在瞬间将速度调整过来3、符号说明 符号符号说明TθLVR机器人到达目的地所用的时间转弯角度转弯的弧长转弯速度直线行走最大速度转弯圆弧的半径4、模型的建立与求解4.1首先证明以下猜想：两点之间假设间隔有障碍物，两点之间的最短路径是由两局部组成。第一局部是自然最短直线段，第二局部是限定局部的边界弧。这两局部是相切并且互相连接的。证明：如图A,B两点，它们之间有一个半径为1的半圆形障碍物。现在要求出A到B的最短路径。分析1：两点之间的最短路径应是连接两点的线段，但是由于障碍物的存在，现在改为绕过障碍物的折线〔用于证明方便〕，设动点C点坐标设为〔0，y〕，折线ACB的长度为，当c点竖直向下移动时，折线ACB的长度会减小，当C点移动到C1〔0，y1〕点时ACB的长度最小，最小长度为。其中C1是过点A,B与圆弧相切的切线交点。又由于满足0<α<的角满足α<tanα，所以弧度EF小于EF的长。记线段AE，弧度EF，线段FB这样的路径为AEFB，则从A到B绕过障碍物的最短路径为AEFB。分析2：当考虑从A到B的路径全为圆弧线段组成时，如图A到B的弧线。假设a=2，则这段弧线所对应的圆为经过A(-2，0)，B(2，0)，(0，1)三点的圆的一局部。此圆的一般方程为：，则这段圆弧路径的长度为2π。假设用分析1中的折线与弧线相交并相切的方法计算，路径长度为≈4.51小于圆弧方案的长度。综上所述，方案AEFB满足题中最短路径的要求。4.2切线和弧线的公式推导如图，在4.1的根底上用解析几何方法计算出两条切线和一段圆弧的长度。假设起点终点为A〔*1，y1〕和C〔*3，y3〕，障碍物的顶点为B(*2，y2〕，D,E为两条线段与圆弧的切点，圆弧的半径为10个单位。现在求解线段AD，CE及圆弧DE的长度。因为三角形ABD和CBE是直角三角形，我们可以利用余弦函数来解出∠DBA和∠EBC。COS∠DBA==，①COS∠EBC==，②然后再利用余弦定理在三角形ABC中找出与∠ABC有关系的等式，COS∠ABC=，③由①②③三式再根据周角为2π可以解出角DBE的弧度数，由于后面编程需要，需要将弧度数转化成角度数，利用公式，然后再利用公式求得弧DE的长度。而对于线段AD,CE，我们可以直接根据勾股定理可以求得具体长度。程序见1。4.3模型简化模型的中心思想是利用Dijkstra算法来求解出最短路径的方案，由于两点间路径是由线段和弧线组成的，为了化为标准的最短路径模型，需要将模型进展简化。在这里以4.2的模型根底上进展示*。首先令A,B,C分别为起点、中间点、末点。我们将路线ADEC分成两个局部，第一局部是线段AD和弧线DE组成的，第二局部是线段EC。又由于弧线的长度会随着末点的变化而变化，所以我们取弧线的平均值作为弧线DE的长度。第一局部表示起点到中间点的距离。在此题中主要不是如4.2中的简单模型。现在以以下图模型进展进一步说明。此模型涉及到两个障碍物，根据以上简化思想，A到H的最短路径应该是简化为三局部。第一局部为线段AD与弧线〔弧线DE的平均值〕，表示A到B的距离。易知线段EC和线段BF的长度是相等的，第二局部为线段BF与弧线，表示B到C的距离。第三局部为线段GH，表示路径的最后一段距离，如果目标点不是H，则下一局部应是线段CH加上下一段圆弧，以此类推。此算法命名为算法1。根据以上的算法1的简化，我们将此题中的机器人避障最短路径模型简化为标准最短路径模型，并且对可能会用到的点加以编号，得到如以下图。4.4模型的求解对于问题1：根据简化使用的算法1，对机器人所有可行走的路径利用4.2推导的公式用matlab进展计算，程序见1，得到所有以三点为一组的各个路径的长度，主要有线段1，圆弧，线段2。具体结果见2。因为中间点到末点具有多条路径，即有不同的圆弧长，所以对同一中间点所对应的所有圆弧长求平均值，将模型简化为最短路径模型，就能得出邻接矩阵，邻接矩阵见3。最后利用matlab自带函数graphshortestpath和邻接矩阵对模型求解得到最短路径。程序见4。运行结果为：〔用编号表示〕O—A：35—1—30O—B：35—2—3—4—5—6—31O—C：35—24—22—20—17—15—32O--A--B--C--O：35—1—30—5—6—31—9—10—11—12—32—15—17—20—22—24—35具体的路径见以下图：对于问题2：问题2需要求出行走时间最短的路径，从图中易知从O到A的路线有两条，一条是35—1—30方案，简称方案1。另一条是35—24—30方案，简称方案2。由问题1解决结果知，方案1比方案2的路径要短，又由计算知，在增加圆的半径的情况下，对于长度较长的方案2所用时间也相应较多。所以，对问题2的讨论中，我们在问题1结果的根底上研究方案1中圆弧变化对时间的影响。对于最短时间模型，我们使用了最优化模型。由于半径会影响机器人在转弯弧上的速度，当半径增大时，机器人在转弯弧上的速度也会增大，此时机器人所走的直线段会变短，而时间=，我们要求最短时间，就要使+最小。其中：第一条直线段长度为；第二条直线段长度为；转弯弧所对的圆心角为：；转弯弧长为：；转弯速度为：模型的数学表达式如下：S.T.=然后利用lingo软件，对模型进展求解，其lingo程序见5。运算结果为：转弯弧半径R=11.50350弧长L=10.52502转弯速度V=4.810298所用时间T=94.55726即，用时最少的路径为从O出发，沿切线到达在以5号正方形左上角为圆心，以11.5035为半径的圆上，再沿另一条切线到达A点。5、模型结果的分析与检验本文模型中的检验主要是针对题中给出的机器人与障碍物之间保持10个单位的距离这一要求，在所得到的路径中，可能存在着*直线段与*障碍物的间隔距离小于10个单位，所以在得到运算结果的前提上，从中找到以下需要检验的检验点：27号〔对应1—30路径〕、7号〔对应31—9路径〕、1