机器人避障问题数学建模论文

2011高教社杯全国大学生数学建模竞赛

承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）：

参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)：

日期： 2011 年 9 月 11 日

赛区评阅编号（由赛区组委会评阅前进行编号）：

2011高教社杯全国大学生数学建模竞赛

编 号 专 用 页

评 阅 人 评 分 备 注 赛区评阅编号（由赛区组委会评阅前进行编号）：

赛区评阅记录（可供赛区评阅时使用）：

全国统一编号（由赛区组委会送交全国前编号）：

全国评阅编号（由全国组委会评阅前进行编号）：

机器人避障问题

摘 要

本文通过在给定的平面场景范围内对机器人就如何躲避12个不同形状障碍物区域的避障行走问题进行探究，在出发点到目的点的多种情形中进行选择，并根据要求，保证所走的路线为直线段和圆弧。继而探究避障的最短路径及最短时间路径的数学模型，在此探究过程中，运用穷举法，进行各种行走路线的CAD绘图，利用平面几何的点、线、圆的关系求解行走路径所经过点的坐标、线段长度、和弧长，在各总长度中进行比较，找出最短路径。最终，根据机器人速度的数据，建立最短时间路径的数学模型，运用LINGO软件最终求出最短时间的路径。

针对问题一，根据题意，为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，可分别以障碍物的边界处绘制以10为半径的圆，从而确定安全的可行走的活动范围。利用平面几何知识，在给定的障碍物的坐标的基础上，求解各路径下的直线段和圆弧的长度并加总求和，利用平面几何的知识，假设未知切点坐标和圆心，以及根据固定点的坐标，建立模型，求解路线的距离。进而，比较同一目的地不同路径的总长度，最终，求得最短路径，结果如下所示：

O?A:471.03; O?B:853.77; O?C:1055.063; O?A?B?C?O:2701.932

对于求解O?A?B?C?O路径时，将路径划分为若干个切线圆结构来求解，建立目标函数，并利用目标函数建立优化方程组，运用LINGO软件，求解确定过A,B,C点圆弧不同圆心的坐标

针对问题二，由于转弯速度的不同，在问题一的基础上求解出转弯半径的取值范围，建立以转弯半径为变量的最短时间路径模型，并通过LINGO软件求解，并通过CAD软件做出求解路径的具体图形。

关键词： 避障 最短路径 穷举法 CAD LINGO 平面几何 优化模型

1

目 录

摘 要 ........................................................................................................................................ 1 1 问题重述 ................................................................................................................................ 1 2 问题分析 ................................................................................................................................ 2 3 模型假设 ................................................................................................................................ 2 4 符号说明 ................................................................................................................................ 2 5 模型的建立与求解 ................................................................................................................ 3

5.1 问题一的模型 ............................................................................................................. 3

5.1.1 模型建立 .......................................................................................................... 3 模型I .......................................................................................................................... 3 5.1.2 模型求解 .......................................................................................................... 7 5.2 问题二的模型 ........................................................................................................... 14

5.2.1 模型建立 ........................................................................................................ 14 模型II ...................................................................................................................... 16 5.2.2 模型求解 ........................................................................................................ 16

6 模型的评价与改进 ............................................................................................................ 117 7 参考文献 .............................................................................................................................. 17

1

1 问题重述

在一个800*800的平面场景图中，如图，在已知的12个不同形状障碍物的坐标区域，机器人从以原点（0,0）出发前往不同的目标点，并且不能与障碍物发生碰撞。障碍物的数学描述如下表所述：

编号 障碍物名左下顶点坐其它特性描述 称 标 1 (300, 400) 正方形 边长200 2 圆形 圆心坐标(550, 450)，半径70 3 (360, 240) 平行四边底边长140，左上顶点坐标(400, 330) 形 4 (280, 100) 三角形 上顶点坐标(345, 210)，右下顶点坐标(410, 100) 5 (80, 60) 正方形 边长150 6 (60, 300) 三角形 上顶点坐标(150, 435)，右下顶点坐标(235, 300) 7 (0, 470) 长方形 长220，宽60 8 (150, 600) 平行四边底边长90，左上顶点坐标(180, 680) 形 9 (370, 680) 长方形 长60，宽120 10 正方形 (540, 600) 边长130 11 正方形 (640, 520) 边长80 12 长方形 (500, 140) 长300，宽60

在机器人的行进过程中，规定机器人所走的路径为直线和圆弧所组成（不可有折线转弯），其中与直线相切的圆弧为不与障碍物发生碰撞的转弯路径，也可以由多个相切的圆弧路径组成，每个圆弧的半径最小为10个单位，否则将发生碰撞，导致机器人无法完成行走。

