2012年高教社杯数学建模D题--机器人避障问题论文

v1.0 可编辑可修改机器人避障问题的解题分析摘要：本文对2012年全国大学生数学建模竞赛D题机器人避障问题进行了全面分析，对最短路的设计进行了理论分析和证明，建立了机器人避障最短路径的几何模型，对最短时间路径问题通过建立非线性规划模型，有效地解决了转弯半径、圆弧圆心位置和行走时间等问题。

关键词：机器人避障；最短路径；Dijkstra算法；几何模型；非线性规划模型1 引言随着科学技术的进步和计算机技术的发展，机器人的应用越来越广泛，在机器人的应用中如何使机器人在其工作范围内为完成一项特定的任务寻找一条安全高效的行走路径，是人工智能领域的一个重要问题。

本文主要针对在一个场景中的各种静态障碍物，研究机器人绕过障碍物到达指定目的地的最短路径问题和最短时间问题。

本文以2012年“高教社”杯全国大学生数学建模竞赛D题“机器人避障问题”为例进行研究。

假设机器人的工作范围为800×800的平面正方形区域（如图1），其中有12个不同形状的静态障碍物，障碍物的数学描述（如表1）：图1 800×800平面场景图表1在原点O(0, 0)点处有一个机器人，它只能在该平面场景范围内活动，机器人不能与障碍物发生碰撞，障碍物外指定一点为机器人要到达的目标点。

规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。

机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。

为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。

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

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

如果超过该速度，机器人将发生侧翻，无法完成行走。

场景图中有4个目标点O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，下面我们将研究机器人从O(0, 0)出发，求O→A、O→B、O→C和O→A→B→C→O的最短路径，以及机器人从O(0, 0)出发，到达A的最短时间路径问题。

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

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

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

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

我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： A我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：贵州师范大学求是学院参赛队员(打印并签名) ：1. 马甜2. 王顺3. 何亿指导教师或指导教师组负责人(打印并签名)：教练组日期： 2012 年 9 月 10 日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：葡萄酒的评价摘要随着经济的快速发展，人们在追求高物质生活的同时，对于酒文化的了解也越来越多，要求也越来越高，特别是葡萄酒文化。

起初，人们只是通过外观、香气、口感来确定葡萄酒的等级，如果将葡萄酒的各个理化指标考虑进来呢？葡萄酒文化体现了一方国土的人文化以及风土文化。

对于衡量葡萄酒的等级或者酿酒葡萄的等级是处于这个文化段的人士所关注的。

对于葡萄酒的理化指标与酿酒葡萄的理化指标这二者的关系，是葡萄酒经营户所关注的，毕竟可以为经营户们带来巨额的经济效益。

酿酒葡萄的等级必定与组成其的各个理化指标有着密不可分的关系。

大多数人都会认同好的葡萄必定酿造出好的葡萄酒，那么，酿酒葡萄的理化指标是否与葡萄酒的理化指标存在着一定的关系呢？葡萄酒的质量是否可以由酿酒葡萄的理化指标和葡萄酒的理化指标来衡量呢？本文通过建立多个数学模型来分别研究葡萄酒等级以及酿酒葡萄、葡萄酒的理化指标和葡萄酒质量这三者的联系。

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

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

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

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

我们参赛选择的题号是（从A/B/C/D中选择一项填写）：我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员(打印并签名) ：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期： 2011 年 9 月 11 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：机器人避障问题摘要本文通过在给定的平面场景范围内对机器人就如何躲避12个不同形状障碍物区域的避障行走问题进行探究，在出发点到目的点的多种情形中进行选择，并根据要求，保证所走的路线为直线段和圆弧。

继而探究避障的最短路径及最短时间路径的数学模型，在此探究过程中，运用穷举法，进行各种行走路线的CAD绘图，利用平面几何的点、线、圆的关系求解行走路径所经过点的坐标、线段长度、和弧长，在各总长度中进行比较，找出最短路径。

最终，根据机器人速度的数据，建立最短时间路径的数学模型，运用LINGO软件最终求出最短时间的路径。

针对问题一，根据题意，为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，可分别以障碍物的边界处绘制以10为半径的圆，从而确定安全的可行走的活动范围。

