机器人避障问题 摘 要：当今科学技术日益发达，高科技产品尤其是机器人在我们日常生活中运用的越来越广泛，它能够代替人类完成许许多多的工作，但如何能让机器人自动化的完成人类交给的任务成为设计机器人的关键。我们做此题就是为了更好的利用机器人为我们提供方便，提高生活质量，若机器人程序设计不当不仅不会给人类带来方便，还很有可能给我们的生活带来更多的麻烦。本题中提出了如何让机器人能够自动识别障碍物，保证机器人能够在合理区域行走，并设计出如何能让机器人自动判断最短路程于最短时间下行走路线的问题。所以解决好本题可以为我们的生活提供帮助。本文通过运用两点之间直线最短理论，优化问题，最短路问题，图论，以及运用matlab 软件编程及作图的方法，阐述了机器人避障问题的相对优化方案的解决办法，即“两点之间直线最好，转弯半径最小”的理论，通过计算中的比较与选择把四条最短路径都求出了相对最优解，论证了转弯速度不会随着r 的增加一直增大或减小，而是有一个最小极点的思想。从而求出了r ，以及最短的时间。
问题一，通过对最短路问题的分析，我们很容易分解成线圆结构来求解，然后把可能路径的最短路径采用穷举法列举出来，最终得出最短路径：
O →A 最短路径为：471.0372
O →B 最短路径为：838.0466
O →C 最短路径为：1085.7531
O→A→B→C→O 最短路径为：2834.6591
问题二，通过建立时间t 与r 的关系式，得出r 在11.504时，从O 到A 的
时间相对最短，最短时间为98.606004。
我们可以利用此篇论文解决生活中实际的问题，在计算时可以节省大量的时间，使机器人又准确又完善的完成我们给定的任务，从而进行拓展，给定区域内任何两个点，我们都可求出其最短路径和走完全程的最快时间。从而可以让机器人帮助我们给家里打扫卫生或设计自动吸尘器等，也可使机器人在最短的时间完成工作，提高效率，延长机器人的使用寿命。
关键字：最短路问题 优化问题 matlab
一 问题重述 随着现代科学技术日新月异的发展，机器人越来越多的出现在日常生活中, 它既可以通过运行预先编排的程序为人类服务，根据人工智能程序自动处理一些生活中问题，进而协助或者相应地取代人类的工作，可以说机器人的创新与改进正一步步影响着人类的发展。如图1所示，该图是一个800×800的平面场景图，在原点O(0，0) 点处有一个机器人，它只能在该平面范围内活动。机器人在活动中不能碰到障碍物及其向外延伸10个单位的区域，障碍物由12个不同形状的图形组成，障碍物的数学描述如下表：
在图1中，在障碍物外指定一点为机器人要到达的目标点，机器人的行走路
线由直线和与直线相切的圆弧组成，也可以由两条及以上圆弧组成。机器人不能折线转弯，必须经过与直线相切的圆弧转弯。每条圆弧的直径不小于10个单位。
机器人直线行走的最大速度为v 0=5个单位/秒。机器人转弯时，最大转弯速度为v =v (ρ) =v 0
1+e 10-0. 1ρ2，其中ρ是转弯半径。如果超过该速度，机器
人将发生侧翻，无法完成行走。
要解决机器人从区域中一点到达另一点的避障最短路径和最短时间路径，请建立数学模型，以达到最短路径和时间。对场景图中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 的最短时间路径。
注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。
图1
二 问题分析
2.1问题一
问题一中要求机器人从O （0,0）出发，按照上述规则求绕过障碍物到达目标点的最短路径，我们可以先设想机器人所走过的路径的各种情况。通过设想然后采用两点之间直线最短的原理寻找可能的最短路径（比如求O 和A 之间的最短路径，我们就可以连接O 和A ，发现OA 的对角线在OA 的下方，所以从OA 对角线的上方行走比下方距离短。在第一问求路径最短时尽量少走圆弧，所以在可能的情况下拐弯时最好走10为半径的圆弧）。之后采用穷举法列出O 到每个目标点的可能路径的最短路径，最短路径由圆弧和直线组成，求出圆弧和直线的长就能求得路径，通过建立优化模型可求出最短路径。进而联立切线和圆的方程组及运用matlab 软件求出各点坐标。
2.2问题二
问题二需要求O 到A 的最短时间，这让我们考虑的就不仅仅是路长的问题，还有了速度的问题。已知公式v 0=5和v =v (ρ) =v 0
1+e 10-0. 1ρ2得出直线比转弯
的速度快且转弯速度与圆弧半径有关。我们可通过建立路程和速度的关系方程
求得时间的最优解。
三 模型假设
1、 假设机器人能够抽象成点来处理。
2、 假设机器人能完整的走到终点，中途不会发生故障。
3、 假设机器人在离路障10个单位处不会发生故障，可以正常行走。
四 符号说明
五 模型建立
5.1证明点到直线距离最短理论在最短路问题中起重要作用
通过起点与终点的连线，判断哪边路径离这条连线距离较近，进而选择出最优路径。如果中间有较多路障的话也可采取分步判断的方法，判断由较近路障附近的点决定。
如图二，求O 到A 最短路径。正方形对角线为BC ，EE ’，DD ’分别为E,D 到OA 的距离，显然EE ’
5.2基本模型求路径（1题）
5.2.1线圆模型
已知O(为起点,B （为目标点,D （和E （分
，别为机器人经过拐点分别于隔离危险线拐角小圆弧的切点，圆心为O1（
圆的半径为r ，OB 的长度为a ，OO1的长度为b ，BO1的长度为c ，角度∠OO 1B ∠OO 11D ∠OO 11E ，∠EO 11D . 通过余弦定理可算出，弧长=圆心角*r，可求出O D E B 的长度。
由此解法在matlab 编程，可求出已知起点与终点及圆心和半径的所有最短路（见附录10.1）
5.2.2
相交切线模型
当两圆半径相同时，由于半径已知以及K(
x 1+x 2⎧x =⎪⎪32们很容易求得⎨ y +y 2⎪y =1
3⎪⎩2,M （,L （我L
点的坐标已知后用上述线圆模型即可求出弧长
当两圆半径不同时，根据半径比值可算出斜边比值，斜边端点已知，即可求出H 坐标，再利用附录10.1求解可得。
5.2.3
平行切线模型
当两圆半径相同时，其中已知O1(
K OO '=y 2-y 1
x 2-x 1， O2（,P
（, 半径已知，
所以切线方程为y =K OO '(x -x 1) +y 1+C
再利用matlab 运算出弧长（详见附录10.1）
C =当两圆半径不同时，两圆心斜率k 可知，∠02O 1K =a，切线斜率
=k ±tan a
1 k tan a
再利用上述方程式即可求得C ，切线方程与圆联立方程即可求得切点（见附录10.2和10.3），再用线圆模型即可求出路径。
5.3基本模型求拐点（1题）
已知条件为O(O1（DO1=r
设D(xy) ，由于两直线垂直即有(x 1-x )(x 2-x ) +(y 1-y )(y 2-y ) =0
D 点在圆上，与圆的方程联立即可求出D 点。此处先运用matlab 中expand 函数将方程式化解成多项式形式，再用solve 函数求出方程的根即D 点坐标。（详见附录10.2和10.3）
5.3时间模型的建立（2题）
根据线圆模型我们可以知道：若一个机器人穿过的圆弧所在圆的半径已知，则机器人行走的路程就是可求得。由于机器人在转弯时的速度是关于半径（r ）的函数，再根据“时间（T ）=路程（S ）/速度（V ）”，我
们可以求出时间（T ）关于半径（r ）的函数关系式。已知直线行走的速度和转弯行走速度的关系式，v 0=5v =v (ρ) =v 0
1+e 10-0. 1ρ2，可以建立一个自变量为
r 的关于时间的函数，通过求导让函数值等于0，可以得出r 的解，从而确定最短时间。我们根据对前面路程的求解，可以判断机器人在转弯时所走的弧形路程相对于直线路程是很小的，那么我们可以断定：当机器人以最短的时间走到目标
点时，它所经过的路线与它以最短的路程所走的路线大致一样。
求函数表达式具体过程：
如图：已知O （x1,y1） B=(x2,y2) O1=(x3,y3),点D ，点E 分别为圆的切点， 设圆的半径为r, 求出O-- B 的时间。
求解过程：
L1^2=(x2-x1)^2+(y2-x1)^2
L2^2=(x3-x2)^2+（y3-y2^2
L3^2=(x3-x1)^2+(y3-y1)^2
设∠O, O1,B为a, ∠D,O1,O 为b ，∠E,O1,B 为c ，
cos(a) =(L3^2- L2^2- L1^2)/2*L1*L2
a=arccos(L3^2- L2^2- L1^2)/2*L1*L2
b=arccos(r/L1)
c=arcos(r/L2)
弧长DE=r*(2*pi-a-b-c)
V=v0/5*(1+e^(10-0.1^2))
时间T1=(L1^2-r^2)^(1/2)/v0
T2=(L2^2-r^2)^(1/2)/v0
T3=弧长DE/V
Tzong=T1+T2+T3
在求出时间关于半径的方程后，我们可数值解法求解最短时间。我们知道半径的大小影响了时间的长短，半径的长度是大于10的实数，我们可以先让自变量（半径）比较大范围的有序变化（因为自变量的范围不大），求出对应的时间。再观察时间随半径变化的规律，得出最短时间时所对应的时间，就可以确定最短时间就在所得时间点的附件摆动。为了能更精确的求出最短时间，我们继续以比上次取值小的值在所求的点的附近做有序的加减。以此类推，经过多轮对时间的取值，就可以解出比较精确的解。
六、模型求解
6.1.1 O—— A的最短距离
如图：D 1(70.5060,213.1406)D2(76.6064,219.4066)
弧OA 的长等于两条切线（OD 1，D 2A ）与弧（D 1，D 2）的和
通过用matlab 计算可知：
● O ——A 的最短距离为471.0372 6.1.2 O—— B的最短距离
●
如图
E 1(50.1353,301.6396)E2(52.198,306.252)E3(142.198,441.252)E4(147.709,444.733)
F 1(222.29,406.264)F2(230,470)F3(230,530)F4(225.4967,538.3538） G 1(144.5033,591.6462)G2(140.6916,596.3458) 同理如上，通过用matlab 计算可知： 的最短距离为838.0466 ——C 的最短距离
如图
D 1(70.5060,213.1406) D3(75.736,219.044) L 1(395.798,339.055)L2(397.709,339.736) K 1(568.331,372.115)K2(600.019,387.588)
J 1(727.7178,710.2822)J2(730,600)J3(730,520)J4(727.802,606.252) 同理如上，通过用matlab 计算可知： 的最短距离为1085.7531
如图
G 3(270.5862,689.9828)G4(272,689.7980)
H 1(368.8934,670.0614)H2(370,670)H3(430,670)H4(435.5878,671.7068) I 1(534.4122,738.2932)I2(540,740)I3(670,740)I4(679.7673,732.1447) F 5(229.4472,533.2789)
同理如上，通过用matlab 计算可知： 的最短距离为454.3989 的最短距离为823.4609
2834.6591 6.2： 如图：
已知：坐标点O （0，0），A （300 ，300），O1（80，210）
根据上面模型，将三点的坐标分别代入，我们可以得到半径（r ）关于时间(t)的方程：
50500-r 267577-r 21r r (10-0. 1r 2)
++r (1+e )(2π-2. 1577-) -)) 555256. 3201224. 7221
根据上面算出的方程，表示如图
注：左右下图的均纵轴为5倍的时间t ，为了便于比较不同时间下时间的大小。
当时间t 取值为10,11,12,13,14时，由图可以看到r=12时，时间5*t为最小，故而判断精确值在12的附近。
图示中在半径r=11.5时，时间最短
。
图示中r=11 .505时， 时间最短
当半径r=11.5045时，时间最短
上图为给半径r 规律性赋值的过程
解得：半径（r ）=11.504时， 最短时间（t ）=98606004 。
七、模型推广
7.1 问题深入分析
在本题中有十二个障碍物，按照线圆结构画出从起点到达目标点的路径是有限的，我们完全可以采用穷举法把这些路径列出来，然后比较大小取最小者即可，但是我们可以设想如果这个区域内有n 个障碍物，那么按照线圆结构从起点到达目标点的可能路径就有无数多条，这时我们如果再采用穷举法是不现实的。所以我们必须寻求新的算法来解决这个问题。
由上述分析我们有了这样一个想法：先求出所有的切线，包括出发点和目标点到所有圆弧的切线以及所有圆弧与圆弧之间的切线，然后把这且曲线看成是图6.11中的，给这些定点赋一个等于切线长度的权值，如果某两条切线有一个公切圆弧，则代表这两条曲线的顶点是一条直线的两个端点，边上的权值等于这两条切线之间的劣弧长度。然后在这张图中加一个源点和终点，那么在所有代表出发点与其它圆弧之间切线的顶点与源点连成一条边，权值均为0，同理在所有代表目标点到其它圆弧切线的顶点与终点连成一条边，权值均为0，这样题目就转化成了求源点到达终点之间的最短路径问题了，这里最短路径就是指经过所有顶点与边的权值之和最小。我们可以采用Dijkstra 算法进行求解。 7.2 模型的进一步求解
根据6.1的分析，在有若干个障碍物的区域中，我们把按照线圆结构画出从出发点到目标点的路径图依据6.1中的想法转换成了下面这张图，图中的A 和G 点就是添加的源点和终点，其它节点均是出发点和目标点到圆弧的切线和圆弧与圆弧之间的切线转化而成，依据Dijkstra 算法求得最短路径。
八 模型评价
8.1模型优点
（1）在本题中，我们对该模型进行优化是通过一些指标进行评判的，具有相对的客观性和一般性； （2）在构造数学模型时我们给出了客观的理由和数据，避免了过分的主观判断； （3）本文利用枚举和数学编程的方法，将定性问题定量化，运用多个方案对路
径进行优化，在相对优化之中取得最优解，最后达到题目所要求的最优解； （4）该模型可以解决日常生活中机器人的基本避障问题，使得机器人在工业，医学，建筑，军事等领域发挥应有的基本作用； 8.2模型缺点
（1）由于分析时间限制和能力水平有限，加上计算量大且复杂，得到的不一定是最佳结果。
（2）题中所涉及的各项比较、判断直到结果的得出都是粗糙的，不适用于精度要求很高的问题。
（3）在障碍物较多时形状不规则时，模型需要进一步改进。 （4）不可避免的具有主观性。
九 参考文献
[1] 冯俊， 数据结构， 北京： 清华大学出版社， 2007 [2] 邦迪，图论及其应用，西安：西安科学出版社， 1984
[3] 刘来福，数学模型与数学建模，北京：北京师范大学出版社， 2011 [5] 赵东方，数学模型与计算， 北京：科学出版社， 2007
十 附录
本题的计算量较大，我们用matlab 软件来解决此问题
10.1该程序用于解决已知起点，终点，相切圆圆心，可以求得起点到终点的最短路长
function zongchang=zongchang(K,M,L,r) KL=sqrt((K(1)-L(1))^2+(K(2)-L(2))^2); KM=sqrt((K(1)-M(1))^2+(K(2)-M(2))^2); LM=sqrt((L(1)-M(1))^2+(L(2)-M(2))^2); alpha1=acos((KM^2+LM^2-KL^2)/(2*KM*LM)); alpha2=acos(r/KM); alpha3=acos(r/LM);
alpha4=2*pi-alpha1-alpha2-alpha3; KS1=sqrt(KM^2-r^2); S2L=sqrt(LM^2-r^2); S1S2hu=r*alpha4;
result=KS1+S1S2hu+S2L result=KS1 result=S2L result=S1S2hu
10.2该程序用于解决多项式的展开问题，以便在solve 函数中求切点 举例：求4个具体方程的多项式的展开式 function new=shijian(x1,x2,y1,y2) syms x1 x2 y1 y2
f1=(0-x1)*(80-x1)+(0-y1)*(210-y1); f2=(x1-80)^2+(y1-210)^2-100;
f3=(320-x2)*(370-x2)+(680-y2)*(680-y2); f4=(x2-370)^2+(y2-680)^2-100; f11=expand(f1) f22=expand(f2)
f33=expand(f3) f44=expand(f4)
10.3该程序用于解决多元多次方程的求解问题 举例：
[x,y]=solve('-80*x1+x1^2-210*y1+y1^2','x1^2-160*x1+50400-420*y1+y1^2')