机器人直线行走的最大速度为v0?5个单位/秒，转弯时，最大的弯速为

v?v(p)?v01?e10?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 问题分析

本文研究的是以（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

?OC?(a?m)2?(b?n)211??22 ?OD?(a2?m)?(b2?n) （16）

?22CD?(a?a)?(b?b)1212??弧长为：

CD???r （17）

5)特别注意

由于障碍物2本身为圆，所以求解其上行走的切点坐标时，应对圆弧半径进行相应改正。将半径r?10改为r?80（80为障碍物本身半径70与障碍物和机器人之间最短距离10之和）。切求解点的坐标时，不能运用求交叉点的方法，需另行计算。

5.1.2求解最短路径

根据前面已证明绘图原则和求解路径长度和起始点坐标的方法，在求得线路O?A,O?B,O?C的最短路径的基础上求得O?A?B?C?O 路径。

1）O?A最短路径

（1）根据所制定的绘制路径的原则，在场景图中，绘制全部的O?A路径，有两条线路1,2,如下图2所示：

?

图6

（2）根据制定的求解路径长度和起始点坐标的方法进行求解，可得出O?A所走 7

路径长度的具体坐标如下表1所示：

表2：O?A路线1

O→T52→A 路线1 起点坐标 终点坐标 圆弧角路线距离 O→A 度 （弧长） 路线1 O→T51 (0,0) (70.5,213.1) 224.4994

(70.5,213.1) (76.6,29.4) 9.051 圆弧1 52°

T51→A (76.6,29.4) (300,300) 237.486

471.03 机器人行走总路程

表3: O?A路线2

O→T54→A 路线1 起点坐标 终点坐标 圆弧角路线距离 O→A 度 （弧长） 路线2 O→T54 (0,0) (232.1,50.2) 237.486

(232.1,50.2) (239.7,57.6) 9.051 圆弧1 52°

T51→A (239.7,57.6) (300,300) 249.799

498.4258 机器人行走总路程

由表2，表3，比较可得出O?A线路1是其最短路径的长度，为471.03

2）O?B最短路径

（1）根据所制定的绘制路径的原则，在场景图中，绘制全部的O?B路径,如下图X所示

图7

8

（2）根据制定的求解路径长度和起始点坐标的方法进行求解，可得出O?B所走路径长度的具体坐标如下表2所示：

表4：O?B线路1

O→T61→T62→ T72→T73→T73→T81→B 路线1 起点坐标 终点坐标 圆弧角度 路线距离 （弧长） O→T61 (0,0) (50.2,301,6) 305.777 (50.2,301.6) (51.7,305.5) 4.239 圆弧1 24° T61→T62 (51.7,305.5) (141.7,440.5) 162.249 (141.7,440.5) (147.9,444.8) 7.776 圆弧2 45° O→B

T62→T72 (147.9,444.8) (220.04,460.2) 75.663

路线1

(230,470) 13.655 圆弧3 (220.04,460.2) 78°

T72→T73 (230,470) (230,530) 60

(230,530) (225.5,538.35) 9.884 圆弧4 57°

T73→T81 (225.5,538.35) (144.5,591.6) 96.95

(144.5,591.6) (140.7,596.3) 6.1473 圆弧5 35°

T81→B (140.7,596.3) (100,700) 111.44

853.77 机器人行走总路程

表5： O?B线路2

O→T51→T63→T73→T81→B 路线1 起点坐标 终点坐标 圆弧角度 路线距离 （弧长） O→T51 (0,0) (70.3,210.05) 224.4992 (70.3,210.05) (76.01,219.03) 8.46 圆弧1 48° T51→T63 (76.01,219.03) (239.02,290.84) 178.11 12.217 圆弧2 (239.02,290.84) (244.98,300.65) 70° O→B

T63→T73 (244.98,300.65) (229.97,530.65) 230.488

路线2

9.94 圆弧3 (229.97,530.65) (225.55,538.41) 57°

T73→T81 (225.55,538.41) (144.51,591.64) 96.95

6.108 圆弧4 (144.51,591.64) (140.69,596.38) 35°

T81→B (140.69,596.38) (100,700) 111.44

878.21 机器人行走总路程

表6: O?B线路3 O→T53→T63→T73→T81→B 路线1 起点坐标 终点坐标 圆弧角度 路线距离 （弧长） O→T53 (0,0) (232.11,50.22) 237.4868 (232.11,50.22) (239.84,59.611) 13.43 圆弧1 77° T51→T63 (239.84,59.611) (244.99,299.79) 240.05 0.87 圆弧2 (244.99,299.79) (244.98,300.65) 5° O→B