机器人避障问题摘要本文主要运用直线逼近法等规律来解决机器人避障问题.对于问题一：要求最短路径运用直线逼近法证得圆弧角三角形定理，得出结论：若一大圆弧角三角形完全包括另一小圆弧角三角形，则该三角形曲线周长必大于小的三角形周长.那么可知机器人在曲线过弯时，选择最小半径可满足路径最短，即为10个单位半径，通过观察可得可能的所有曲线，通过仅考虑直线段的大致筛选选出总长较小、长度相近（之差小于100）的曲线，然后利用平面几何知识对相关切点，进而求出各直线、曲线的长度，求和可得最段路线.对于问题二：通过对机器人过弯规律21.0100e 1)(ρρ-+==v v v 的分析可知，当过弯半径13ρ=时，机器人速度达最大速度为50=v 个单位/秒，再大就无变化了，那么可分两种情况考虑：1）当13ρ>时，过弯速度无变化，但由圆弧角三角形定理可知，此时随着ρ的不断变大，其路线总长不断变大，这时ρ越小O A →所用时间最短；2）当13ρ≤时，统计计算ρ分别为10、11、12、13时，过弯速度v 也不断变化，计算所用时间发现随ρ不断变大，O A →所用时间越短，此时当13ρ=时，时间最短.综合上述可知：当13ρ=时，时间最短.关键词：质点机器人 安全范围 直线逼近法 圆弧角三角形定理 10单位半径1 问题重述在一个800×800的平面场景中，在原点O(0, 0)点处有一个机器人，它只能在该平面场景范围内活动，其中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，物的距离至少超过10个单位）.规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径.机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位.为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位.机器人直线行走的最大速度为50=v 个单位/秒.机器人转弯时，最大转弯速度为2100.110()(1e)v v v ρρ--==+，其中ρ是转弯半径.如果超过该速度，机器人将发生侧翻，无法完成行走.下面建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型.对场景图中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 问题分析2.1问题一：该问题要求路径最短，即不要求速度与时间，则可认为以最小半径10的圆过弯.如图2.1所示：由圆弧角三角形定理（简单证明见模型准备5.3）可知过弯时，只有采用10单位半径过弯时，才会使得过弯路径最短，因此解决问题一的过弯拐角问题均采用10单位半径过弯路径. 2.2问题二：由于O→A 过程中，机器人至少要经过一次转弯；因为转弯时的速度一般小于直线行走的最大速度，又由分析指出转弯次数越多，转弯路径越远，转弯所花费的时间也越长.所以可以确定有且只有一次转弯时才存在最短时间路径.就仅考虑只经过一次转弯的情形.3 模型假设1）假设机器人可准确执行运动轨道，无任何偏差；2）假设机器人为一可运动的质点，即质点机器人不考虑其外形尺寸； 3）假设机器人的行进速度可瞬时加减变化，不受条件限制；4）假设机器人可到达边界线而不会发生碰撞，即对边界线不再加10个单位.4 符号说明hij D ： 机器人的行走路径上各切点，h 表示路径目的地（A 、B 、C ），i 表示到达h 机器人行走路线的第(1,2,3,)i i = 种方案，j 表示机器人在该路线上所经过的第(1,2,3,)i i = 个点；hij L : 机器人的行走路径上的线段长或弧长，h 、i 、j 同上定义；ij D ：机器人的行走路径上的障碍物的顶点，i 、j 同上定义；`hj D ：机器人在O A B C O →→→→环道中的各线切点h 、j 同上定义5 模型准备5.1建立机器人运动坐标系：以O 为原点，两对应坐标轴，水平方向为X 轴，垂直方向为Y 轴5.2建立机器人可安全运动到达的区域图：由于保持安全距离10个单位，则机器人的实际可到达到区域应由各障碍物的外延10个单位的区域组成如图所示图5.2.1实线外的空白部分.5.3圆弧角三角形定理：定义1：平面内若两不平行直线所夹的角被一同时与这两条直线相切的圆弧段取代而形成的角，叫做圆弧角.如图5.3.2，称为凸圆弧角（本文主要讨论）；如图 5.3.3，称为凹圆弧角.定义2：由有一内角为凸圆弧角的三角形为圆弧角三角形.圆弧角三角形定理：圆弧角`DHD ∠在直线`DD 及上方范围完全包含圆弧角`DGD ∠（即圆弧角DGD ’各边均在圆弧角`DHD ∠的边与线段DD ’所构成的封闭区间内，如图5.3.1所示）时，则有曲线段`DGD 的长度恒小于曲线段`DHD 成立.证明：如图 5.3.1，过圆弧 'EGE的一个端点E 作该圆弧在该点的切线的垂线交曲线DH 于点F ，同样过圆弧 'EGE的另一个端点'E 也作相应的垂线交曲线'D H 于点'F ，两条直线的交点O 显然为圆弧 'EGE 所在圆的圆心. （1）,EF DE ⊥ 90DEF ∴∠=︒ ；,DF DE ∴> 曲线段DF DF ≥， ∴曲线段DF DE >.（2）'''',E F D E ⊥ '''90D E F ∴∠=︒；'''',D F D E ∴> 曲线段''''D F D F ≥；∴曲线段''''D F D E >.（3）将''EFF E 分成n 等份（如图5.3.5），每部分（见图5.3.4）中，,(1,,)i i M N i n = 是 MN 与边界的交点.令i i M N 为i M ，i N 两点间直线长度，''i i M N 为`i A ,`i E 两点间直线长度，则圆弧 MN 长度=1lim ni i n i M N →∞=∑，曲线`AE 长度=''1lim ni in i M N →∞=∑又容易证明，''(1,,)i i i i M N M N i n ≤= ，故有''11lim lim n ni i i i n n i i M N M N →∞→∞==≤∑∑ .因此，圆弧 MN长度≤曲线 ''M N 长度. 综合（1）（2）（3）的证明，得曲线段DF +曲线段''D F +曲线 ''M N 长度 > DE +''D E +圆弧 MN长度.结论得证. 6 模型建立与求解该问题要求路径最短，即不要求速度与时间，则可认为过弯半径允许以最小半径10，如图6.1所示.由圆弧角三角形定理可得：本论文问题一求路径最短可采用10单位过弯半径，即以半径为10个单位的圆弧过弯可满足两点避障过弯最短问题.6.1问题一的模型建立与求解：6.1.1：机器人从O(0, 0)出发，O A →的最短路径. 由圆弧角三角形定理可得：采用10单位半径过弯路径最短，解决过弯避障拐角问题采用10单位半径过弯路径.已知机器人所走路线为直线或圆弧，那么通过实际规划可得如下四种避障行进方案：如图6.1.1首先对上述四条路线进行筛选：1）当机器人以一个连续圆弧过弯，即选择路 线二或路线四时,其中路线二：分别过点O A ，和障碍物5的切点23a D （72.74，216.88），则可得过该三点的圆的方程：225406140x y x y ++-=显然当0x =时，y 有不等的两个根，则该路线超出规定场地. 同理路线四的圆方程：22(73.98)(226.02)56558.350x y -+--= (Matlab 求解程序见程序01) 当0y =时，x 有不等的两个根，则该路线也超出规定场地.2）当机器人以直线—圆弧—直线的方式过弯，即有以10单位半径过弯模式的线路一和三：比较线路一与线路三：显然路线一的总长1111213a a a a L L L L =++，线路三的总长3313233a a a a L L L L =++. 解得13471.04498.44a a L L =>=则可知O→A 的最短路径为路线一总长为1471.04a L =，下表5.1.1为线路一的各点的详细参数，表6.1.2为各线的参数.表6.1.26.1.2机器人从O(0, 0)出发，O B →的最短路径由圆弧角三角形定理可得：采用10单位半径过弯路径最短： 通过观察可得如下四种较短的避障行进方案，如图6.1.2：由于方案较多，可预先进行粗略筛选：如图所示：大致统计长度仅包括直线段长度如下表6.1.2线的精确长度：设：11b OD 、1111b D D分别表示O 点到点11b D ，点11b D 到点11D 之间的向量；1111b D D 为11b D 、11D 两点之间的向量的模；()()(),hij hij x y 表示切点hij D 坐标；()()(),ij ij x y 记为障碍物顶点ij D 的坐标；b11L2220(b12)(b11)(b12)(b11)00b12-((x -x )+(y -y ))22=arccos()L ρρρ⨯b13L11(11)(00)(11)(00)(,)b b b OD x x y y =-- ()1 61(61)(00)(61)(00)(,)OD x x y y =--1111(11)(11)(11)(11)(,)b b b D D x x y y =--()2 1111110b b D D OD =()3 1111b D D r =()4联立方程()1()2()3()4解得11b D (50.14,30.64)由于点12b D ，13b D 分别是以点61D ，61D 为圆心r 为半径圆的外公切线切点，所以 由点到直线的距离公式得0ρ= ()50ρ=()6并且线段13126163b b D D D D =()7由于直线13126163b b D D D D 平行直线由斜率相等得(13)(13)(61)(63)(13)(13)(61)(63)b b b b x x x x y y y y --=-- ()8联立方程()5()6()7()8解得点12b D 的坐标(51.6795,305.547)13b D 的坐标(141.68,440.55)线路一和线路二的各段路线及总长分别如下表6.1.2,6.1.3同理可解得各点坐标如下表6.2.4→的最短路径为：O B6.1.3机器人从O(0, 0)出发，O C→的最短路径由圆弧角三角形定理可得：采用10单位半径过弯路径最短：通过观察可得如下避障行进方案，如图6.1.3由于该线路同样较复杂，可通过大致筛选，仅考虑其中的直线段长度.将通过障碍物1上边沿的线路称为上线路，通过下边沿的线路称为下线路1）考虑上线路中最短路径：上线路中如图6.1.3.1分两大段，上半段：线路A、B、C，下半段：线路D、E对上半段的线路进行只计算线段的粗筛选：计算统计可得三线路的粗选长度：如对下半段的线路进行只计算线段的粗筛选： 计算统计可得三线路的粗选长度：如表6.1.62）考虑下线路中最短路径： 如图图6.1.3.2对下线路的线路进行只计算线段的筛选：计算统计可得线路的长度：下表6.1.7为路线一的各段线路总长对于同一条路径上的两个相邻点(),i i x y 、()11,i i x y ++来说，如果这两点之间的路径为直线段时，用通式1L 计算；如果这两点之间的路径为弧线段时，可用通式2L 计算：1L 222011002-((-)(-))22=arccos()i i i i x x y y L ρρρ+++⨯下表6.2.8为路线二的各段线路总长下线路的两段线路对比得：线路一最短为：950.84综合上线段、下线段可得：线路一最短.各切点坐标如下表6.1.9表6.1.96.1.4机器人从O(0, 0)出发，O A B C O →→→→的最短路径 由圆弧角三角形定理可得：采用10单位半径过弯路径最短：6.1.4.1A B →的最短路径求解： 通过实际规划可得如下A B →的避障行进最短方案：如图6.1.4.16.1.4.2B C →的最短路径求解：通过实际规划可得如下A B →的避障行进最短方案：如图6.1.4.1对线路一、二进行大致选可得下表表6.1.10则可知路线一距离最近对于同一条路径上的两个相邻点(),iix y 、()11,i i x y ++来说，如果这两点之间的路径为直线段时，用通式1L 计算；如果这两点之间的路径为弧线段时，可用通式2L 计算：1L 222011002-((-)(-))22=arccos()i i i i x x y y L ρρρ+++⨯6.1.4.3线路经过A 、B 、C 的圆弧处理问题为使经过A 、B 、C 的圆弧路线最短，在A 与相邻切点的连线形成的夹角的平分线，以该角的平分线为基础，在该线上做与点A 相切的半径为10个单位的圆，则此时通过该构造圆与相邻圆弧的切线连接就产生了，进而保证了机器人的圆弧过弯和线路最短. 点A 的圆弧处理结果如图6.1.4.3则综上所述：求得各线短的最短路径，则可计算并统计出线段总长及各切点坐标如下表表6.1.116.2问题二的模型建立与求解：由于O→A 过程中，机器人至少要经过一次转弯；因为转弯时的速度一般小于直线行走的最大速度，又由分析指出转弯次数越多，转弯路径越远，转弯所花费的时间也越长.所以可以确定有且只有一次转弯时才存在最短时间路径.故以下就仅考虑只经过一次转弯的情形.机器人由起点到终点所用时间121255O AOQ Q AQ Q t v →=++，对于每种固定的转弯半径来说，转弯路径所在的圆的圆心与点(80,210)连线垂直平分该转弯路径所在的圆弧时，所得的总路径长度最短.如图6.2.1所示.对于已知条件中的最大转弯速度为21.0100e1)(ρρ-+==v v v ，其中ρ是转弯半径通过matlab 画出其图像，见程序02 如图6.2.2根据图6.1中所示，当1013R ≤<时，v 随R 增加而增加；当13R ≥时，v 已非常趋近于5单位/秒，此时可以看做v 不随R 增加而变化了.于是可以分两种情况解决本问题：1)当13R ≥时，由于O→A 整个过程的平均速度可以达到最大05v =单位/秒，以这样的速度沿最小的路径就可以使到达A 的时间最短.通过问题一中对机器人O→A 最短路径的分析，可知其最小时间路径应在OA 连线左上方区域；同时根据所建立并证明的圆弧角三角形定理可以知道，所得路径的转弯半径应为13个单位（如图6.2.3）1236.1392OQ =, 120.9077Q Q =,2223.1903Q A =,总长度： 1122++471.1296L OQ Q Q Q A == 总时间：1212471.135594.225595O AOQ Q A Q Q L t v →=++===（秒）2)当1013R ≤<时，图6.2取自原题目图中的一部分，其中(0,0)O ，2(80,210)O ，(300,300)A 点的坐标均已给出.1Q 、2Q 分别为OQ1和OQ2与1O 的切点，其中1O 又与2O 相切于3Q 点.假设半径R 已知，1O 、1Q 、2Q 、3Q 的坐标分别为00(,)x y 、11(,)x y 、22(,)x y 、33(,)x y ，则可列出如下方程组：2221010()()x x y y R -+-= 2222020()()x x y y R -+-= 2223030()()x x y y R -+-= 22233(80)(210)10x y -+-=21302130()()()()0x x x x y y y y --+--=310302108080y y y x x --=-- 110110()()0x x x y y y ⨯-+⨯-=202202()(300)()(300)0x x x y y y --+--=分别取R =10，11，12，13并解方程组可以得到总时间t 随转弯半径R 变化的数据，根据弧长公式得12Q Q AR =, A = 最终计算数据如下表：6.2.1最终会趋于94.22秒.因此，可以确定出最短时间路径.经过以上两种情况的讨论，可得最短时间路径， 具体坐标信息见表6.2.27 模型的评价与推广7.1优点：1)该模型采用较准确的及计算方法，数据精度高，可信度高. 2)该模型定义了新的几何名词与定理.具有一定的创新性. 3)利用估算法减少了计算量. 7.2缺点：程序利用率和执行率较低，计算量较大. 7.3应用与推广：自动控制技术 智能机器人技术 避障快速救援项目8参考文献[1]姜启源谢金星，数学建模，北京：高等教育出版社，2003[2]薛毅，数学建模基础，北京：北京工业大学出版社，2004[3]杨启帆方道元，数学建模，浙江，浙江大学出版社，19999附录程序01%三点确定圆方程%三点坐标x1=input('请输入x1=');y1=input('请输入y1=');x2=input('请输入x2=');y2=input('请输入y2=');x3=input('请输入x3=');y3=input('请输入y3=');if((y1==y2)&(y2==y3))disp('三点不构成圆!');elseif((y1~=y2)&(y2~=y3))k1=(x2-x1)/(y2-y1);k2=(x3-x2)/(y3-y2);endif(k1==k2)disp('三点不构成圆!');enda=2*(x2-x1);b=2*(y2-y1);c=x2*x2+y2*y2-x1*x1-y1*y1;d=2*(x3-x2);e=2*(y3-y2);f=x3*x3+y3*y3-x2*x2-y2*y2;disp('圆心为::');x=(b*f-e*c)/(b*d-e*a)y=(d*c-a*f)/(b*d-e*a)disp('半径为::');r=sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1))利用参考文献：/thread-790618-1-1.html/求助已知3点怎么用MATLAB编程求圆的方程/参考程序程序02function plot_v_rr=0:0.5:20;v=5./(1+exp(10-0.1*r.^2));plot(r,v)grid on。

