1d1406理工学院参赛队员

2012高教社杯大学生数学建模竞赛区评阅编号（由赛区评阅前进行编号赛区评阅记录（可供赛区评阅时使用统一编号（由赛区送交前编号评阅编号（ 评阅前进行编号针对问题一为使机器人不与物碰撞在原物的边界向外延伸10个单位，10人可以贴着“安全路径”行走。Floyd算法得到机器人从O(0,0)发，O→A、O→B、O→CO→A→B→C→O的折线最短距离分别为：471.041853.088 96.018建立模型二，利用lingo12求解各切点即每次的起点与终点坐标。最后，利用7.0（结果见表五至表八针对问题二，求解O到A的最短时间路径，此时最短时间与最短线路、最短拐弯次数以及拐弯半径的大小有关，由拐弯半径与速度的函数关系式：vv(r)5/(1e1001r2

用7.0绘制图像分析和探讨可知：在半径满10r14时，机器人拐弯速度趋近极大值v0定合适的半径使得行走的时间最短我们利用问题一中求解的由O到A的最短线路中合适半径r13.1887以及此时对应的拐弯圆弧的圆心坐标Q(82.285,207.78。随着拐弯半径及圆心的改变会使得搜索出来路径中的切点发生改变得到两切点坐标为T3(72.832,211.038、T4(78.777,217.1410T94.2182s0：机器人避 图 Floyd算 非线性目标规 最佳半—问题重物，物的数学描述如下表1(300,边长2圆心坐标(550,450)，半径3(360,4(280,上顶点坐标(345,210)，右下顶点坐标(410,5(80,边长6(60,上顶点坐标(150,435)，右下顶点坐标(235,7(0,长220，宽8(150,底边长90，左上顶点坐标(180,9(370,长60，宽(540,边长(640,边长(500,长300，宽机器人直线行走的最大速度为v05个单位/vv()

1e1001

，是转弯半径。数学模型。对场景图中4个点O(0,0)，A(300,300)，B(100,700)，C(700,640)具体计机器人从O00)出发，到达A图 二问题分10lingo三模型假目标点与物的距离至少超过10个单位机器人在直线路径中始终保持最大速度V05个单位/机器人在转弯路径中始终保持最大速度vv()

1e1001

四符号说按逆时针方向顺序第i物的第j个顶点的坐Q表示两直线与圆Ql表示两直线与圆QPP vr表示机器人从OATT2五模型前准10称Qij①Q11(300,400)称Qij①Q11(300,400)Q12(500,400)Q13(500,,600)Q14③形Q31(360,240)Q32(500,240)Q33(540,330)Q34④Q41(280,100)Q32(410,100)Q33⑤ ⑥ Q62(150,435)Q63⑦ ⑧形Q81(150,600)Q82(240,600)Q83 ⑨Q91(370,680)Q92(430,680)Q93 ⑩Q101(540,600)Q102(670,600)Q103(670,730)Q104Q111(640,520)Q112(720,520)Q11 4(0,,)0)Q121(500,140)Q112(800,140)Q113 Q114根据题目要求在图1的平面场景中机器人行走线路与物间的最近距离为10个单位。因此，物在原有大小的基础上扩大10个单位。此时，所有物2所示：图2物在原有大小的基础上扩大10个单位示意对于无物的情况通过模型前准备，根据两点间直线最短原理，连接OA、OB、OC及O-A-B-C-O可得Q相切后的交点Q'(xy3 3EOa定理一：EOaM4当运动物体M沿探索线a前进，如果碰到物O，则O的顶点必定分布在A的两侧，且部分边是M可见的(图中的实线部分)，部分边是不可见的(虚线边)，吧M可见的物的顶点分成两组，矢量a左侧的顶点L组，右侧归入R组。另外设VLVR分别是LRa最远的两个顶点。VLVRa更远C=R，否则令C=L,VC就是登陆点。M绕过物时首先向登陆点靠近。找到登陆点后，接着就是如何绕过O，SVCVCE连接。视VC为当前点，记作P，如果PE不与物香蕉，表明已经绕过物，称此P点位M绕过物O的分离点。否则把当前点从P出发顺着或逆着O的边界移动到绕过一个物后如果后面还有物就把当前点作为新的起点重复上述过程，知道绕过所有物到达终点E。运用以上原理经过逐步搜索可以找到机器人从OABCO-A-B-O的初步最短路径，分析发现：所有初步确定的最短路径都以物顶点为转弯点。物顶点为圆心，10Q相切后的交点Qxy 也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。所以我们以10个单位为半径对各物进行安全包裹，由定理一确定了初步筛选的最短路径以物各顶点为转弯点的规律，在实际情况下，机器人行走路径由直线—圆弧—直2：5PPPQ'PQ1 定理二：(分离定理)对平面中的凸集RRK，存在直线l,l分离RK，即RKl（注：对一般的凸集RRKRK证明MMEFO 6如图3所示AE、EF、FBAE′，E′F′，F′B围成的区域R是一凸集。利用分离定理易证最短径不可能经过R外的点，我们采用反证法：设Γ为最短路径，Γ过R外的一点M，则必存在直线l分离M与R，由于路径Γ是连续曲线A沿Γ到M，必交lM1MΓBlM2。这样，直线M1M2的长度必小于路径M1MM2的长度，与Γ是A到B的最短路径，至此，我们已证明最短路径必在凸集R内。不妨设路径经圆的上方到达B点，则弧EF必在路径F上，又直线段AE是由AE的最短路径，直线FB是由F到B的最短路径。与此同时，若可行区域的边界是光滑曲圆Qij相切后的交点P1和P2之间的劣弧长比两切点与两直线交点的距离之和更短。即：PPPQ'P劣弧1

OABCO-A-B-C-O7(O-AO-B8（O-CA-B-C六模型的建立与求本文研究的是机器人避障设计问题，找到达指定目标点的最短路径和时间，将路线图转化为网络图，运用图论知识求解最短路径和最短时间，采用逐步优化法建立模型。（一）问题(1)最短路径网转化为网络图形，图论知识寻找折线转弯最短路径。由定理一二可得：以逆时针方向第i个 物的第j个顶点的圆心Qij的下表序号表示折线最短距离根据已知位置点的坐标和连接情况，利用绘制出O-A、O-B、O-C的潜在短路径赋权图，再通过对A-BB-CO-A-B-C-O（一）其中，O-A图 O-A折线路径赋权FloydD

ij

dij

当（vivj其D(0)DD(k)(d(k)

d(k)min[d(k1),d(k1)d(k1)计 D(n)(d(n)

d(n

其

中元素

就是 j的最短路长根据以上步骤，首先计算O-A权矩阵D

2 2

0

211.7 000000 A=v 00 9 9

图 O-A折线最短路同理，按求解O-Afloyd（1.1）以依次求解O-B、O-CA-B、B-CO-A-B-C-O（1.2）（二）O-B图 O-B折线路径赋权11：11O-B（三）O-C图 O-C折线路径赋权图利用软件编程求解得：O-C折线最短路径为1099.3；所需最短时间为12O-C（四）A-BB-C图 A-B折线路径赋权图图 B-C折线路径赋权图利用软件编程求解得A-B469.2；所需最短时间为B-C709.18；图 A-B折线最短路 图16B-C折线最短路结合以上对O-AO-CO-A-B-C-O折线段总长度为：2752.08所需最短时间为：550.416。1515O-A-B-C-O 物且考虑转弯路径的实际情况下两直线与圆Qij相切后的交点P1和P2之间的劣弧长较两切点与两直线交点的距离之和短。即：劣PPPQ'P1 1

ij坐标，进而求解得到两切点间的劣弧长。对于每一条最短路径中的每一段弧长及切点坐标的求解，我们采用分段求解法，以O-A取O-A16DcDcCoabO16O-A其中设O（为起点为相对于A的终点和分别为机器人经过拐点分别 线拐角小圆弧的切点，圆心为 ，的半径为r，AB的长度为a，AO的长度为b，BO的长度为c，角度AOB=,AOC=ADB

(x(xx)2(yy (xx(xx)2(yy (x(xx)2(yy 在AOB中在RtAOC

b2c2 RtAOC中b2b2r2c2r2

barccosc2综合以上分析

L

联立方利用lingo求解切点即每次的起始点与终点坐标，利用求解（1.3）结果见如下表格：表五O-AO-度间表六O-B度表七O-C度表八O-A-B-C-OO-A-B-O标间）2（二）问题(2)及其求短线拐弯次数以及拐弯半径的大小有关，由拐弯半径与速度的函数关系式：vv(r)5/(1e1001r2)可以 绘制出其大致图像如下54拐弯拐弯速度21 拐弯半17由此我们可以大致分析得到在半径满足10r14时，机器人拐弯时间最少。因为如果r

3 区域一点选择一条由O1到A2的最短时间的路径。O1和A2与半径为r1的切点分别为Q1Q2点，O1和A2与半径为r2的切3QQQQ

点，现过O1A2分别作同心圆并与Q1Q2相交，再过

Q4Q并交同心圆上与CD两点。若14rr 由O1到Q4到Q3A2的距离是大于由O1到Q1到Q2A2的距离的。即说lingo的搜索功能对拐弯的半径及其圆心进行在模型一种我们已经得到由OA的最短路径，以及两切点的坐标Q(x,y

Q(x,y

O()

(213.170.5)Q2(9)

A(30300)OQ：x

70.51

QA

300)300219.4

300 12MinT12x1(213.14/70.51)2(300219.4)/(30076.60)(x2

2300)2(xx)2(yy

r (x2x)(yy020 020

rV0 V0

/(1e(1001r2) 2r2(xx)2(yya )11

a

2r(x(x)2(y11(x300)2(y22TS/ TS/ (x(x80)2(y00r

0V0

lingo软件求解(2.1)r13.1887标间七模型的评价与推1、本文通过对机器人避障问题的全面考虑，对于折线转弯理想模型我们引入绕物用图论知识求解最短路径和最短时间，采用floyd算法逐步优化建立模型。这中网络图八参考文【1】姜启源谢金星《数学模型（第三版，：高等教育【2】数学建模与数学实验：高等教育【3】朱德通《最优化模型与实验》同济大学【4】编写组《运筹学（第三版》【5】肖华勇,实用数学建模与软件应用,西北工业大学附录1.1functionA=[0293230.87437.5245.2infinfinf2930infinfinf209211.7inf230.87inf0infinfinfinfinf437.5infinf0infinfinfinf infinfinf0infinf inf209infinfinf0infinfinf211.7infinfinfinf0infinfinfinfinfinf0inf243.53256.9214fori=1:nforforforforifD(i,j)=D(i,k)+D(k,j)%¸üÐÂD(i,j)£¬ËµÃ÷ͨ¹ýkµÄ·³Ì¸ü¶Ì

D

function[Pu]=func2(w,k1,k2)n=length(w);U=w;m=whilem<=nfori=1:n;forj=ifU(i,j)>U(i,m)+

U(i,j)=U(i,m)+m=m+u=k=1;P1(k)=V=ones(1,n)*100;kk=k2;whilekk~=k1fori=1:nV(1,i)=U(k1,kk)-w(i,kk);ifV(1,i)==U(k1,i)

wrow=forj=length(wrow):(-1):1P(k)=P1(wrow(j));A=[0293437.46245.2230.87infinfinfinfinfinfinfinfinfinfinfinfinfinf2930infinfinf196.1infinfinfinfinfinfinfinfinfinfinfinfinf437.46inf0infinfinf162.5163.1infinfinfinfinfinfinfinfinfinfinf245.2infinf0infinfinfinf45.9 240.4infinfinfinfinfinfinfinfinf230.87infinfinf0infinfinfinf196infinfinfinfinfinfinfinfinfinf196.1infinfinf0infinfinfinf80infinfinfinfinfinfinfinfinfinf162.5infinfinf0infinfinfinf170.6infinfinfinfinfinfinfinfinf163.1infinfinfinf0infinf169.1infinfinfinfinfinfinfinfinfinfinf45.9 infinfinfinf0200.2301.3infinfinfinfinfinfinfinfinfinfinf240.4196infinfinf200.20171.6106.6322.2inf300infinfinfinfinfinfinfinfinf80infinfinf171.60infinf80131.1infinfinfinfinfinfinfinfinfinf170.6169.1 301.3106.6inf0inf161.6infinfinfinfinfinfinfinfinfinfinfinfinfinf322.2infinf0infinf80.2infinfinfinfinfinfinfinfinfinfinfinfinf80161.6inf0infinf106.9infinfinfinfinfinfinfinfinfinfinf300131.1infinfinf0111.4infinfinfinfinfinfinfinfinfinfinfinfinf infinf0111.4infinfinfinfinfinfinfinfinfinfinfinfinf106.9111.40infinfinfinfinfinfinfinfinfinfinfinfinfinfinfinf111.40infinfinfinfinfinfinfinfinfinfinfinfinfinfinfinf A=[0230.87245.2437.46infinfinfinfinfinfinfinfinfinf230.870infinf344.9274.8infinfinfinfinfinfinfinf245.2inf0infinfinf infinfinfinfinfinfinf437.46infinf0infinfinf135.2infinfinfinfinfinfinfinf344.9infinf0infinfinfinfinfinf238.4infinfinfinf274.8infinfinf0infinf1622infinfinfinfinfinfinf45.9 infinfinf0infinf160.2infinfinfinfinfinfinfinf135.2infinfinf0infinf25.9 infinfinfinfinfinfinfinfinf162infinf0infinfinf358.3infinfinfinfinfinfinf2160.2infinf0infinfinfinfinfinfinfinfinfinfinfinf infinf0inf358.3infinfinfinfinf238.4infinfinfinfinfinf0163.3infinfinfinfinfinfinfinfinfinf358.3 inf358.3163.30100infinfinfinfinfinfinfinfinfinfinfinfinf100042.4infinfinfinfinfinfinfinfinfinfinfinfinf42.4 A=[0174.6250 infinfinfinfinfinf174.6080infinfinfinf infinf250800161.6159.6 infinf inf161.60infinfinf220infinfinfinf159.6inf0106.8infinfinf111.4