机器人壁障问题——数学建模.doc

　　　　　　 　 　　 　 　　 机器人避障问题　 　　 　 　　 　 　 　 　 　 　 　 　 　　　 　 　 　 摘　 要：当今科学技术日益发达,高科技产品尤其就是机器人在我们日常生活中运用得越来越广泛，它能够代替人类完成许许多多得工作,但如何能让机器人自动化得完成人类交给得任务成为设计机器人得关键.我们做此题就就是为了更好得利用机器人为我们提供方便,提高生活质量，若机器人程序设计不当不仅不会给人类带来方便，还很有可能给我们得生活带来更多得麻烦。本题中提出了如何让机器人能够自动识别障碍物，保证机器人能够在合理区域行走,并设计出如何能让机器人自动判断最短路程于最短时间下行走路线得问题.所以解决好本题可以为我们得生活提供帮助。本文通过运用两点之间直线最短理论,优化问题,最短路问题，图论，以及运用ｍaｔlab软件编程及作图得方法，阐述了机器人避障问题得相对优化方案得解决办法，即“两点之间直线最好，转弯半径最小”得理论,通过计算中得比较与选择把四条最短路径都求出了相对最优解，论证了转弯速度不会随着r得增加一直增大或减小，而就是有一个最小极点得思想。从而求出了r，以及最短得时间。
问题一,通过对最短路问题得分析,我们很容易分解成线圆结构来求解,然后把可能路径得最短路径采用穷举法列举出来,最终得出最短路径:
O　A　 最短路径为：４７1、03７2
O B 最短路径为:８38、0466
O C 　最短路径为:1085、753１
O→A→B→C→O 最短路径为:2８34、6591
问题二,通过建立时间ｔ与r得关系式，得出r在１１、5０4时，从O到A得时间相对最短，最短时间为９８、6060０4。
我们可以利用此篇论文解决生活中实际得问题，在计算时可以节省大量得时间,使机器人又准确又完善得完成我们给定得任务，从而进行拓展，给定区域内任何两个点,我们都可求出其最短路径与走完全程得最快时间。从而可以让机器人帮助我们给家里打扫卫生或设计自动吸尘器等,也可使机器人在最短得时间完成工作，提高效率,延长机器人得使用寿命.
关键字：最短路问题 　优化问题 matlａb
　 　　 　　 　 　 　 　一 问题重述 　 　 　 　　 　　　随着现代科学技术日新月异得发展，机器人越来越多得出现在日常生活中，它既可以通过运行预先编排得程序为人类服务，根据人工智能程序自动处理一些生活中问题,进而协助或者相应地取代人类得工作，可以说机器人得创新与改进正一步步影响着人类得发展.如图1所示，该图就是一个80０×800得平面场景图,在原点O(0，０）点处有一个机器人，它只能在该平面范围内活动。机器人在活动中不能碰到障碍物及其向外延伸1０个单位得区域，障碍物由12个不同形状得图形组成,障碍物得数学描述如下表：
编号
障碍物名称
左下顶点坐标
其它特性描述
1
正方形
（3０0, 4００）
边长200
2
圆形

圆心坐标（５５0， 450）,半径7０
3
平行四边形
(３60， ２４０)
底边长140,左上顶点坐标（400， ３30)
４
三角形
（28０,　1０0）
上顶点坐标（３４5，　２１0)，右下顶点坐标（４10,　１00）
5
正方形
（80, ６0）
边长150
6
三角形
（６0，　３０0）
上顶点坐标（１50， 435）,右下顶点坐标（2３5,　3０0)
7
长方形
（0, 470)
长220，宽60
8
平行四边形
(1５０， 600)
底边长９0,左上顶点坐标（1８０, 680)
9
长方形
(37０,　680）
长６0，宽120
１0
正方形
（5４０， 6０0）
边长130
11
正方形
（640， 5２0)
边长80
12
长方形
（５００, 140)
长300,宽60
在图1中,在障碍物外指定一点为机器人要到达得目标点,机器人得行走路线由直线与与直线相切得圆弧组成,也可以由两条及以上圆弧组成。机器人不能折线转弯，必须经过与直线相切得圆弧转弯。每条圆弧得直径不小于１０个单位.
机器人直线行走得最大速度为个单位/秒。机器人转弯时，最大转弯速度为，其中就是转弯半径.如果超过该速度,机器人将发生侧翻,无法完成行走。
要解决机器人从区域中一点到达另一点得避障最短路径与最短时间路径，请建立数学模型，以达到最短路径与时间。对场景图中4个点Ｏ（0， 0），Ａ(300, ３0０),B(100, 70０),Ｃ（700， 640)，具体计算:
（１） 机器人从O（0,　0)出发,O→Ａ、O→B、O→Ｃ与O→Ａ→B→C→O得最短路径。
（2)　机器人从O (0， ０）出发，到达Ａ得最短时间路径.
注:要给出路径中每段直线段或圆弧得起点与终点坐标、圆弧得圆心坐标以及机器人行走得总距离与总时间.

　 图1
二　问题分析
2、1问题一
问题一中要求机器人从Ｏ(0,0）出发,按照上述规则求绕过障碍物到达目标点得最短路径,我们可以先设想机器人所走过得路径得各种情况。通过设想然后采用两点之间直线最短得原理寻找可能得最短路径（比如求Ｏ与A之间得最短路径,我们就可以连接O与Ａ，发现ＯＡ得对角线在OA得下方,所以从OＡ对角线得上方行走比下方距离短。在第一问求路径最短时尽量少走圆弧,所以在可能得情况下拐弯时最好走１0为半径得圆弧).之后采用穷举法列出O到每个目标点得可能路径得最短路径,最短路径由圆弧与直线组成,求出圆弧与直线得长就能求得路径,通过建立优化模型可求出最短路径。进而联立切线与圆得方程组及运用matｌaｂ软件求出各点坐标. 　 　 　 　　 　 　
2、2问题二
问题二需要求Ｏ到A得最短时间，这让我们考虑得就不仅仅就是路长得问题，还有了速度得问题。已知公式与得出直线比转弯得速度快且转弯速度与圆弧半径有关。我们可通过建立路程与速度得关系方程 求得时间得最优解. 　 　 　 　 　　 　 　 三　模型假设
1、 假设机器人能够抽象成点来处理。　　　 　 　　 　　 　　 　
2、 假设机器人能完整得走到终点,中途不会发生故障.
3、 假设机器人在离路障10个单位处不会发生故障,可以正常行走.
四 符号说明
符号
符号解释
切 点
:表示5号图形包络线上得点、 　 i=1，2,3
E：表示6号图形包络线上得点 i=1，2，３,4
Fi:表示７号图形包络线上得点 ｉ=1，2,３,4,5
Gi:表示8号图形包络线上得点 　　 i=１,2，3，４
Hi：表示9号图形包络线上得点 　　　i＝1,2，3，4
Ii：表示１0号图形包络线上得点 ｉ=１，2，３，4
Ji:表示１１号图形包络线上得点 　 　 ｉ=1，２，3，4
Ｋｉ：表示2号图形包络线上得点 　　 　 i=１,２
Li：表示3号图形包络线上得点 i=1，2
五 模型建立
5、1证明点到直线距离最短理论在最短路问题中起重要作用
通过起点与终点得连线,判断哪边路径离这条连线距离较近，进而选择出最优路径。如果中间有较多路障得话也可采取分步判断得方法，判断由较近路障附近得点决定.
如图二，求O到A最短路径。正方形对角线为BC,EE’，DＤ’分别为E,D到OA得距离，显然ＥE’〈　DD'，所以从OA得上方通过为最短路径.　
5、2基本模型求路径(1题）
５、2、1线圆模型
已知O（为起点,Ｂ(为目标点，D（与E（分别为机器人经过拐点分别于隔离危险线拐角小圆弧得切点,圆心为Ｏ1(，圆得半径为ｒ，OＢ得长度为ａ,OO1得长度为b,BO1得长度为c，角度 ,、通过余弦定理可算出，弧长=圆心角＊r,可求出OB得长度.
由此解法在mａtlaｂ编程，可求出已知起点与终点及圆心与半径得所有最短路（见附录10、1）
　 5、2、2相交切线模型
当两圆半径相同时,由于半径已知以及Ｋ（,Ｍ(，Ｌ（我们很容易求得
L点得坐标已知后用上述线圆模型即可求出弧长
当两圆半径不同时,根据半径比值可算出斜边比值，斜边端点已知，即可求出H坐标，再利用附录10、1求解可得。
5、2、3平行切线模型
当两圆半径相同时，其中已知O1(Ｏ2（,P（,半径已知，,
所以切线方程为
再利用matlａb运算出弧长(详见附录10、1)

当两圆半径不同时，两圆心斜率k可知，=a,切线斜率
再利用上述方程式即可求得Ｃ，切线方程与圆联立方程即可求得切点（见附录1０、2与1０、3）,再用线圆模型即可求出路径.
５、3基本模型求拐点(1题)
已知条件为O（Ｏ1（ＤO１=r
设Ｄ(xｙ），由于两直线垂直即有
D点在圆上,与圆得方程联立即可求出Ｄ点.此处先运用matlａb中ｅxｐａｎd函数将方程式化解成多项式形式，再用solve函数求出方程得根即Ｄ点坐标。（详见附录１0、2与10、3）
5、3时间模型得建立（2题)
　 　 　 　 根据线圆模型我们可以知道:若一个机器人穿过得圆弧所在圆得半径已知,则机器人行走得路程就就是可求得。由于机器人在转弯时得速度就是关于半径（r）得函数，再根据“时间(T)=路程（Ｓ）/速度（V）”,我们可以求出时间（T）关于半径(r)得函数关系式。已知直线行走得速度与转弯行走速度得关系式，,可以建立一个自变量为r得关于时间得函数,通过求导让函数值等于０,可以得出ｒ得解，从而确定最短时间。我们根据对前面路程得求解，可以判断机器人在转弯时所走得弧形路程相对于直线路程就是很小得，那么我们可以断定：当机器人以最短得时间走到目标点时，它所经过得路线与它以最短得路程所走得路线大致一样.
求函数表达式具体过程:
如图：已知O(x１,y1) B＝（x２,y2) 　Ｏ1=（x３，y3），点D，点E分别为圆得切点， 设圆得半径为r，求出O－-àB得时间。
求解过程：
L1＾2=（x２—x1）^2+（ｙ２-ｘ1）^2
L2＾2＝（x3—x2）^2+（y３-y2^２
L3^２=（x3－x1）^2+（y3-y1)^2
设O, O1,B为a， Ｄ,O1，O为ｂ，Ｅ，Ｏ1，Ｂ为c，
ｃos（a) =（Ｌ３^2- L2^２—　Ｌ1^2）/2＊L1*Ｌ2
ａ=arｃcos（Ｌ3^2— L2^2-　L１^2)/2＊L1＊Ｌ２
b=arccos（r/L1）
ｃ=arcos（r／L2)
弧长DE=r*（2*pi—a－b—c）
V=ｖ０/5*（1+e＾（1０—0、1^2）)
时间T1＝（L１^2－r＾2）^（1/２）/ｖ0
Ｔ2＝（Ｌ２^2-r^２）＾（1／2)／ｖ０
T３=弧长DE/V
Tｚｏng=T１+Ｔ2+T3
在求出时间关于半径得方程后,我们可数值解法求解最短时间。我们知道半径得大小影响了时间得长短,半径得长度就是大于１0得实数,我们可以先让自变量(半径）比较大范围得有序变化（因为自变量得范围不大)，求出对应得时间。再观察时间随半径变化得规律,得出最短时间时所对应得时间，就可以确定最短时间就在所得时间点得附件摆动.为了能更精确得求出最短时间，我们继续以比上次取值小得值在所求得点得附近做有序得加减。以此类推，经过多轮对时间得取值,就可以解出比较精确得解。
六、模型求解
６、1、1 O-— A得最短距离