机器人避障问题摘要移动机器人是一种能够在工作环境中自由移动并完成预定任务的智能系统，移动机器人的避障问题则是移动机器人控制领域的研究热点。

本文针对移动机器人的避障问题，建立了最短路径及最短时间路径的数学模型。

并应用于解决本题给定的路径规划问题，获得了满足问题需求的全部最优路径。

对于最短路径问题，本文分析了障碍物对移动机器人运行的影响，给出了最优移动规则；建立了简化的路径网格模型，将其抽象为由节点及边构成的两维图，并确定了其各项参数，再使用经典的Dijkstra算法获得可行的最短路径。

由于计算机行走过程与障碍物之间还需满足一定的间隔约束，故上述结果可能并非最优，故我们实际还需对次优的几条参考路径（也可通过以上Dijkstra算法获取）进行精算，经准确计算获得各段路径的具体位置后，确定实际的最短路径。

为方便计算，文中推导了自指定点向指定圆作切线，两个相离圆的内、外切线方程的解析表达式，给出了闭式结果，作为MATLAB编程的依据，从而大大提高了运算处理的速度及精度。

考虑到移动机器人需完成由O→A→B→C→O的多点移动，且中间不能折线运行，即机器人在通过上述点时一般必须以圆弧通过，且其上下游多数也是圆弧路径，其通过点并不固定。