T63→T73 (244.98,300.65) (229.97,530.65) 230.488

路线3

9.94 圆弧3 (229.97,530.65) (225.55,538.41) 57°

9

T73→T81 圆弧4 T81→B

(225.55,538.41) (144.51,591.64) (144.51,591.64) (140.69,596.38) (140.69,596.38) (100,700)

机器人行走总路程

35°

96.95 6.108 111.44 946.76

由表4，表5，表6，比较可得O?B的三条路径中，最短的路径为路线1，为853.77

3）O?C最短路径

（1）根据所制定的绘制路径的原则，在场景图中，绘制全部的O?C路径,如下图X所示

图8

（2）根据制定的求解路径长度和起始点坐标的方法进行求解，可得出O?C所走路径长度的具体坐标如下表1所示：

表7：O?C线路1

O→T61→T62→T74→T12→T94→T102→T103→C 路线1 圆弧角度 路线距离 （弧长） O→T61 305.77 4.188 圆弧1 24° T61→T62 162.2698 7.8539 圆弧2 45°

10

O→C 路线1

O→C 路线2

T62→T74 75.66

9.4247 圆弧3 54°

T74→T12 151.32

7.3303 圆弧4 42°

T12→T94 151.327

1.7453 圆弧5 10°

T94→T102 119.16

5.9341 圆弧6 34°

T102→T103 130

13.439 圆弧7 77°

T103→C 94.38

1239.802 机器人行走总路程

O→T52→T32→T2→T114→T113→C

路线1 圆弧角度 路线距离

（弧长）

O→T52 224.49

4.188 圆弧1 51°

T52→T32 341.76

7.8539 圆弧2 10°

T32→T2 169.70

9.4247 圆弧3 34°

T2→T114 170

7.3303 圆弧4 45°

T114→T113 80

1.7453 圆弧5 39°

T113→C 43.5

1059.992 机器人行走总路程 表8：O?C线路3

O→T54→T32→T2→T114→T113→C

路线1 圆弧角度 路线距离

（弧长）

O→T54 237.48

8.552 圆弧1 49°

T54→T32 318.43

8.9011 圆弧2 51°

T32→T2 169.70

9.4247 圆弧3 34°

T2→T114 170

7.3303 圆弧4 45°

T114→T113 80

1.7453 圆弧5 39°

T113→C 43.5

1055.063 机器人行走总路程

11

O→C 路线3

由表7，表8比较分析可得，在三条备选路径中，路线3是最短的，路径长为1055.063 4）确定过点A、B、C时的圆弧圆心位置和圆弧半径

无论路径多么复杂，我们都可以将路径划分为若干个切线圆结构来求解，目标函数可以表示为：

minL?Li r?i?1n?10 （18）

其中L表示总路径长，Li表示各分段路径中每一段的长度，因此利用该目标函数，

建立优化方程组，再借助LINGO对优化方程进行求解。例如在障碍物5经过A再到障

（x,y）碍物7的路径中，设经过A的转弯圆弧的圆心坐标为，经过障碍5和障碍7的转

弯圆心坐标为（80,210），（220,530），根据关系建立优化方程为：

minL?L1?L2?EF （19）

