承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）：我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员(打印并签名) ：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期：年月日编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：机器人避障问题摘要针对题中机器人避障最短路径问题，文章使用简化后建立的最短路径的数学模型来解决此类问题。

对于问题1，我们matlab中自带函数graphshortestpath函数求解最短路径的数学模型。

其主要思想是：首先先证明出两点之间的最短路径是由两条线段和以中间点为圆心的圆的一段圆弧组成，然后证明圆弧的半径为定值10。

然后对模型简化使模型化为标准的最短路径模型，最后用graphshortestpath函数对模型求解。

针对问题2，我们建立了优化模型。

在问题1的基础上，我们对两种行走方案进行分析，根据转弯弧的半径变化对速度的影响我们锁定到一条路径，然后利用lingo对优化模型进行求解。

关键词：graphshortestpath函数、最短路径、避障问题1、问题重述已知：在下图中原点O(0, 0)点处有一个机器人，它只能在该平面场景范围内活动。

图中有12个区域是机器人不能与之发生碰撞的障碍物。

在机器人的行走中，要求机器人行走路径只能是以下两种：由与直线路径相切的一段圆弧组成、由两个或多个相切的圆弧路径组成。

不能沿着折线转弯。

转弯的圆弧半径最小为10个单位，并且机器人与障碍物至少距离10个单位。

在速度方面，机器人直线行走的最大速度为50=v 个单位/秒。

机器人转弯的最大转弯速度为21.0100e1)(ρρ-+==v v v ，其中ρ是转弯半径。

问题1：求机器人从O(0, 0)出发，O→A 、O→B 、O→C 和O→A→B→C→O 的最短路径。

问题2：求机器人从O (0, 0)出发，到达A 的最短时间路径。

2、模型假设1、假设机器人抽象成点来分析2、假设机器人在改变路径时能在瞬间将速度调整过来3、符号说明符号 符号说明Tθ L V 0V R机器人达到目的地所用的时间 转弯角度 转弯的弧长 转弯速度直线行走最大速度转弯圆弧的半径4、 模型的建立与求解4.1 首先证明以下猜想：两点之间若间隔有障碍物，两点之间的最短路径是由两部分组成。

第一部分是自然最短直线段，第二部分是限定部分的边界弧。

这两部分是相切并且互相连接的。

证明：如图A,B 两点，它们之间有一个半径为1的半圆形障碍物。

现在要求出A 到B 的最短路径。

分析1：两点之间的最短路径应是连接两点的线段，但是由于障碍物的存在，现在改为绕过障碍物的折线（用于证明方便），设动点C 点坐标设为（0，y ），折线ACB 的长度为222y a +，当c 点竖直向下移动时，折线ACB 的长度会减小，当C 点移动到C1（0，y1）点时ACB 的长度最小，最小长度为2122y a +。

其中C1是过点A,B 与圆弧相切的切线交点。

又由于满足0<α<2π的角满足α<tan α，所以弧度EF 小于E 1C F 的长。

记线段AE ，弧度EF ，线段FB 这样的路径为AEFB ，则从A 到B 绕过障碍物的最短路径为AEFB 。

分析2：当考虑从A 到B 的路径全为圆弧线段组成时，如图A 到B 的弧线。

假设a=2，则这段弧线所对应的圆为经过A(-2，0)，B(2，0)，(0，1)三点的圆的一部分。

此圆的一般方程为：425)23(22=++y x ，则这段圆弧路径的长度为2π。

若用分析1中的折线与弧线相交并相切的方法计算，路径长度为332π+≈4.51小于圆弧方案的长度。

综上所述，方案AEFB 满足题中最短路径的要求。

4.2 切线和弧线的公式推导如图，在4.1的基础上用解析几何方法计算出两条切线和一段圆弧的长度。

假设起点终点为A （x1，y1）和C （x3，y3），障碍物的顶点为B(x2，y2），D,E 为两条线段与圆弧的切点，圆弧的半径为10个单位。

现在求解线段AD ，CE 及圆弧DE 的长度。

因为三角形ABD 和CBE 是直角三角形，我们可以利用余弦函数来解出∠DBA 和∠EBC 。

COS ∠DBA=AB DB =212212)()(10y y x x -+-，①COS ∠EBC=BC BE =232232)()(10y y x x -+-，②然后再利用余弦定理在三角形ABC 中找出与∠ABC 有关系的等式，COS ∠ABC=BCAB AC BC AB ⨯⨯-+2222，③由①②③三式再根据周角为2π可以解出角DBE 的弧度数，由于后面编程需要，需要将弧度数转化成角度数，利用公式180π⨯=弧度角度，然后再利用公式180n rπ=弧长求得弧DE 的长度。

而对于线段AD,CE ，我们可以直接根据勾股定理可以求得具体长度。

程序见附件1。

4.3 模型简化模型的中心思想是利用Dijkstra 算法来求解出最短路径的方案，由于两点间路径是由线段和弧线组成的，为了化为标准的最短路径模型，需要将模型进行简化。

在这里以4.2的模型基础上进行示范。

首先令A,B,C 分别为起点、中间点、末点。

我们将路线ADEC 分成两个部分，第一部分是线段AD 和弧线DE 组成的，第二部分是线段EC 。

又由于弧线的长度会随着末点的变化而变化，所以我们取弧线的平均值作为弧线DE 的长度。

第一部分表示起点到中间点的距离。

在本题中主要不是如4.2中的简单模型。

现在以下图模型进行进一步说明。

此模型涉及到两个障碍物，根据以上简化思想，A到H的最短路径应该是简化为三部分。

第一部分为线段AD与弧线DE（弧线DE的平均值），表示A到B的距离。

易知线段EC和线段BF的长度是相等的，第二部分为线段BF与弧线FG，表示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中圆弧变化对时间的影响。

对于最短时间模型，我们使用了最优化模型。

由于半径会影响机器人在转弯弧上的速度，当半径增大时，机器人在转弯弧上的速度也会增大，此时机器人所走的直线段会变短，而时间=路程速度，我们要求最短时间，就要使0两边直线段之和速度（v =5)+20100.1v=)1R v e -⨯+圆弧长速度( 最小。

其中： 第一条直线段长度为22280210R +-； 第二条直线段长度为222(30080)(300210)R -+--；转弯弧所对的圆心角θ为：2222360(arccos ) 3.14180(arccos ) 3.1418080210(30080)(300210)RR -÷⨯-÷⨯+-+-222222222280210(30080)(300210)300300arccos 3.14180280210(30080)(300210)++-+----÷⨯+⨯-+-； 转弯弧长为：3.14180R θ⨯⨯； 转弯速度为：2100.151R e -+模型的数学表达式如下：S.T. min T =22222280210(30080)(300210)5R R L V+-+-+--+10R ≥2222360(arccos ) 3.14180(arccos) 3.1418080210(30080)(300210)RR θ=-÷⨯-÷⨯+-+- 222222222280210(30080)(300210)300300a r c c o s 3.14180280210(30080)(300210)++-+----÷⨯+⨯-+- 3.14180R L θ⨯⨯=2100.151R V e -=+然后利用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路径）、19号（对应20—27路径）。