为此，理论推导了该未知圆弧的约束公式，以各圆心之间距离最小作为优化条件，建立数学模型，再使用MATLAB中的fmincon有约束优化工具箱获得了理想的结果。

对于最短时间路径问题，本文分析了移动机器人弯道运行的速度曲线，特别是对O→A两点间的避障问题进行了详细的理论分析与推导，通过几何关系得出了转弯半径与总的移动距离、移动时间的严格数学关系，此后借助MATLAB优化函数fminsearch获得最佳的转弯半径。

经分析计算，得到下述结果：结论1：机器人完成O→A，O→B，O→C及O→A→B→C→O的最短路径总距离分别是：471.04、853.70、1050.50、2712.68单位长度；总时间分别是96.02、179.07、235.19及570.36秒。

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

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

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

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

我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：山西农业大学参赛队员(打印并签名) ：1. 邓浩然2. 成月红3. 罗太坚指导教师或指导教师组负责人(打印并签名)：王琳娟日期： 2012 年 9 月 10 日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：太阳能小屋的设计摘要太阳能作为一种新兴的绿色能源,越来越受到人们的重视，而光伏电池也逐渐成为太阳能光伏发电系统研究的主要环节，随着能源的耗竭，光伏发电技术越来越受到人们的重视，光伏发电的过程主要就是将接收到的太阳辐射利用光伏电池转变为电能的过程国内新能源商业化市场的培育和发展，是我国新能源产业得以可持续发展的重要前提，因此对光伏电池的研究具有重大意义。

