1、机器人避障问题【摘要】本文主要是对机器人在一个平面区域内的通过不同障碍物到指定目标点进行研究，首先通过机器人与障碍物的最小安全距离对不同障碍物的禁区进行了划分见图1，把障碍物划分为有顶点和无顶点两大类。然后证明了机器人在障碍物顶点处转弯路径最优，转弯半径最小路径最优，转弯圆心在障碍物顶点处（圆行障碍物在圆心）路径最优。问题一对于起点和目标点的的路线先用拉绳子的方法确定了可能的最短路线，然后用穷举法确定最佳路径。机器人的行进又分单目标点和多目标点两种情况。针对单目标点问题，先对只进行一次转弯的过程建立了基本线圆组合结构的解法即模型一。然后对多次转弯问题中的直线路径与圆弧路径的不同的位置关系推导出
2、了计算模型即模型二。对O-A是基本的线圆组合，直接用模型一求解得到0-A的最短路径长为471.0372个单位，所用时间为96.0178秒具体情况见文中表1。对O-B和O-C都是先用模型二对路线进行基本分割，然后用模型一进行求解得到O-B最短路径长为853.7127个单位，所用总时间为179.0851秒，具体见表2。得到O-C最短路径长为1087.6个单位，所用时间为221.9秒，具体见表3。针对多目标点问题，由于机器人不能直线转向，所以在经过目标点时，应该提前转向，且中间目标点应该在转弯弧上。因此先建立优化模型（模型三）对进行中间目标点处转弯圆弧圆心搜索求解。求出中间目标点转弯圆心后，用把中间
3、目标点的圆心看做“障碍物”的办法把问题转化为单目标点问题。然后利用模型二和模型一进行求解，解得O-A-B-C-O的最短路径长为2812.52个单位，所用时间为585.6712秒，具体见附表1。对于问题二，在问题一求出的最短路的基础上，根据转弯半径和速度的关系，在问题一求出的最短路径的模型的基础上，进行路线优化，建立以最短时间为目标的非线性规划模型，求解得最短时间为94.22825秒，转弯半径为12.9886个单位，转弯圆心坐标为（82.1414，207.1387），具体结果见表5。关键词：基本线圆组合 拉绳子法 穷举法 非线性规划 中间目标点转弯圆心1问题重述附图1是一个800800的平面场景
4、图，在原点O(0, 0)点处有一个机器人，它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述如下表：编号障碍物名称左下顶点坐标其它特性描述1正方形(300, 400)边长2002圆形圆心坐标(550, 450)，半径703平行四边形(360, 240)底边长140，左上顶点坐标(400, 330)4三角形(280, 100)上顶点坐标(345, 210)，右下顶点坐标(410, 100)5正方形(80, 60)边长1506三角形(60, 300)上顶点坐标(150, 435)，右下顶点坐标(235, 300)7长方形(0, 470)长22
5、0，宽608平行四边形(150, 600)底边长90，左上顶点坐标(180, 680)9长方形(370, 680)长60，宽12010正方形(540, 600)边长13011正方形(640, 520)边长8012长方形(500, 140)长300，宽60在图1的平面场景中，障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走
6、线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。机器人直线行走的最大速度为个单位/秒。机器人转弯时，最大转弯速度为，其中是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中4个点O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具体计算：(1) 机器人从O(0, 0)出发，OA、OB、OC和OABCO的最短路径。(2) 机器人从O (0, 0)出发，到达A的最短时间路径。注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的
7、圆心坐标以及机器人行走的总距离和总时间。2问题分析 本问题主要是对机器人在一个平面区域内的通过不同障碍物到指定目标点进行研究，首先通过观察发现障碍物不同，因此我们先要对机器人通过不同的障碍物的情况进行讨论。在行进过程中转弯位置，转弯的半径，转弯圆心的不同都会影响路径的优劣。因此我们要先确定最佳转弯位置、半径和转弯圆心。对于问题一，分单目标点和多目标点两种情况。针对单目标点问题，从已知点到指定点有多条路径可以选择，可以先用拉绳子的办法确定可能的最短路线，然后用穷举法确定最短路径。由于机器人不能折线转弯，转弯路径由与直线路径相切的圆弧组成，因此可以把路径看成由多个基本线圆组合而成，然后在对基本线圆
8、结构建立求解模型。针对多目标点问题，不能简单的处理为求解每个两点之间的最短路径之和，因为机器人不能直线转向，所以在经过目标点时，应该考虑提前转向，且中间目标点应该在转弯弧上。因此对于中间目标点处转弯圆弧圆心的确定可以建立优化模型进行搜索求解。求出中间目标点转弯圆心后可以把中间目标点的圆心看做“障碍物”进行研究，这样问题就转化为了单目标点问题。对于问题二，可以根据转弯半径和速度的关系，在问题一求出的最短路径的模型的基础上，进行路线优化，即建立以最短时间为目标的非线性规划模型，进行求解最短时间。3模型假设为了简化计算，给出如下模型合理性的假设：【1】假设所有障碍物是固定不动的；【2】机器人性能足够
9、好，能准确地沿圆弧转弯；【3】假设机器人在初始时的速度为5个单位每秒；【4】假设机器人在直线切入弧线时的速度是瞬间变化完成的；【5】机器人行走过程中不会意外停止；【6】忽略影响机器人行走非最小转弯半径以及最小安全距离因素。 4符号说明为了简化对问题的分析和对数字的处理，做出如下符号规定：第条直线路径长度第条弧线路径长度最短路径总长度最短路径所用时间机器人直线行进速度机器人转弯速度5模型的建立与求解5.1最短路径模型（问题一）从已知点到指定点有多条路径可以选择，可以先用拉绳子的办法确定可能的最短路线，然后用穷举法确定最短路径。在行进过程中转弯位置，转弯的半径，转弯圆心的不同都会影响路径的优劣。因
10、此我们要先确定最佳转弯位置、半径和转弯圆心。本问题中对于路径的求解分为单目标路径和多目标路径两种，因此在本问题中我们分开讨论。5.1.1单目标点模型（只有起点和终点） 由于机器人不能折线转弯，转弯路径由与直线路径相切的圆弧组成，因此对于本问题可以把路径看成由多个基本线圆组合而成。5.1.1.1相关推论及证明 把机器人的行进路线看成一根有弹性的绳子，根据实际情况我们推论：禁区顶点处变向路径最小，转弯半径最小路径最短，转弯弧圆心在顶点路径最短。【1】禁区划分 由于机器人行进过程中与障碍物有最小距离的限制，因此我们先画出包络障碍物的禁区，对于有圆形障碍物来说，禁区还是一个圆，对于有顶点的障碍物来说禁
11、区拐角处为一个圆弧，具体如图1：图1 禁区示意图【2】障碍物有顶点（1）禁区顶点变向路径最小如下图2所示，机器人从指定的A点到C点，需要进行变向，从图形可以看出来，在禁区边缘变向总路径会最小，下面我们进行证明：图2 禁区顶点处变向图假设D点为禁区顶点，先不考虑转弯半径等因素，其中B为禁区外任意一点，AD变延长线交BC于E点。由三角形的任意两边之和大于第三边可以得到：两式相加得到：化简得到：即，由A点到B点，选择在顶点D处转向，总路径最短。推论得证。（2）转弯半径最小路径最短机器人从A点到B点需要绕过禁区，在禁区顶点附近（前面已证）转弯。选择的转弯半径越小，得到的路径越短。下面从物理学的角度进行
12、证明：如下图3所示，将A到B的路径看做一条可伸缩的绳子。假设其两点相连时，绳子自然伸长。如线段AB。由于机器人要绕过禁区，因此拉长绳子绕过禁区，又因为机器人有最小转弯半径为10，禁区直径也为10，因此可以把绳子直接绕过禁区边缘。由于绳子的弹性势能与伸长量的关系为：因此绳子伸长量最小时，路径最短。图3 机器人过障碍转弯半径根据最小势能原可知，当弹性体平衡时，系统势能最小。即弹性体在自由条件下，有由高势能向低势能转化的趋势。现在将圆环看成也有弹性，在如图所示的条件下为初始状态。圆环受力如图所示，此时圆环有缩小的趋势，随着圆环的缩小系统趋于平衡，弹性绳有最小势能。由能量守恒也可以说明，绳子的弹性势能
13、转化为弹性圆环的弹性势能，于是弹性绳的弹性势能减小。因此，随着圆环的半径的减小，绳子的势能减小，即最短路径变短。所以最小转弯半径最小路径最短得证。（3）转弯弧圆心在顶点路径最短 机器人在禁区顶点附近转弯时，转弯弧的圆心在顶点上，路径最短。下面进行证明： 如下图4所示，圆O和圆O均过最远点D它们的半径分别为R和R。其中圆O的圆心在垂线上。分别为过A、B点向圆O和O所引切线段和所夹圆弧长度。则需证明：因为两圆圆心不同在过点 D 所引的垂线上，且两圆交于点 D，因此它们只能有两种关系相交或相切。若两圆相切，由几何定理知切点、圆心 O、圆心 O三点共线。因点 D 和圆心O均在过D所作直线AB的垂线上，
14、圆心O在垂线外，故两圆不会相切，只能相交。要过点D则必有圆O上点到直线AB的最大距离大于圆 O上点到直线AB的最大距离。运用上文已证得的结论可得到：因此推论得证。图4 机器人过障碍转弯圆心位置（4）结论分析 结合（1）（2）（3）证明得到结论：机器人过有顶点的障碍物时，沿以顶点为圆心，最小转弯半径为半径的圆弧转弯路径最短，在本题中机器人的最小转弯半径和机器人与障碍物的最小安全距离相等。因此对于本题来说，机器人沿禁区边缘转弯路径最短。【3】障碍物为圆的情况在前面我们已经证明了障碍物有顶点的情况下，机器人过禁区时沿禁区边缘圆弧转弯路径最小。下面就机器人通过圆形障碍物的情况是否符合以上结论进行讨论。
15、如图5，分别是机器人通过圆形禁区的3种情况，其中a图为机器人人沿禁区边缘进行转弯的。b图为机器人沿以圆形障碍物边上一点为圆形，最小转弯半径为转弯半径的弧转弯图，c图为机器人沿一个刚好绕过禁区的圆弧转弯的情况。图5 机器人通过圆形障碍物由以上用弹性绳的方法进行证明发现，b图转弯路径最小，但是经过了禁区，因此不可行，另外两种方案a图路径明显要比c图小。因此机器人过禁区时沿禁区边缘圆弧转弯路径最小得结论同样适用于障碍物位圆的情况。转弯半径为： （其中为障碍物半径，为机器人距离障碍物的最小安全距离）5.1.1.2模型的建立经过以上证明得到，起点到目标点中间不管有多少障碍物，最短路径都是由若干个相切的直
16、线和圆弧构成的，前面已经证明机器人经过所有障碍物时，禁区边缘转弯路径最短，因此转弯圆弧半径为危险区域半径。所以在下面模型中经过障碍物转弯时，都以障碍物顶点为转弯弧圆心，最小转弯半径为转弯半径。【1】途中转弯一次的模型（模型一）如图6所示，已知机器人要从起点A（）点出发绕过障碍物到终点B。途中从以障碍物顶点D（）为圆心，为半径的弧上转弯，切点为C和E。需要求C点和E点坐标，以及的长度。图6 机器人过障碍物转弯图根据两点距离公式：由于C点和E点是切点，所以 根据勾股定理：切点坐标的确定假设C点坐标为（），E点坐标为（）。那么根据两点距离公式还有：综上所述，对于E点坐标就有：对于C点坐标：解以上方程
17、组即可得到两个切点C和E的坐标。转弯弧长的确定在中，根据余弦定理：在中：在中：对于就有：因此弧的长度就为：总路径和总时间的确定机器人途中转弯一次路径长度就为所用时间就为【2】途中转弯多次的模型（模型二）机器人在从起点到终点的过程中，如果障碍物多的话，机器人需要通过多次转弯才能到达目标点，多次转弯可以分解成由多个两次转弯和一次转弯组成，而在两次转弯的过程中，两个转弯弧度的公切线分为内公切线和外公切线两种。沿内公切线前进的情况 如图7所示，机器人从起始点A到目标点B要经过两个障碍物，途中从障碍物内侧转两次弯，已知两个障碍物转弯处的顶点为D，F,圆D和圆F的半径均为。图7 内公切线路径图两圆心连线与
18、内切线交点为O点。易证：因此O点为线段DF的中点，根据中点坐标公式：确定O点坐标后，用模型一就可以分别求出和的长度，以及确定C、E、M、N点坐标。沿外公切线前进的情况 如图8所示，机器人从起始点A到目标点B要经过两个障碍物，途中从障碍物外侧转两次弯，已知两个障碍物转弯处的顶点为M，N,圆M和圆N的半径均为。图8 外公切线路径在两圆心的的连线上找出中点O，过O点作DF垂线，交DF于H点。根据中点坐标公式可得O点坐标：由于,所以四变形MNDF为矩形，因此H也为DF的中点,且。根据勾股定理：因此对于H点坐标就有：解上面方程组可以求出H点坐标，确定H点坐标后，就可以用模型一分别求出路径和长度，以及切点
19、C、D、E、F坐标。以及所用时间。5.1.1.3模型计算 假设机器人从起始点到目标点经过的路径有条直线，长度分别为，有条弧线，长度分别为，则机器人到达目标点的总路为途中所用时间为： 其中，是转弯半径。【1】O-A的最短路径如图9所示，根据前文证明，O-A点可能的最短路线有两条，从5号障碍物左上角处拐弯，或从5号障碍物右下角处拐弯。图9 O-A可能最佳路线两条路线都为基本的线圆组合，用模型一可直接求解，用MATLAB程序解得，两条路径分别为，个单位，因此最佳总路程为从障碍物5左上经过路线，总路程为个单位；总时间秒，经过二条直线段和一以条以为圆心半径的弧线段，途中具体情况如表1：表1 O-A最短路
20、径途中情况起点坐标点终点坐标点转弯弧圆心距 离时 间直线10070.50595213.1405-224.499444.9弧线170.50595213.140576.60645219.4066802109.0513.7402直线276.60645219.4066300300-237.486847.4974总和-471.037296.1376【2】O-B的最短路如图10所示，机器人从O到B点有三条可能最短路线，在路径途中经过多次转弯到达目标点，因此先用模型二把路径分为若干个基本线圆组合，然后用模型一对每个线圆组合求解，可得出答案。图10 O-B可能最佳路线经MATLAB计算可得到三条路线的路程分别
21、为，,个单位；最佳总路程为路线一，总路程为个单位；总时间秒，经过六条直线段和五条分别以，为圆心半径的弧线段，具体起始点如表2：表2 O-B 最短路径途中情况起点坐标点终点坐标点转弯弧圆心距离时间直线10 050.136 301.649-305.7861.156弧线150.136 301.64951.6564 305.51260 3004.1881.6752直线251.6564 305.512157.5493 428.4419-162.2532.45弧线2157.5493 428.4419159.9754 435.7009150 4357.8543.1416直线3159.9754 435.700
22、9229.2334 466.1602-75.6615.132弧线3229.2334 466.1602230 470220 47013.61365.44544直线4230 470230 530-6012弧线4230 530225.1602 538.5658220 5309.94843.97936直线5225.1602 538.5658144.4749 591.6149-96.9519.39弧线5144.4749 591.6149140.6933 596.3414150 6006.10872.44348直线6140.6933 596.3414100 700-111.3622.272总和-853.7
23、127179.085【2】O-C的最短路径如图11所示，机器人从O到C点有三条可能最短路线，在路径途中经过多次转弯到达目标点，因此先用模型二把路径分为若干个基本线圆组合，然后用模型一对每个线圆组合求解，可得出答案。特别要说明的是在O-C的第二条路径中，通过前文的证明，经过圆形障碍物的转弯半径应该为。图11 O-C可能最佳路线经MATLAB计算得到距离分别为，个单位，最佳总路径为路线一，总距离为个单位；总时间秒，经过五条直线段和四条分别以，为圆心半径的弧线段，途中具体情况如表3：表3 O-C最短路径途中情况起点坐标点终点坐标点转弯弧圆心距离时间直线10 0412.0796 90.2186-421
24、.8484.368弧线1412.0796 90.2186418.2907 94.4085410 1007.67943.0718直线2418.2907 94.4085491.6 205.4275-133.0426.608弧线2491.6 205.4275492 206500 2000.69810.2792直线3492 206727.8719 513.8328-387.8177.562弧线3727.8719 513.8328730 520720 5406.45772.5751直线4730 520730 600-8016弧线4730 600727.7715 606.2932720 6006.8068
25、2.7227直线5727.7715 606.2932700 640-43.598.718总和-1087.6221.90485.1.2经过多个目标点（O-A-B-C-O）本问题的特点是要经过中间若干个目标点后在回到起点，不能简单的处理为求解每个两点之间的最短路径之和，因为机器人不能直线转向，所以在经过目标点时，应该考虑提前转向，且中间目标点应该在转弯弧上。因此对于中间目标点处转弯圆弧圆心的确定为本题的一个难点。经过中间目标点的路径（模型三）如图12所示已知点，分别为两个障碍物的顶点，且机器人要绕过B点障碍物经过中间目标点到另一个障碍物顶点转弯。其中为在圆心为半径为的圆上。由于点，分别引同侧相切于
26、圆心为的圆的切线，因此我们需要用点和点来确定圆心的位置。图12 机器人经过中途目标点图由于需要确定的圆心是以为半径点为圆上一点，所以需要进行搜索求解求出要确定的圆心。这样就将目标转化为距离和弧长最短的目标模型。根据点是圆上一点的关系就可以点为圆心为半径搜索得出圆心，那么得出关系为：将上述关系转化为圆的标准方程可以得到：根据两点直接的距离公式可以得出以下条件：由于与是两个圆的同侧公切线，两圆的半径相等而与和与是矩形的对边，所以，。在中由余弦定理可以得出：最后我们建立的模型为：根据上面模型我们可以求解出和圆心坐标，由于点的圆心与其他附近的圆是交错相切，根据交错相切时切线与圆心的连线的交点是两圆心的
27、的中间点（前文已经证明）可以得出与同侧相切时对应的点和的坐标，所以我们只需套用上面同侧相切的模型求解点的圆心坐标。点的圆心与的连线刚好与到圆的切线垂直，即点是与圆相交的切点。 通过本模型可以求出两个障碍物中间为中途目标点的线圆组合，其他情况的线圆组合可用模型一和模型二进行求解。模型计算 如图13所示，通过前文证明以及单目标点的计算模型，可以得到从O点出发，经过A、B、C三点在回到O点的最短路线只有一条。首先利用模型三算出A、B、C三点处转弯弧度的圆心坐标，然后用模型二把路径转化为若干个基本线圆组合。利用模型一计算。图13 O-A-B-C-O最短路径利用MATLAB编程计算得到，机器人从最佳总路
28、程为个单位；总时间秒，一共经过十六条直线段和十五条分别以, ,为圆心半径的弧线段，具体起始点如附表1：表4 经过多目标点最短路径途中部分情况起点坐标 点终点坐标 点转弯弧圆心距离时间直线10070.5059 213.1405-224.499444.8999弧线170.5059 213.140576.6064 219.406680 2109.253.7直线276.6064 219.4066294.1547 294.6636-229.9845.996弧线2294.1547 294.6636281.3443 301.7553290.8855 304.114115.35896.1436直线14727.
29、9377 513.9178492.0623 206.0822-387.8177.562弧长14492.0623 206.0822491.6552 205.5103500 2000.69810.2792直线15491.6552 205.5103412.1387 90.2314-133.0426.608弧线15412.1387 90.2314418.3348 94.4085410 1007.67943.0718直线16418.3348 94.40850 0-421.8484.368总和2812.52585.67125.2最短时间路径模型（问题二）模型分析本问题是研究机器人从O点出发绕过障碍物5到达
30、A的最短时间，根据问题一所求最短路，可以知道最短时间路线也是从障碍物5的左上通过，机器人所有的时间由直线段和弧线段两部分时间组成。由于最短时间和最短距离不是同一条路线，因此在求最短时间时先要确定最短时间的路径。机器人靠近障碍物时距离障碍物的最近距离不能少于10个单位。所以根据机器人在行走路线中要避免遇到的障碍物和影响其行动的范围来确定机器人行走的范围。机器人转弯时最大转弯速度为:机器人经过圆弧时间为：由上式可以看出当转弯半径变小时，机器人速度也变小，而机器人通过的圆弧长度也变小。的变化不好确定。当机器人转弯半径增大时，转弯速度也增大，而机器人通过的圆弧长度也随着增大。的变化不好确定。因此对于转
31、弯时间随转弯半径的变化关系，没有直接的线性关系。而对于转弯半径的变化在题目中是有限制的，过大会发生碰撞。过小（小于10）会发生侧翻。所以我们可以根据的变化范围，建立最小时间的非线性规划模型，对最小时的进行搜索求解。模型准备：如图14所示，已知是起始点，是终点，是障碍物5的左上顶点。假设机器人在C处以N为圆心，为半径转弯，经弧,在B点转弯，可以得到最短时间路径。连结BC，做ND于BC。ON长度为，AN长度为，切线OC的长度为，切线AB的长度为。令，由于B点和C点为切点，所以图14 最短时间示意图由两点之间的距离公式得出：因为B点和C点是切点，所以：根据勾股定理可以得到： 根据距离公式：在所以目标
32、分析根据机器人行走的直线距离和速度以及弧线长度和对应的弧线速度建立最短时间的目标：约束分析 根据机器人与障碍物的距离至少要超过10个单位可以得到半径的约束条件，即必须使圆弧离障碍物10个以上的单位：对于两个切点的范围：根据问题一证明的结论圆心在障碍物以内的距离最短可以得出约束条件为：因为机器人不能直线转弯，转弯路径由与直线路径相切的一段圆弧组成，因此对于C、B两点来说，必须保证是切点：C、B两点在圆上，与圆心的距离为半径：NOC和ABN必须是直角三角形，B点和C点为两直角边交点。模型的建立与求解综合以上条件，建立时间最短的优化模型：用Lingor软件编程求得最短时间为94.22825秒，转弯半
33、径为，具体结果见表5：表5 O-A最短时间路径途中情况起点坐标点终点坐标点转弯弧圆心距离时间直线10 069.8045 211.9779-223.175544.6351弧线169.8045 211.977977.74918 220.138782.1414 207.915311.78992.360433直线277.74918 220.13870 0-236.163647.23272总和-471.12994.22825结果分析 把结果同问题一比较发现最短路径未必所用时间最少，关键在于转弯半径和转弯圆心的选择。因此机器人在转弯过程中的转弯半径和转弯圆心的确定，对路线的优劣有着不可避免的影响。6模型推
34、广与评价模型改进本题障碍物并不是太多，当障碍物多的时候利用本题目所用的穷举法是不现实的。我们在做题目的时候有如下一些想法，先划去障碍物的危险区，再求出所有的切线，包括出发点和目标点到所有圆弧的切线以及所有圆弧与圆弧之间的切线，然后把这些相交联的线看成是最小生成树，和最短路。假设机器人从起点R到到目标点，路径一定是由圆弧和线段组成，设有m条线段，n条圆弧。那么目标函数可以表示为：利用matlab或者lingo等计算机软件，用最编程求最优解。此程序可以起到起点到目标点之间的路径进行优化求解模型评价优点：本模型简单易懂，便于实际检验及应用，可以应用到机动车驾驶证考试、城市汽车运输等一系列实际生活问题
35、，主要优点；1、运用多个方案对路径进行优化，在相对优化之中取得最优解。2、模型优化后用解析几何进行求解，精确度较高。缺点： 1、利用解析几何进行求解，精确度较高的前提计算时间比较慢，所以此模型利用起来效率比较低。 2、当障碍物足够多的时候本模型并不适合。参考文献1吴家龙弹性力学北京：高等教育出版社，20012 姜启源 谢金星，数学建模，北京：高等教育出版社，2003年；3 李 涛 贺勇军，应用数学篇，北京：电子工业出版社，2000年。207附录附表1：经过多目标点最短路径途中具体情况起点坐标 点终点坐标 点转弯弧圆心距离时间直线10070.5059 213.1405-224.499444.89
36、99弧线170.5059 213.140576.6064 219.406680 2109.253.7直线276.6064 219.4066294.1547 294.6636-229.9845.996弧线2294.1547 294.6636281.3443 301.7553290.8855 304.114115.35896.1436直线3281.3443 301.7553229.8206 531.8855-236.8347.366弧长3229.8206 531.8855225.4967 537.6459220 5306.80682.7228直线4225.4967 537.6459144.5033
37、 591.6462-96.9519.39弧长4144.5033 591.6462140.8565 595.9507150 6005.75962.3038直线5140.8565 595.950799.08612 690.2698-103.1620.632弧线599.08612 690.2698109.113 704.2802108.296 694.319120.76948.3078直线6109.113 704.2802270.8817 689.9611-162.432.48弧长6270.8817 689.9611272 689.7980270 6801.04720.4188直线7272 689.
38、7980368 670.282-97.9819.596弧线7368 670.282370 670370 6802.09440.8378直线8370 670430 670-6012弧长8430 670435.5878 671.7068420 6805.93412.3736直线9435.5878 671.7068534.4115 738.2932-119.1623.832弧线9534.4115 738.2932540 740540 7305.93412.3736直线10540 740670 740-13026弧长10670 740679.9126 731.3196670 73014.38465.7
39、538直线11679.9126 731.3196690.9183 648.6458-83.40316.6806弧线11690.9183 648.6458693.5095 643.1538709.7933 642.02276.172.468直线12693.5095 643.1538727.3214 606.8116-129.630525.9261弧长12727.3214 606.8116730 600720 6007.49282.997直线13730 600730 520-8016弧线13730 520727.9377 513.9178720 5206.45772.583直线14727.9377
40、 513.9178492.0623 206.0822-387.8177.562弧长14492.0623 206.0822491.6552 205.5103500 2000.69810.2792直线15491.6552 205.5103412.1387 90.2314-133.0426.608弧线15412.1387 90.2314418.3348 94.4085410 1007.67943.0718直线16418.3348 94.40850 0-421.8484.368总和-2812.52585.6712附图附图1 800800平面场景图程序一：基本线圆组合计算程序（仅以0-A为例，其它类似）
41、clco=0,0;c=80,210;m=300,300;r=10;oc=sqrt(o(1)-c(1)2+(o(2)-c(2)2);om=sqrt(o(1)-m(1)2+(o(2)-m(2)2);cm=sqrt(c(1)-m(1)2+(c(2)-m(2)2);a1=acos(oc2+cm2-om2)/(2*oc*cm);a2=acos(r/oc);a3=acos(r/cm);a4=2*pi-a1-a2-a3;d1=sqrt(oc2-r2);d2=sqrt(cm2-r2);d3=r*a4;dd=d1+d2+d3程序二：求A，B点所在的圆心坐标（以A为例）；%求经过（A）点弧的圆心坐标clcclear%坐标A=300,300; %所求圆弧上的坐标B=80,210; %一边圆心的坐标C=220,530; %另一边圆心的坐标R=10; %圆的半径sita=-pi:0.0001:pi; %搜索圆心坐标的范围for i=1:length