如图：D1（70、5060,2１3、1４06）D2（7６、６06４，21９、４066)
弧OA得长等于两条切线（ＯD1，D2Ａ）与弧（Ｄ1,D2）得与
通过用matlab计算可知:
l Ｏ—-A得最短距离为471、0３7２
6、1、2　O—- Ｂ得最短距离
l 如图E1（５0、１３53，301、６396)E２(5２、1９8，306、25２)E3(142、19８,4４1、25２）E４（147、7０9,４44、７33）
Ｆ1（２２2、29，406、26４)F2（230,４70)F3（2３0,530）F4（２25、4967，538、35３8)
G1（144、50３3，59１、6462）G2(1４0、６９１6,５96、３45８)
同理如上,通过用matlab计算可知：
O 　 B得最短距离为8３８、0４66
6、1、3 O——C得最短距离
　 　 　　 　 　　 　　 如图
D1(７0、506０，213、14０６) D3(７５、736,219、04４)
L1（39５、798，339、055）L2(397、70９，339、７3６)
Ｋ1(56８、331,372、115)Ｋ2（600、01９，387、５8８）
J1（７２7、7178，7１0、2822）J2（730，600)Ｊ3(730，520)J４（７2７、８０２,６０6、25２)
同理如上，通过用maｔlａb计算可知:
O_C得最短距离为10８5、7531
如图
Ｇ3(2７0、58６2,６89、9828）G4(2７2,６８9、79８0)
H１(3６8、８93４,670、061４）H2（3７0，67０)H３(4３0,6７0）H４(4３５、5878，６７1、７０68)
I1(534、4１２2,738、2９３２）I2（５４0,74０）I3(6７０,740)Ｉ4（６7９、767３，７32、14４7)
F5（229、4472，533、2７89)
同理如上，通过用mａｔlab计算可知：
Ａ 　B得最短距离为454、３9８９
Ｂ C得最短距离为823、460９
　O Ａ B　 C　 O得最短距离为28３4、659１
６、2问题二得求解：
如图：
已知:坐标点O(0,０）,A(300 ,３０0)，Ｏ1（80，2１０)
根据上面模型，将三点得坐标分别代入,我们可以得到半径(r）关于时间(ｔ)得方程：
根据上面算出得方程，表示如图
注：左右下图得均纵轴为5倍得时间ｔ,为了便于比较不同时间下时间得大小.

当时间ｔ取值为1０,1１，１２,13,1４时,由图可以瞧到r＝12时，时间5*t为最小，故而判断精确值在12得附近.
表
图示中在半径ｒ=11、5时,时间最短
.
图示中ｒ=１1　、5０5时, 　　 时间最短

当半径r=１1、5045时，时间最短

　上图为给半径r规律性赋值得过程
解得：半径（r)＝１1、504时,
最短时间(ｔ)=98606004 .
七、模型推广
7、1 问题深入分析
　 在本题中有十二个障碍物，按照线圆结构画出从起点到达目标点得路径就是有限得，我们完全可以采用穷举法把这些路径列出来，然后比较大小取最小者即可,但就是我们可以设想如果这个区域内有n个障碍物，那么按照线圆结构从起点到达目标点得可能路径就有无数多条,这时我们如果再采用穷举法就是不现实得.所以我们必须寻求新得算法来解决这个问题。 　　　 　 　　 　 　 　 　
由上述分析我们有了这样一个想法：先求出所有得切线，包括出发点与目标点到所有圆弧得切线以及所有圆弧与圆弧之间得切线,然后把这且曲线瞧成就是图6、11中得,给这些定点赋一个等于切线长度得权值,如果某两条切线有一个公切圆弧，则代表这两条曲线得顶点就是一条直线得两个端点，边上得权值等于这两条切线之间得劣弧长度。然后在这张图中加一个源点与终点,那么在所有代表出发点与其它圆弧之间切线得顶点与源点连成一条边，权值均为０,同理在所有代表目标点到其它圆弧切线得顶点与终点连成一条边，权值均为0，这样题目就转化成了求源点到达终点之间得最短路径问题了,这里最短路径就就是指经过所有顶点与边得权值之与最小。我们可以采用Dijｋstrａ算法进行求解。
7、2 模型得进一步求解
　根据6、1得分析，在有若干个障碍物得区域中,我们把按照线圆结构画出从出发点到目标点得路径图依据6、1中得想法转换成了下面这张图,图中得Ａ与Ｇ点就就是添加得源点与终点,其它节点均就是出发点与目标点到圆弧得切线与圆弧与圆弧之间得切线转化而成,依据Dijkstｒａ算法求得最短路径。
八　模型评价
8、1模型优点 　　 　 　　　　 　 　
（１）在本题中,我们对该模型进行优化就是通过一些指标进行评判得,具有相对得客观性与一般性；
(2）在构造数学模型时我们给出了客观得理由与数据，避免了过分得主观判断；
（3）本文利用枚举与数学编程得方法,将定性问题定量化，运用多个方案对路径进行优化,在相对优化之中取得最优解,最后达到题目所要求得最优解； 　 （４)该模型可以解决日常生活中机器人得基本避障问题，使得机器人在工业，医学,建筑，军事等领域发挥应有得基本作用；　
８、2模型缺点
（１）由于分析时间限制与能力水平有限，加上计算量大且复杂,得到得不一定就是最佳结果。
（２）题中所涉及得各项比较、判断直到结果得得出都就是粗糙得，不适用于精度要求很高得问题.
（3）在障碍物较多时形状不规则时,模型需要进一步改进。
（４）不可避免得具有主观性.
　　 　 　 　 　 　 九 参考文献
［1] 冯俊， 数据结构, 北京: 清华大学出版社， 2007
［2] 邦迪,图论及其应用，西安：西安科学出版社,　1984
［3]　刘来福,数学模型与数学建模,北京：北京师范大学出版社， 201１
［5] 赵东方，数学模型与计算， 北京：科学出版社， 2007
十　附录
本题得计算量较大，我们用matlab软件来解决此问题
１0、1该程序用于解决已知起点，终点,相切圆圆心,可以求得起点到终点得最短路长
fｕncｔion　ｚoｎgchanｇ=zｏｎgchang（Ｋ,Ｍ,L，r)　
KＬ＝ｓqｒt((Ｋ(1）－Ｌ（1）)^2+（K（２）－L（2））^2）； 　
KＭ＝sqｒt((K(１)—M（１)）^2+（K（2）－M（2））＾2)；
LM＝sqrt（(Ｌ(1）—M（1)）^2＋（L（２）—M(2）)^2）;
aｌｐｈａ1=acoｓ（(KM^2+LM^2—KL＾2）/（2*KM*LM））;
ａlｐhａ２＝ａcos(r/KM）；
alphａ3=aｃoｓ(r／LM）;
alpｈａ４＝２＊ｐi-alpha１-alpha2—alpｈa3；
ＫS1=sｑrt（KM^２－r^2)；
S2L＝sqrt(LM^２-r^2）；
S1S2ｈｕ=r＊alｐha4;
reｓult=KS1+S1S2hu＋S２L
reｓｕlt=KS１
resulｔ＝S2L
ｒesulｔ=S1Ｓ２hu
10、2该程序用于解决多项式得展开问题,以便在solve函数中求切点
举例:求4个具体方程得多项式得展开式
fｕｎｃtioｎ neｗ=shijiａn(x1,x２，y1,y2)
sｙmｓ x1 x２　y1 y２
ｆ１=(0—x1）＊（80—ｘ1)+（0-y１）*（210－ｙ1)；
f２=(ｘ１-8０)＾2+(y1—2１0)^２-100；
f３=（320—x2）＊(３70－x2)+(6８0-y２）＊（680—y２）；
f4=(x2-370）^2+(y2-680）＾2—100；
f11=expand(ｆ１）
ｆ22=eｘpanｄ(f2）
f3３＝ｅxpand（f3)
ｆ44=expand(f4)
１０、3该程序用于解决多元多次方程得求解问题
举例：［x，y]=ｓolve（’-8０＊x1+x1＾２—210*y1+y1＾２'，’x1^2—160＊x１+504０0-420＊y1+y1^2＇）