对于问题一，首先建立Ray模型来求出小屋两个倾斜面上所接受到的太阳辐射强度，并利用Matlab软件编程计算出一年中每天每小时的太阳辐射总量。

由于在不同表面上，即使是相同型号的电池也不能进行串、并联连接，故可以对各个面单独进行分析。

机器人避障问题模型的几何画板解法探析作者：刘晓可孙志杰来源：《科技探索》2012年第10期摘要：本文对2012年全国大学生数学建模竞赛D题“机器人行走避障问题”，给出了利用“几何画板”这一数学软件进行求解的方法，并对该方法的优缺点进行了分析。

关键词：数学模型机器人避障几何画板2012年全国大学生数学建模竞赛D题“机器人行走避障问题”如下：在一个800×800的平面场景图中，原点O（0， 0）点处有一个机器人，它只能在该平面场景范围内活动。

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

规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。

机器人不能折线转弯，转弯路径由与直线路径相切的圆弧组成，每个圆弧的半径最小为10个单位。

为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位。

计算机器人从O（0，0）出发，O→A、O→B、O→C和O→A→B→C→O的最短路径。

这个题目是平面区域的最短路径问题，难度在于路线的具体长度和拐点的坐标不容易计算，但可以利用几何画板的度量与标记坐标的功能实现求解，具体做法为：1. 在几何画板中画出平面区域的相关障碍物。

