2 问题分析
本文研究的是以（0,0）为起点，以800*800为平面场景的机器人避障行走问题，在给定的明确的障碍物的坐标位置的前提下，按照一定的行走路径绕过障碍物达到目的点的最短路径进行分析，且给定的路径行走方式为仅可以直线段与圆弧，对最短路径的行走给出方案，建立可行的避障定位最短路径和最短时间路径的数学模型。
问题1中，首先根据给定的10个单位的障碍距离，绘制出机器人允许行走的活动区域。接着，利用平面几何的知识以及导数原理，找出最短路径的制定方法，得出圆弧的半径越小，得到的路径也相应的最短的结论，据此证明所绘制的路径为最短路径。其次，将到不同目标点,O（0,0），A（300,300），B(100，700)，C(700，640),四个点的最短路径的情况绘制出，在拐角处绘制以方形或圆形的障碍物的顶点为10单位半径的圆弧（圆形的障碍物即以障碍物的圆心为圆心，障碍物的半径加10单位为半径的圆弧）。在此，制定求解路径长度及起始点的坐标，分4种情况进行分析。最终，对各条路径的直线段和圆弧进行加总求和，求得总长度，比较同一目标点下不同路径，最短的即为最短路径。依据此方法，建立最短路径的数学模型，并求解直线，圆弧起点，终点坐标，圆弧的圆心坐标。
问题2中，O?A的最短路径由距离和速度决定，而直线和转弯的速度不同。因此需建立转弯半径为变量的优化模型，此时，建立将转弯半径的取值范围为约束条件，由此，建立模型求解最短时间距离。
3 模型假设
1、假设障碍物的位置固定不变，且只包含长方形，正方形，平行四边形，三角形，圆形，题目中所给的数据准确无误。
2、假设机器人是一个不被考虑大小的点，即可作为质点，本身宽度不计。
3、假设机器人的性能足够好，在行走的时候不出现故障，且能准确的沿着圆弧转弯。 4、假设机器人可以无限接近边缘行走，忽略机器人转弯的时间。
4 符号说明
表 1 符号说明表
符号
描述
原点到直线A的长度 A到下一切点直线段的长度
圆弧半径 机器人过圆弧长度
i表示第i个障碍物，j表示由左下角逆时针旋转的第j个角
L1
L2
r
EF Tij
?2
5 模型的建立与求解
5.1问题一（求解最短路径） 5.1.1模型分析
1确定机器人可行区域
由于要求的目标点与障碍物的距离至少超过10个单位的距离，且行走路径为直线段与圆弧组成，无直线转弯，可绘制出机器人的活动区域，利用CAD制图软件，绘制图形。
2绘制路径的原则
题目要求在机器人允许的活动区域内，绘制出机器人到达不同目标点的线路图。规定机器人的行走路径由直线段和圆弧组成(转弯路径由与直线路径相切的一段圆弧组成，机器人不能折线转弯)。所以将模型简化为在已知两个固定点和圆弧圆心的情况下，确定圆弧半径r为何值时，才能使机器人行走布局路径最短。局部简化路线图如图1：
图1
1）圆弧半径与路径长度关系
假设图中固定点的坐标分别为A(a1,b1)、B(a2,b2)，圆弧圆心为O(m,n)，圆弧半径为r。线AC和线BD分别相切于圆O于点C、D，各圆心角分别为????AOC，????BOD，????BOD，????COD，线段AO、BO、AB、的长度分别为a,b,c。根据勾股定理可以分别计算a,b,c的长度为：
?a?(m?a)2?(n?b)211??22?b?(m?a2)?(n?b2) （1） ?c?(a1?a2)2?(b1?b2)2??且在?AOC、?BOD、?AOB中??、??、??满足如下三角函数关系：
?r???arccos?a?r? ????arccos （2）
b?222????arccosa?b?c?2ab?（由于a、b、c三条线段均可由已知条件计算出，所以??、??、??也为已知角）
再根据机器人所走路线结构和公式（2）计算出的角度，可建立路径长度关于圆弧
3
半径r的函数关系：
L(r)?a2?r2?b2?r2??r?a2?r2?b2?r2?(2???????)r（3）
rra2?b2?c2?a?r?b?r?(2?-arccos-arccos-arccos)rab2ab22222）求解最短路径下的r
根据路径与圆弧半径的关系式（3），对未知量r求导，求出最短路径下的r。求导结果为：
dLrra2?b2?c2?2??arccos-arccos-arccos （4） drab2ab??、??均在直角三角形中，所以??????90，则求导结果可以近似看为：
dL??????0 （????） （5） dr（路程函数对于r求导的结果大于0，所以函数关系为单调递增函数）
得出绘制路径原则
制定机器人行走路线时，圆弧半径应为要求中的最小值10个单位。 理由：根据求导结果（4），可知当圆弧半径r逐渐增大时，机器人行走弧线结构的路程最大，r逐渐减小时，路程逐渐减小。题目要求离障碍物最近距离为10个单位，所以当圆弧半径为10时，路程最短。
所走圆弧的圆心为障碍物定点。
理由：两点之间直线最短，所以尽量要直线靠近目标点，当无法直线行进时要尽量保证躲避障碍物所走弧线最短，即以障碍物顶点为圆心下最小要求距离为半径的圆弧最短，才不会产生绕远现象（障碍物2本身为圆，所以圆弧圆心为障碍物2的圆心，半径为障碍物2的半径）。
3求解路径长度以及点坐标（路径起始点和终点坐标）的方法 在进行绘制路径的过程中，经归纳可以将路径长度的计算分为三钟类型，第一，（点到弧）已知点到圆弧，第二，（弧到弧）公切线与两圆心的连线平行；公切线与两圆心的连心相交。三，弧长的求解
（1）已知点到圆弧
图2
如图2中固定点的坐标分别为A(a1,b1)、B(a2,b2)，圆弧圆心为O(m,n)，圆弧半径为r（为最小半径r?10），线AC和线BD分别相切于圆O于点C、D，切点C、D坐标未知，设坐标分别为(x1,y1)、(x2,y2)。
4
根据已知坐标和数据可以求出AC、BD线段的长度为：
?AO?(m?a)2?(n?b)211??求AC长度?CO?r （6）
?AC?AO2?CO2???BO?(m?a)2?(n?b)222??求BD长度?CO?r （7）
?BD?BO2?DO2??在求出线段AC、BD后，可以根据方程求解确切的切点C、D坐标：
22??AC?(x1?a1)?(y1?b1)求切点C坐标? （8）
22??r?(x1?m)?(y1?n)22??BD?(x2?a2)?(y2?b2)求切点D坐标? （9）
22??r?(x2?m)?(y2?n)由于方程组（8）、（9）均为二元二次方程组，可以用MATLAB软件进行求解。
（2）切点连线与圆心平行
图3
'O(m,n)O(m2,n2)，两圆弧的半径均为最短半径r?10。未12、如图3，已知圆心
（x2,y2）（x1,y2）知点为切点A、B，设其坐标分别为、。
''图3中四边形ABOO为矩形，所以切线段AB的长度等于线段OO的长度：
AB?OO'?(m2?m1)2?(n2?n1)2
在结合AB的长度，和三角形勾股定理建立方程，求出切点坐标
22??r?(x1?m1)?(y1?n1)?2222(x?m)?(y?n)?AB?r?1212求切点A坐标? （10）
22??r?(x2?m2)?(y2?n2)?2222(x?m)?(y?n)?AB?r?2121?求切点B坐标 （11）
（3）切点连线与圆心连线相交
5
图4
'O(m,n)O12如图4，已知圆心、(m2,n2)，两圆弧的半径均为最短半径r?10。未
（x2,y2）（x1,y2）知点为切点C、D，设其坐标分别为、。切点连线与圆心连线的交点为E。 '根据三角形全等规律，可以证明?OEC??OED，此时E为线段CD的中点，切线CD的长度计算公式为：
22
根据所求CD长度和已知坐标点，列出关于切点的函数方程组并求解出（计算机求解）切点具体坐标。函数方程组具体如下：
?r?(x?m)2?(y?n)21111??m1?m2n1?n2CD22(?x)?(?y)??11222 （12） ?C求切点坐标
?r?(x?m)2?(y?n)22222??m1?m2n1?n2CD22(?x)?(?y)??22222 （13） ?D求切点坐标
CD?2(m1?m2?m1)2?(n1?n2?n1)2?r2（4）求弧长
图5
D(a2,b2)，C(a1,b1)、在以上3种情况中我们均可求出切点坐标，圆弧圆心为O(m,n)，
圆弧半径为r（为最小半径r?10）。
根据余弦定理可得
OC2?OD2?CD2cos?COD? （14）
2?OC?ODOC2?OD2?CD2???COD?arccos （15）
2?OC?OD并且有已知条件可得：
6