■b
在Rt^AOC中:
a,=arccos/-~y）
2bc
ay=arccos一
c
所以:
L=>jb2-r+ylc2-r+r0
（2）对于下面两种悄况不能直接采用线岡结构来解决，需要做简单的变换。
悄况_：
对于同心连线与切点连线交叉的悄况。
线Bl结构4・3
假设两圆心坐标分别为和N（x29y2）,半径均为「，P点坐标为（可,旳），可以求得:
西+“2
儿=
因此可以利用
（1）中的方法，先求A到P,再求P到B,这样分两段就可以求解。
同理血果有更名的转弯，同样可以按照此种方法分解。
悄况二:
对于圆心连线与切点连线平行的悄况。
DE
y=%d）+x
M/V直线方程为:
因为公UJSDE与MN平行，所以DEM直线方程可以表示为:
『=%（兀_召）+”+3
其中:
把公切线的方程于圆的方程联立,可求和E的坐标。
用D和E任直一自作为分劃点都可以将上图分创成两个4-2所示的线冏结枸，这样就可以对其进行求解。
同3,多个这样的转弯时，用同样的方法可以进行分创。
4.2模璽准备二
假按:
如果一个圆坏可以绕着坏上一个定自转动，朋么过圜坏外两定点连接一根绳子，并以该圆坏为支撑拉紧绳子，达到平衡状态H,|«心与该顶点以及两条幼线的延长线的交点共线。
证明:
血图4-5所示，E点就是惻坏上的一个顷点，ACDB与圆坏相切的胳线，N就是切线AC和BD的延长线的交点，込明M、E、N三点共线。
用力学的知识afiil明，RiHfi力相等，设为戸，它们的合力设为丘，定点对岡坏的作用力设为E。
由几何学的知识可知，&与顾共线，根据力的平術条件可得：
_—F°T
即顾与石可共线。
妹上所述M、E和N三点一定共线。
准备：
根据假设的定理可求出机器人UA绕过障碍物经UP到达目标自B的最短路径（血图4-6）,釆用以下方法：
用一根知子使一个岡坏定在P点，使这个圆坏能册绕P点转动。
然后连接A和B的绳子并以这些转弯处的圆弧为支«（S里转弯处Bill的半径均按照最小转弯半径来it算），拉紧绳子，册么绳子的长度就是A到B的最短距离。
可以把路径图抽象为以卞的几何图形2H亍求解:
0V''./M
P
ED
图4-6
如图,A（西,廿）是起点，B（x2,y2）是终点，M（羽,旳）和N（刃,）打）是两彳、固定的圆，0是一个可以绕P（P,q）点转动的圆环,三个圆的半径均为r,C、D、E、F、G、H均为切点。
a、b、c、e,f分别是AM、MO、AO、AN、0N的长度。
A、B、M、N均是已知点,0是未知点。
那么最短路径就可以表示为：
L=\AC\+CD+\DE\+EF+\FG\+GH+\HB\
因为o点的坐标未知，不能用线冏结沟对其亍求解。
故得先求出o点的坐标。
设O坐标为（m,n）,ZAMC、ZAMO、ZAOM、ZAON、ANOF分别为af（Z=1、2、3、4、5）,ZCMD.ZEOF、ZEOM分别为0、y、0Q
得到如下关系:
"=J（斗73）2+（开_卩3）'
b=yl（xy-m）2+（y3-n）2）2e=yl（xl-x4）2+（yi-y4Yf=yl（x4-m）2+（y4-n）2
在R3MC中：
r
ax=arccos—
a
在AAMO中：
a2+b2-c2
4=arccos
22ab
Zr+L—/
a.=arccos
32bc
在^AON中：
c2+f2-e2
a.=arccos
2cf
在Rt^QOF中:
2r
a.=arccos——
f
0=¥_4_冬
3兀
/=—-^-^4-^5
Q81为PO—定会在ZEOF的用平分线上，所以满足：
e=L
2
了果用向量的形式来求,易知莎的一个方向向量:
心（】,g）x2-n
而OE^MO垂直，故其一个方向向量：
/；=（!
-AZ1）
y2-m
ffij:
OP=（p-tn.q-n）
所以:
a/八OM
^=arccos.
l/jOMI
■
综合以上式子可以求借O的坐标，从而可以得出路径的长为:
L=yja2-r2+pr+b+yr+2^）2-r2+/0
l°=GH+HB
5模型的建立与求解
5.1»S-W建立与求解
根据题恿，机器人行走线路与障碍物间的最ifi距离为10f单位，由此可以画岀机器人行走的可Item与危险EM,则下图5-1示，阴影部分代表可行区域，白色部分代表危险EMo
图5-1机器人行走的可行区域与危险区域
假设机器人从起点0到目标点由题可知路径由冏恥和线股组成，设有m条线股，nftlll®。
那么目标函数可以表示为：
nin
min厶=2X+*
/=1J=1
X?
>10
s.t=<
k>10
用此模型就可以对起点到目标点之间的路径进行优化求解。
（1）#0图5-2解决的是0到目标点A的最姬路gro，图中给出了可能的两条路径的最短胳径（图中的蓝色所示），可以分别计算岀两条可能路径的最短路径的长度，滋后进行比较，取最小者就是0到目标点A的最优路径。
g
0
图5-2到ftA«可能最短路径
利用MATLAB编程（程序见附录A）对模型进行求解，结果如下:
10U胳线1到达目标点A,解借最姬路径为498.97个单位。
20从路线2到达目标虑A,解借最矯路径为471.04个单位。
综合①2嘶述，0到目标点A的最姬路径为471.04个单位。
（2）ffl图5-3解决的是0到目标点B的最短路径问!
图中给岀了可能的兀条路径的最短胳径（图中的线条所示），可以分别廿算岀穴条可能路径的最短路径的长度，然后进行比较，取最小者就是0到目标点B的最优路径。
Y
利用MATLAB编程（程序见附录A）对模型进行求解，结果如下：
10从路线1到达目标点B,在拐贞a处分为两条胳线，即图巾的黄色路线与红色路线。
al.USS线1走红色路线：
这条路径是由5条直线和4段岡恥组成，直接用简单的线同箱构无法解岀。
于是做血下变换：
首先，找岀两圆％的幼线段与两囿心连线的交点M；其次，用线凰给枸4—2的解法计算,分别求0到M和M到下一个交点,以此类推直到目标点B,分四部分求解;最后把这El部分的和相加，便可求岀0到B的最姬路径。
求得结果为945.96t单位。
bl.UJS线1走黄色路线：
同理这条路径是由4条貞线和3段圆恥组成，同样可以采取肋中的变换,分三部分求解，求得结果为1058.4个单位。
妹上：
01USS1到达目标自B走红色路线路径最短，最短路径为945.96个单位。
20从路线2到达目标自B,在拐自b处分为两条胳线，即图中的黄色路线与红色路线。
a2.Uffi线2走红色路线：
同理这条路径是由5条直线和4段圆弘组成，同样可以采取肋中的变换,分四部分求解,求得结果为878.05个单位。
b2.U路线2走黄色路线：
同理这条路径是由4条貞线组成，同样可
以果取a1中的变换,分三部分求解，求得结果为990.17个单位。
妹上：
0从路线2到达目标自B走红色路线路径最短，最短路径为878.05个单位。
30从路线3到达目标自B,在拐点c处分为两条胳线，即图中的黄色胳线与红色路线。
a3.UJS线3走红色路线：
同理逆条路径是由6条直线和5H®®组成，同样可以采取肋中的变换,分五部分求解，求得结果为853.71个单位。
b3.U路线3走黄色路线：
同理这条路径是由5条直线和4段圆弘组成，同样可以采取a1中的变换,分皿部分求解，求得结果为971.23个单位。
综上：
0从路线3到这目标点B走红色路线路径最短，最婕路径为853.71个单位。
综合①②③所述，0到目标虑B的最短路径为853.71个单位。
（3）M图5-4解决的是0到目标点C的最短路径冋題，图中给岀了可能的三条路径的最短路径（图中的蓝色所示），可以分别廿算岀三条可能路径的最短胳轻的长度，
图5-4到达C的可能最短路径
利用MATLAB编程（程序见附录A）对模型进行求解，结果如下:
1OU胳线1到这目标点C,同理这条路径是由6条fiSfll501^1®组成，同样可以呆取刖中的变换,分五部分求解,求借结果为1088.20个单位。
20从胳线2到这目标点C,同理逆条路径是由6条貞线fl!
5Hia®组成，同样«IJU®a1中的变换，分五部分求解，求得结果为1102.60f单位。
30从胳线3到这目标自C,同理这条路径是由7条貞线和6Kl§|®组成，同样可tt«®a1中的变换，分兀部分求解，求骨结果为1253.40f单位。
40UJSS4到达目标自C,同理这条路径是由8条育线和7段圜飯组成，同样可以呆取砧中的变换,分七部分求解,求得结果为1239.80个单位。
综合①2）③^所述，0到目标点C的最姬路径为108&20个单位。
⑷如图5-5解决的是OtAtBtCtO的最短路径问题，可利用准备二的理论对其进行廿算，棉出最姬路径。
蓝色线为OtAtBtCtO的最短JS6,这条路径由17条貞线和16Kia®组成，在个目标处用准备二进行廿算，同样果取31中的变换，分十五部分求解，求得给果为2730.01个单位。
5.2模型二的建立与求解
机器人最大转弯速度为v=v（p）=—,其中°是转弯半径。
所以，在一定X围内,
1+e
转弯半径越大，最大转弯速度也就極大，行走时间减小。
根据以上分折，做岀以下假设：
SS：
JDJ走弧线的中自C为公共切点，将最小圆的圆心与公共切点C连接并延长,所得直线即为以相同半径不同冏心所有冏的最优路径（为所走弧长路径），其中所有最优圆的圆心，即为在不与障碍物发生碰撞的悄况下岡心的变化x围。
证明:
以任意虑m、n为圆心，其中点m、”不在公共切虑c与最小圓的圆心（80,210）连线的直线上，另外在这条直线上找一"然后分别以点〃?
、〃、z为圜心，作出相同半径的闊并部内切于公共切点c,如图所示：
分别求得以点加、〃、z为圆心，相同半径的圆的不同路径距离分别为489.61个单位、483.47个单fi.472个单位，通过对比可8l,当半径相同时，圆心在公共切点c与最小岡的冏心（80,210）连线的直线上所走的路径最短。
Q因为公共切点c正好为所走版线的中点，所以此直线与正方形的対角线重合，因此可得直线为y=—x+290。
同时也騎込假设是正确的。
通社上述证明可JU,III心在貞线y=-x+290上变化为最优。
找出圓心在直缆y=-x+290上变化时，没有与障碍物同发生碰撞的最大圆的凰心位置与最小圆的圆心位置，设最大BI的H心坐标为心刃，如下图所示：
当线段力=必时，以交点0为冏心，心为半径师圆，此时的圓为没有与障碍物间发生碰撞的最大冏，Q因为点c为直线y=一兀+290与以点（80,210）为圓心半径为10个单
位圆的交虑,由此可得;
y=-x+290（x-80）2+（y-210）2=102
解得点c坐标为（80-572,210+5^）
根据两点之间的距离公武〃=/兀-*+（儿+肘可知：
y=一兀+290
^（80-5^2-x）2+（210+5VI-y）2=^（x-x）2+（290-y）2
解得最大H的圆心坐标为0（249,41）
同理,可知最小U的圓心坐标为（80,210）o
由上述可知，同心是在直线y=-x+290（80/•=>/（x-80）2+（y-210）2+10
根据題恿，机器人转弯时，最大转弯速度为V=V（P）=—,其中Q是转弯半
1Ie
径。
所以，当％—定时，机器人转弯的半gpi大，最大转弯速度也就越大。
乂因为机器人直线行走的最大速度为v0=5个单位/秒，所以当p趋于无穷大时严Wo（其中因为不能碰撞障碍物所以Q不能无限范于无穷大），最大转弯速®v=v（p）=—
1+e•卩
也就范于v=v（p）=v0=5个单位/秒，所以在转弯时，眠的半gl§t,转弯速度加快。
如图5-9解决的是0到目标点A的最短时同路径问SSoia心dU小園到大同内变化,图巾给岀了OtA的所有可能时间路线。
计算岀所有路线的时间，比较其大小，找出最短时同路径。
图5-9
因为圆心是一个动点，所以可以得到很多条路径。
结合准备以中的定理，利用MA7UB编程（程序见附录B）对模型进行求解，找岀时间最姬的路径，结果如下：
0-A的最姬时间路径为471.12f单位，最短时间为94.229杪。
5.3模型结果
由題恵可知，路径由圆恥和线段组成，设有m条线段，n条凰恥。
机器人貞线行走的最大速度为v0=5f单位/枚。
机器人转弯时，最大｛专弯速度为y==—o
|+glU-U.l^
经过推算可th专弯半径Q=io,假设机器人在貞线上一貞以5f单位/枚行走，根摇公式可以借到最大转弯速度为v=2.5个单创秒。
5.3.1模型一的结果
（1）0-A的最類路径为471.04个单位，根据上述公式得到总时同为96.022秒。
最姬路径中每段宜线段或圆*的起点和终点坐标、冏版的圓心坐标以尺机器人行走的总更离和总时间如下表：
表5-100-A9条线段与冏醫的坐标及总路桿与息时间
O-ASJ®路为471.04个单•总时间为96.022杪
第％条线段
d\
d2
起始坐标
X
0
76.61
y
0
219.41
终点坐标
X
70.5
300
y
213.12
300
第厶条圆礼
h
風心坐标
（80,210）
（2）0-B的最矯路径为853.71个单位，根据上述公式得到总时间为179.084秒。
最短路径中毎段直线段或圓％的起点和终点坐标、圓11的圓心坐标以及机器人斤走的总距离和总时间如下表：
表5-110-B毎条找段与岡醫的坐标及总路桿与息时间
O-BggSg»853.71个单位,总时间为179.084杪
第/条裁段
山
d2
爲
£
4
〃6
駅始坐标
X
0
52
147.96,
230
225.5,
140.69
y
0
305.55
444.79
470
538.35
596.35
冥点坐标
X
50.14
141.68
222.04
230
144.5
100
y
301.06
440.55
460.21
530
591.65
700
第C条同取
h
仁
厶
h
&
岡心坐标
X
60
150
220
220
150
'、
300
435
470
530
600
（3）OtC的最矯
升级会员 