2. 先目测可能的最短路线并画出。

3. 计算几条路线的总长并进行比较。

4. 选取出最短的路线，并标记拐点的坐标。

下面是针对O→C的具体做法：如图，首先选取两条可能的最短路线，再利用几何画板的度量功能，分别计算出总长度。

经计算，S1=1087.37，S2=1102.32。

因为，S1问题中到其他点的路径可以用类似方法求得，在这里不一一表述。

该方法的优点是简单易操作、直观性强，缺点是计算结果没有用matlab等数学软件求解的精确，但现有的精确度已经足够，因此其不失为一个简单高效的方法。

参考文献：[1]赵静，数学建模与数学实验，北京：高等教育出版社，2008。

机器人避障问题摘要本文研究了机器人避障最短路径和最短时间路径的问题。

主要研究了在一个区域中存在12个不同形状障碍物，由出发点到达目标点以及由出发点经过途中的若干目标点到达最终目标点的多种情形，寻找出一条恰当的从给出发点到目标点的运动路径使机器人在运动中能安全、无碰撞的绕过障碍物而使用的路径和时间最短。

由于规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径，机器人不能折线转弯。

所以只要给定的出发点到目标点存在至少一个障碍物，我们都可以认为最短路径一定是由线和圆弧所组成，因此我们建立了切线圆结构，这样无论路径多么复杂，我们都可以将路径划分为若干个这种切线圆结构来求解。

