数学建模江厚翔

2012高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：D我们的参赛报名号为（如果赛区设置报名号的话）：Y5203所属学校（请填写完整的全名）：西安航空职业技术学院参赛队员(打印并签名)：1.江厚翔（组长）2.刘祥3.屈杰指导教师或指导教师组负责人(打印并签名)：刘宝利日期：2012年9月10日赛区评阅编号（由赛区组委会评阅前进行编号）：2012高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1机器人避障最短路径模型摘要避障最短路径和最短时间路径成为机器人大赛中获胜的关键，本文以研究避障最短路径和最短时间路径为出发点，首先简单推断求解了行走路径为圆弧段时的最小半径。其次，当已知圆和过圆外两点的切线段时，求出由切线段和切点出的圆弧组成的最短路径。则对于问题一：为了使复杂的移动机器人路径问题得到简化，并减少可行路径的计算量,建立图论模型，对此问题的环境，给其赋予权值，将避障路径问题转化为多阶段决策问题，再利用动态规划得到几条较短线路。由于上述方法未考虑到转弯问题，所以需要改进模型对其删选的路线在进行精算。对可能遇到每种障碍物进行分析并建立相应的规划模型。最后，将复杂的线路问题简化为各种简单环境下的最短路径，从而将复杂的路径分割成n个最简单的模型，运用Matlab软件对其优化求解，最终得出最短路径分别为：1）O→A的最短距离为471.04个单位2）O→B的最短距离为860.08个单位3）O→C的最短距离为1090.54个单位4）O→A→B→C→O的最短距离为2708.26个单位对于问题二：构造时间和行走路径中圆弧的半径之间的函数关系，对其求导，利用极值定理得到当半径.511r时，所走路径用时最短。求得最短时间路径长度为472.40关键字：图论动态规划分割线路Matlab软件2一.问题重述图1是一个800×800的平面场景图，在原点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)上顶点坐标(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个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。机器人直线行走的最大速度为50v个单位/秒。机器人转弯时，最大转弯速度为21.0100e1)(vvv，其中是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中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的最短时间路径。注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机3器人行走的总距离和总时间。·问题一:求机器人从O(0,0)出发，O→A、O→B、O→C和O→A→B→C→O的最短路径。第一步：对O→A、O→B、O→C和O→A→B→C→O的各种可能性路径进行粗算，即：将所经过的障碍物拐点和终点与起点用折线连接起来，形成有向图论，给其赋予权值，找出可能的最短路径。第二步：对第一步找出的几条可能最短路线采用拉绳子的方法排除第一步中存在的弊端（没有考虑到弧线路径），我们先可以用包络线画出机器人行走的危险区域，这样的话，拐角处就是一个半径为10的四分之一圆弧，然后采用拉绳子的方法寻找最短路径（比如求O和A之间的最短路径，我们就可以连接O和A之间的一段绳子，以拐角处的圆弧为支撑拉紧，那么这段绳子的长度便是O到A的一条最短距离）。从而找出最短的路线。第三步：用建立的模型对最短的路线进行求解，求出最短的路程值。问题二:针对机器人从O→A的最短时间路径，我们建立求时间最短的路径模型。二.模型假设1.假设机器人转弯时与地面垂直；2.假设机器人在转弯时的减速和加速都是瞬时的，时间可以忽略不计；3.假设机器人直线行走和曲线行走都为匀速;4.假设机器人抽象为一个点来处理；5.假设机器人内部电量的变化不会影响机器人的速度。三.符号说明1.S：表示机器人行走的路程总和；2.Li：表示第i个分割路径的长度；3.r：表示转弯半径；4.v0：表示机器人在直线上行走的最大速度；5．v：表示机器人在圆弧上的最大速度；6．t:表示机器人所运动的时间；7.:k表示障碍物上任意一点到机器人的距离。四.模型的建立4.1模型准备4.1.1确定行走路径中的某段为圆弧时的最小半径。（1）两圆内切，即顶点相同：4图1由上图易知:AD+DEAG+GE,所以可得出当半径越小时路程越短，结合题意故拐弯求最短路程时半径应该取10个单位。2．两圆为同心圆：图2由图知:当圆半径越小时，A到B之间距离最短，而题意最小安全半径为10个单位，故求最短路程问题，半径应取为10个单位。4.1.2重要结论已知圆O和圆外两点A，B,过A,B做圆的切线段，求由切线段和切点出的圆弧组成的最短路径。图35求解过程分两种情况讨论，如下所示：（1）假设最短路径由两条切线和一段圆弧组成时。。如图3，设A1,1yx错误!未找到引用源。为起点，B2,2yx错误!未找到引用源。为目标点，C3,3yx错误!未找到引用源。和D4,4yx错误!未找到引用源。分别为机器人经过拐点分别于隔离危险线拐角小圆弧的切点，圆心为O5,5yx错误!未找到引用源。，圆的半径为r，AB的长度为a，AO的长度为b，BO的长度为c，角度AOB=,AOC=,BOD=，COD.求AC,CD,BD的总长度，设为L.解法如下：212212yyxxa215215yyxxb225225yyxxcAOB在中：bcacb2arccos222在RtAOC：brarc在RtAOC中：arccosrc所以：2从而可得：2222Lbrcrr6图42）：假设最短路径为两段圆弧的内公切线组成。图5我们假设两圆心坐标分别为Oyx1,1和O`yx2,2，半径为r和R，M点为yx3,3，那么我们容易可以求得：DMOOEM`,`DMOEMO7所以EMOODM`RrEOODMOOM``RRrRRryyyxxx213213这样我们就可以利用二中的方法，先求A到M，再求M到B，这样分两段就可以求解。同理如果有更多的转弯，我们同样可以按照此种方法分解。3）假设最短路径为两段圆弧外切线组成。图6这里我们依然设圆心坐标分别为Oyx1,1和o`yx2,2,Cyx33,，Ayx44,，1`COO,2`OEO,3COD，AO斜率为k2，BO`的斜率为k1，半径为r和R。所以可以推导出212212`yyxxoo，oc22`rRooooyOoooc21221arccos`arccos有角度关系可得213所以：Cox133cosCoy133sin由于OA//O`B,可得：kxxyyk2232318再由图分析可得214214yyxxr与xxyyk14142即可推导出yx44,这样我们就可以再次利用环境一的方法进行求解。4.2模型的建立：4.2.1对问题一：机器人从O点出发到达指定位置，将其路径划分为n个由圆弧和线段组成的简单模型即环境一,那么目标函数可以表示为：niiLSMin11010.krts4.2.2对问题二短时间模最型：所求单个路径:2222Lbrcrr所以evvrcvrbrrt21.01000220221化简为vercrbrrt01.010222221min从而找出r的值，所经过的路线为最短时间路线。五．模型的求解5.1问题一1）O→A如图，很显然从O到A就两条路径，直接可以通过最简单的模型求解方法对其进行求解，计算所得最小路径为O到A的最短路径。2)O→B如图，经过粗算取出几条可能的最短路线，我们可以分别对其进行求解，计算所得最小路径为O到B的最短路径。3)O→C如图，同2）经过粗算取出几条可能的最短路线，接着分别对其进行求解，计算9所得最小路径为O到C的最小路径。4）O→A→B→C→O分别对A→B,B→C按前三种方法求出其最短路径，接着由1)找出的O→A最短路径和由3）找出的O→C最短路径可以得到O→A→B→C→O的最短路径。图中的路径即为O→A→B→C→O的最短路径。AO求解过程图7对AO路径粗算可得：路线一：4933.4625651050510路线二：6972.4876251050510故可得路线一较短，因此对路线一进行精算。10图8利用上模型可得AO求解的精值为471.0372BO求解过程图911对BO路径粗算可得：路线一：817.255502706061252632593600路线二：699.754882550270853212550510路线三：1293.840955502708592.52556510路线四：933.469116293104661061252632593600路线五：956.7373829310233253212550510路线六：955.2496162931038601026510故可得路线一，二较短，因此对路线一进行精算。图10利用上模型可得BO求精解为:路线一：860.08166.9790.0583.17131.85388.4路线二:878.27166173.39216.95321.93所