?L?(x?80)2?(y?210)2?122??L2?(x?220)?(y?2530)2 （20） ??L1?L22?BC)?EF?r*(??arccos2*L*L12???x?300利用LINGO软件编程求解：

min=l1+l2+EF;

l1=@sqrt((x-80)^2+(@sqrt(100-(x-300)^2)+300-210)^2); l2=@sqrt((x-220)^2+(@sqrt(100-(x-300)^2)+300-530)^2);

EF=10*(3.1415926-@acos((l1^2+l2^2-140^2-320^2)/(2*l1*l2))); x<300;

y=@sqrt(100-(x-300)^2)+300;

?

解得圆心坐标为（290.8854，304.1140），半径长度为10。

绘制过A点的线路图，如图9所示

图9

12

同理可证，过点B的圆弧圆心为（108.1715,694.0966）；过点C的圆弧圆心为（709.7939,642.0198），圆弧半径均为10。

5）根据所确定的过点A,B,C圆弧圆心坐标，求解最短路径（O→A→B→C→O）

1、先求从O到A的最短路径，可能成为O到A的最短路径的有两条路径，如图10：

图10

从O到A的两条路径的距离如下表9所示：

表9 O?A的线路1

路线1 O→T52 圆弧1 T52→A 圆弧2 总距离

距离(弧长) 224.4994 9.25 230.0239 15.707 479.4803 路线2 O→T54 圆弧1 T54→A 圆弧2 总距离 距离(弧长) 237.4868 10.64 251.4854 5.7595 505.3717

所以我们选择路线1：O→T52→A

2、 如图可知从A→B的最短路径只有一条：A→T73→T81→B

3、 由于无法从9号障碍物上方行走，因此从B→C的路径也只有一条：B→T91→T94→T102→T103→C 13

4、上文已求O→C的最短路径，所以C→O的最短路径为C→T113→T114→S2→T32→T54→O

所以从O→A→B→C→O的最短路径为：

O→T52→A→T73→T81→B→T83→T91→T94→T102→T103→C→T113→T114→S2→T32→T54→O 距离及弧长如下表10：

表10 O?A线路2

O→T52 圆弧1 T52→A 圆弧2 A→T73 圆弧3 T73→T81 圆弧4 T81→B 圆弧5 B→T83 圆弧6 T83→T91 圆弧7 T91→T94 圆弧8 T94→T102 圆弧9 T102→T103 圆弧10 T103→C C→T113 圆弧12 T113→T114 圆弧13 T114→S2 圆弧14 S2→T32 圆弧15 T32→T54 圆弧16 T54→O 总路程

14

224.4994 9.2522 230.0239 15.7073 236.5184 6.6986 96.9543 5.4894 103.0155 20.7680 162.3420 1.1451 97.9790 2.0135 60 5.9200 119.163 5.9291 130 13.5462 94.4673 38.3383 7.1911 80 11.8013 196.7232 12.6136 135.6466 13.6802 318.4337 8.5852 237.4861 2701.932

所以，最短路径：

O→T52→A→T73→T81→B→T83→T91→T94→T102→T103→C→T113→T114→S2→T32→T54→O的总长度为2701.932

5.2问题二（求解最短时间路径） 5.2.1 模型的建立

由问题1可知从O→A的最短路径为O→5(左上角)→A，当速度一定时，时间与路程成正比，因此只需先在最短路径上方画出安全行走范围，在安全范围内对转弯半径讨论即可得到行走时间最短的转弯半径。

为了求出安全行走范围，以5号障碍物左上角为圆心，半径R需要满足：（1）最小转弯半径R=10；（2）最大转弯半径必须保证机器人在6号障碍物右下角的安全行走。

通过分析，如图所示，只要保证机器人在酒红色区域行走即可，通过计算可知最大转弯半径为55.0824。所以，机器人以5号障碍物左上角顶点为圆心，在半径为[10,55.0824]区域内行走是安全的，在这个范围内可以找到最短时间路径。

设机器人转弯半径为r，以5号障碍物左上角点F为圆心，设A点与O点与圆F相切与E、D两点，根据几何关系可以求得OD，AE，DE弧的长度分别为：

dOD?(90?

421214r2?r50500?r2)2?(210?r2?r50500?r2)22525505050502525119911r2?r56500?r2)2?(?90?r2?r56500?r2)2825565056502825dAE?(?220?

dDE?r(??arccos(?1?115639((r2?r56500?r2?22853255650211641114r50500?r2)2?(r2?r56500?r2?r50500?r2)2)))505028532528252525

所以

T?因此该问题的模型为： minT s.t10?r?55.0824

其中，直线行走速度 v1?5m/s,转弯速度为

dAD?dOEd?DEv1v2

v2?v11?e10?0.1r

2 15

图11

5.2.2 模型求解

有lingo编程求解该优化模型，程序如下： min=(OE+AF)/5+EF/v;

OE=@sqrt((80-4/2525*r^2-21/5050*r*@sqrt(50500-r^2))^2+(210-21/5050*r^2+4/2525*r*@sqrt(50500-r^2))^2);

AF=@sqrt((-220+11/2825*r^2-9/5650*r*@sqrt(50500-r^2))^2+(-90+9/5650*r^2+11/2825*r*@sqrt(50500-r^2))^2);

EF=r*(3.1415926-@acos(-1+1/2*((1563/285325*r^2-9*r/5650*@sqrt(56500-r^2)+21*r/5050*@sqrt(50500-r^2))^2+(1641/285325*r^2+11*r/2825*@sqrt(56500-r^2)-4*r/2525*@sqrt(50500-r^2))^2)/r^2));

v=5/(1+@exp(10-0.1*r^2)); r>=10;

r<=55.0824; L=OE+AF+EF;

解得O?A的最短时间路径总时间为94.55895（秒），对应的转弯半径为r?11.50617，总距离为472.3807

16

6 模型的评价与改进

本文对机器人避障移动模式进行探讨，并给出了分别基于最小路径以及最小时间规则的优化路径。

本题主要研究机器人的避障行走问题，根据要求的机器人行走的转向方式，分析得出机器人从起点到目标点行走的最短路径的方法基本图形为线性和弧形的组合。在本题中存在的障碍物的不可行走区域为在拐点处的半径为10个单位的圆弧。利用穷举法，以最短路径为目标，将可能的行走路径列出，利用平面几何的知识以及求导原理，建立计算模型最终得出机器人行走路程的距离，在目标路径中选择最短的路径，得到最优解也即是最终求得的最短路径。在此过程中，利用CAD方法求得的路径长度是精确的，减少了工作量，提高了计算速度。

机器人避障问题的研究是人工智能，自动化控制，以及传感技术的多个领域研究成果的综合，在工业，农业，服务业等多个领域得到广泛的应用。本文的机器人避障问题的研究，在进行侦探，军事，搜救,病人监护等特殊场合的运用有着不可忽视的作用，对日后的避障能力在更高层次领域的运用起到了铺垫作用，具有较好推广前景。然而，在所给的12个障碍物，按照绘制最短路径的原则进行穷举是有限的，也是可行的，但是，当障碍物的个数不断增加，求得最短路径的方法可能会随之改变，而且利用穷举法求得最短路径的方法也是不可行的，在经济中也是不具有可行性，因此模型的推广面会受到影响。

参考文献

[1] 邹益民，高阳，高碧悦， 一种基于Dijkstra算法的机器人避障问题路径规划，数学

的实践与认识，第43卷第10期，2013

[2] 钟秋平，机器人避障优化模型，大众科技，第14卷160期，2012.

[3] 谢金星，优化模型与LINGO/LINGO软件[M]，北京，清华大学出版社，2005. [4] 李磊，叶涛等.移动机器人技术研究与未来 [J].机器人，2005.24（5）:475-477 [4] 霍迎辉，张连明，杨宜民.移动机器人路径规划的最短切线路径算法[J].自动化与信息工程，2003（1）：10-12

[5] 邹益民，高阳，高碧悦， 一种基于Dijkstra算法的机器人避障问题路径规划，数学的实践与认识，第43卷第10期，2013

17

6 模型的评价与改进

本文对机器人避障移动模式进行探讨，并给出了分别基于最小路径以及最小时间规则的优化路径。

本题主要研究机器人的避障行走问题，根据要求的机器人行走的转向方式，分析得出机器人从起点到目标点行走的最短路径的方法基本图形为线性和弧形的组合。在本题中存在的障碍物的不可行走区域为在拐点处的半径为10个单位的圆弧。利用穷举法，以最短路径为目标，将可能的行走路径列出，利用平面几何的知识以及求导原理，建立计算模型最终得出机器人行走路程的距离，在目标路径中选择最短的路径，得到最优解也即是最终求得的最短路径。在此过程中，利用CAD方法求得的路径长度是精确的，减少了工作量，提高了计算速度。

机器人避障问题的研究是人工智能，自动化控制，以及传感技术的多个领域研究成果的综合，在工业，农业，服务业等多个领域得到广泛的应用。本文的机器人避障问题的研究，在进行侦探，军事，搜救,病人监护等特殊场合的运用有着不可忽视的作用，对日后的避障能力在更高层次领域的运用起到了铺垫作用，具有较好推广前景。然而，在所给的12个障碍物，按照绘制最短路径的原则进行穷举是有限的，也是可行的，但是，当障碍物的个数不断增加，求得最短路径的方法可能会随之改变，而且利用穷举法求得最短路径的方法也是不可行的，在经济中也是不具有可行性，因此模型的推广面会受到影响。

参考文献

[1] 邹益民，高阳，高碧悦， 一种基于Dijkstra算法的机器人避障问题路径规划，数学

的实践与认识，第43卷第10期，2013

[2] 钟秋平，机器人避障优化模型，大众科技，第14卷160期，2012.

[3] 谢金星，优化模型与LINGO/LINGO软件[M]，北京，清华大学出版社，2005. [4] 李磊，叶涛等.移动机器人技术研究与未来 [J].机器人，2005.24（5）:475-477 [4] 霍迎辉，张连明，杨宜民.移动机器人路径规划的最短切线路径算法[J].自动化与信息工程，2003（1）：10-12

[5] 邹益民，高阳，高碧悦， 一种基于Dijkstra算法的机器人避障问题路径规划，数学的实践与认识，第43卷第10期，2013

17

本文来源：https://www.bwwdw.com/article/rcf7.html