在没有危险碰撞的情况下，圆弧的半径越小，路径应该越短，因此我们尽量选择最小的圆弧半径以达到最优。

对于途中经过节点的再到达目标点的状况，我们采用了两种方案，一种是在拐点和节点都采用最小转弯半径的形式，另一种是适当扩大拐点处的转弯半径，使得机器人能够沿直线通过途中的目标点。

然后建立了最优化模型对两种方案分别进行求解，把可能路径的最短路径采用穷举法列举出来，用lingo 工具箱求解得出了机器人从O(0, 0)出发，O →A 、O →B 、O →C 和O →A →B →C →O 的最短路径；利用matlab 中的fminbnd 函数求极值的方法求出了机器人从O (0, 0)出发，到达A 的最短时间路径。

本文提出一种最短切线圆路径的规划方法，其涉及的理论并不高深，只是应用了几何知识和计算机程序、数学工具计算，计算简易，便于实现，能搞提高运行效率。

问题一O →A 最短路径为：OA L =471.0372 O →B 最短路径为：=1OB L 853.8014 O →C 最短路径为：4OC L =1054.0O →A →B →C →O 最短路径为：问题二机器人从O (0, 0)出发，到达A 的最短时间路径：最短时间是94.5649，圆弧的半径是11.5035,路径长4078.472=OA L关键词 最短路径；避障路径；最优化模型；解析几何；数学工具一 、问题重述图1是一个800×800的平面场景图，在原点O(0, 0)点处有一个机器人，它只能在该平面场景范围内活动。

2012年全国大学数学建模赛题D2012高教社杯全国大学生数学建模竞赛题目（请先阅读“全国大学生数学建模竞赛论文格式规范”）A题葡萄酒的评价确定葡萄酒质量时一般是通过聘请一批有资质的评酒员进行品评。

每个评酒员在对葡萄酒进行品尝后对其分类指标打分，然后求和得到其总分，从而确定葡萄酒的质量。

酿酒葡萄的好坏与所酿葡萄酒的质量有直接的关系，葡萄酒和酿酒葡萄检测的理化指标会在一定程度上反映葡萄酒和葡萄的质量。

附件1给出了某一年份一些葡萄酒的评价结果，附件2和附件3分别给出了该年份这些葡萄酒的和酿酒葡萄的成分数据。

请尝试建立数学模型讨论下列问题：1. 分析附件1中两组评酒员的评价结果有无显著性差异，哪一组结果更可信？2. 根据酿酒葡萄的理化指标和葡萄酒的质量对这些酿酒葡萄进行分级。

3. 分析酿酒葡萄与葡萄酒的理化指标之间的联系。

4．分析酿酒葡萄和葡萄酒的理化指标对葡萄酒质量的影响，并论证能否用葡萄和葡萄酒的理化指标来评价葡萄酒的质量？附件1：葡萄酒品尝评分表（含4个表格）附件2：葡萄和葡萄酒的理化指标（含2个表格）附件3：葡萄和葡萄酒的芳香物质（含4个表格）东立面南立面透视图西立面（请先阅读“全国大学生数学建模竞赛论文格式规范”）C题脑卒中发病环境因素分析及干预脑卒中（俗称脑中风）是目前威胁人类生命的严重疾病之一，它的发生是一个漫长的过程，一旦得病就很难逆转。

这种疾病的诱发已经被证实与环境因素，包括气温和湿度之间存在密切的关系。

对脑卒中的发病环境因素进行分析，其目的是为了进行疾病的风险评估，对脑卒中高危人群能够及时采取干预措施，也让尚未得病的健康人，或者亚健康人了解自己得脑卒中风险程度，进行自我保护。

同时，通过数据模型的建立，掌握疾病发病率的规律，对于卫生行政部门和医疗机构合理调配医务力量、改善就诊治疗环境、配置床位和医疗药物等都具有实际的指导意义。

数据（见Appendix-C1）来源于中国某城市各家医院2007年1月至2010年12月的脑卒中发病病例信息以及相应期间当地的逐日气象资料（Appendix-C2）。

A题葡萄酒的评价确定葡萄酒质量时一般是通过聘请一批有资质的评酒员进行品评。

每个评酒员在对葡萄酒进行品尝后对其分类指标打分，然后求和得到其总分，从而确定葡萄酒的质量。

酿酒葡萄的好坏与所酿葡萄酒的质量有直接的关系，葡萄酒和酿酒葡萄检测的理化指标会在一定程度上反映葡萄酒和葡萄的质量。

附件1给出了某一年份一些葡萄酒的评价结果，附件2和附件3分别给出了该年份这些葡萄酒的和酿酒葡萄的成分数据。

请尝试建立数学模型讨论下列问题：1. 分析附件1中两组评酒员的评价结果有无显著性差异，哪一组结果更可信？2. 根据酿酒葡萄的理化指标和葡萄酒的质量对这些酿酒葡萄进行分级。

3. 分析酿酒葡萄与葡萄酒的理化指标之间的联系。

4．分析酿酒葡萄和葡萄酒的理化指标对葡萄酒质量的影响，并论证能否用葡萄和葡萄酒的理化指标来评价葡萄酒的质量？附件1：葡萄酒品尝评分表（含4个表格）附件2：葡萄和葡萄酒的理化指标（含2个表格）附件3：葡萄和葡萄酒的芳香物质（含4个表格）B题太阳能小屋的设计在设计太阳能小屋时，需在建筑物外表面（屋顶及外墙）铺设光伏电池，光伏电池组件所产生的直流电需要经过逆变器转换成220V交流电才能供家庭使用，并将剩余电量输入电网。

不同种类的光伏电池每峰瓦的价格差别很大，且每峰瓦的实际发电效率或发电量还受诸多因素的影响，如太阳辐射强度、光线入射角、环境、建筑物所处的地理纬度、地区的气候与气象条件、安装部位及方式（贴附或架空）等。

因此，在太阳能小屋的设计中，研究光伏电池在小屋外表面的优化铺设是很重要的问题。

附件1-7提供了相关信息。

请参考附件提供的数据，对下列三个问题，分别给出小屋外表面光伏电池的铺设方案，使小屋的全年太阳能光伏发电总量尽可能大，而单位发电量的费用尽可能小，并计算出小屋光伏电池35年寿命期内的发电总量、经济效益（当前民用电价按0.5元/kWh计算）及投资的回收年限。

在求解每个问题时，都要求配有图示，给出小屋各外表面电池组件铺设分组阵列图形及组件连接方式（串、并联）示意图，也要给出电池组件分组阵列容量及选配逆变器规格列表。