数学建模 机器人避障问题之欧阳道创编

机器人避障问题

时间：2021.03.06 创作：欧阳道 一、摘要

本文讨论了机器人在平面场景中避障行走的问题，已知机器人的行走模式（直线与相切圆弧）以及场景障碍物的分布，计算出到平面各个给定点的最短路径，以及到A点的最短时间。

文中，首先，考虑到机器人与障碍物之间有10个单位的碰撞距离，故用CAD软件将平面场景图进行改进，再用CAD设计可能的最短路径。接着，对每条具体路径进行分解，得到三种基本线圆形模型（点圆模型，双圆异侧模型，双圆同侧模型），对这三种模型进行求解，得到各个模型直线长度以及转弯圆弧圆形角的表达公式。之后，参照具体的行走路径，构造合适的行走矩阵，用以判断每段路径所属的基本模型。路径总的长度可用如下公式表达：

最后，通过计算设计的集中可能的最短路径，我们得到每段的最短路径的长度分别为：

O——A路段：471.0372（单位）；

欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

O——B路段: 853.7001（单位）； O——C路段:1.0915103（单位）；

O——A——B——C——O路段:2.6778103（单位）。

对于问题二，我们在问题一的基础上分别利用直线最大速度和转弯最大速度计算出时间的表达式。为了方便计算，我们将转弯圆弧的圆心定在P（80,210）（场景中正方形5的左上角），这样得到时间T与转弯半径

的函数关系式：

通过MATLAB编程，画出其图像，求解得出：当半径=11.435时，时间T最小，其大小为94.5649（秒）。

关键词：最短路径 线圆模型 行走矩阵 MATLAB 二、问题重述

在一个800×800的平面场景图（见附录一），在原点O(0, 0)点处有一个机器人，它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述如下表：

编号 1 2 障碍物名称 正方形 圆形 左下顶点坐标 (300,400) 边长200 圆心坐标(550,450)，半径70 其它特性描述 欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

3 4 5 6 7 8 9 10 11 12 平行四边形 三角形 正方形 三角形 长方形 平行四边形 长方形 正方形 正方形 长方形 (360,240) (280,100) (80,60) (60,300) (0,470) (150,600) (370,680) (540,600) (640,520) (500,140) 底边长140，左上顶点坐标(400,330) 上顶点坐标(345,210)，右下顶点坐标(410,100) 边长150 上顶点坐标(150,435)，右下顶点坐标(235,300) 长220，宽60 底边长90，左上顶点坐标(180,680) 长60，宽120 边长130 边长80 长300，宽60 在图中的平面场景中，障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。

机器人直线行走的最大速度为 v05个单位/秒。机器

人转弯时，最大转弯速度为 vv()v01e100.12，其中 是

转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。

欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

现需建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中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、假设机器人能够准确的按照设计的路线行走行走，在其行走中不发生任何突发事故；

3、机器人以最大速度行驶，在转弯过程中没有发生侧翻，速度发生突变，不考虑加速减速。 四、符号说明

lij：圆Oi到圆Oj圆心的距离；

欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

i,i1,i2：机器人经过的第i个圆弧的圆心角；

i,i1：第i段直线多对应的圆心角

r：圆的半径；

mi,i1：机器人经过的第i段直线的长度；

S:行走路径的总的长度； T：机器人行走的总的时间

N：机器人行走经过的总点数（包括起点终点以及转弯圆弧的圆心）；

A：行走矩阵。 五、模型建立

对于该题建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型的研究，主要是用尽可能短的路径和时间避开障碍物到达目标点。根据题目中的要求可知，机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走，故可把各障碍物的边界扩大10单位。利用CAD软件制图可在距每个障碍物的边缘10个单位处添加外边框，形成新的屏障，特别注意的是在障碍物顶点处使用圆弧。机器人就可在新屏障外的范围内随意活动，不用担心发生碰撞，根据原图修改后的图形见下图1。

欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

B(100, 700)

C(700, 640)

A（300,300）

图1

机器人行驶路线是由直线段和圆弧组成。机器人从O(0, 0)出发，建立数学模型求得O→A、O→B、O→C和O→A→B→C→O的最短路径。现将各个路段的情况进行综合分析，根据每个路段所遇到的情况，从起始点到目标点的最短距离应该是直线段与圆弧组成，由已知的数学知识，两点之间线段最短，故机器人走的直线越多，路径越短，也就是说当机器人绕过障碍物的时候，半径越小，路径越短，根据题意，转弯半径可按最小半径10来计算，经过分析，可建立如下三个线圆模型。

欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

模型一：（点圆模型）

该模型主要求解O1——O2的路径长度，该路径只有一个转弯，由图2易知，SO2DDCCO1，C、D均为直线与圆的切点，CD为圆弧，为圆弧对应的圆心角的大小，根据已积累的知识，圆弧的长度为圆弧对应的圆心角与圆半径的乘积，即r，同时利用余弦定理

a2b2c2cosC2ab，即可求得总距离为：

22r2l12r2r； S=l13222l13l12l23rr其中 =2arccosarccosarccos ll2ll13121312D

C

O3

O2

O1

图2

模型二：（双圆异侧模型）

欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

该模型是为了计算O1——O4的距离，从起始点到目标点经过圆弧异侧拐弯（如图3），根据已知点O1、

O2、

O3、

O4可求得

lij的长度。

SO1AABBCCDDO4，AB、CD为两段圆弧，1、

2为其对应的圆心角，BC与O2O3的交点E是这两条线

段的中点，根据两个全等三角形以及勾股定理，可求得BC长度。

其

中

，

2222rrlll1223132arccosarccosarccos 12l12l12l23l23O4

B

O3

D

E

C

A

O2

O1

图3

模型三：（双圆同侧模型）

该模型是为了计算O1——O4的距离，从起始点到目标点

欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

经过圆弧同侧拐弯（如图4），添加辅助线，连接

O1O3、O2O4，运用几何知识轻易能够证明EF//O2O3。由

图4易知SO1DDEEFFCCO4,可以根据已知点的坐标求出所需线段的长度，进而求得起始点到目标点的总距离。

其

中，

222222l12l23l13l34l32l24r12(arccosarccosarccos)

2l122l12l232l34l32F E

D

C

O3 O2

O1

O4

图4

综合模型：

在实际情况中，机器人所走的路线是以上三种模型的结合。设计好机器人的行走方案，可根据设计好的方案构建行走矩阵，构建方法如下：

欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

1Ai2

3i段为模型1 i段为模型2 i段为模型3

则i段的直线长度为： 其中i=1,2…N-1;

i段为模型1

i段为模型2 第i段与i+1段之间的转弯圆弧所对应的的圆心角

为：

其中i=1,2…N-2；

i段为模型3

i,i1i1,i

i段为模型1

机器人行走的总的长度为：

六、模型求解 问题（1）：

i段为模型2

i段为模型3

根据所建立的数学模型，用CAD画出可能的最短路径，构建每条路线的行走矩阵，通过MATLAB编程计算出每天路线的实际长度，从而得到最短路径。

1、O——A路段，这是四个路段中最简单的情况，从O到A经过了一个转弯，从图5中易看出有两种方案，虚线与实线各代表一个方案。

欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

A（300,300）

O1（80,60）

O（0,0）

图5

利用MATLAB编程求解，计算结果如下： 机器人从O到A的行走路线长度为471.0372； 同理，O从下面绕到目标点A的总的路线长度为498.4259；

通过比较两种方案的结果易知，机器人在点O从上面绕到目标点A的距离最短，期最短路线长度为471.0372 。

2、O——B路段，经过分析与整理，我们得到四种

欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

方案，如图6所示①②③④，在这四种方案中，三种模型全部都要用到，模型一在O——A路段已详细说明，模型二就是从起始点到目标点经过的圆弧在所走路径的异侧，而模型三就是从起始点到目标点经过的圆弧在所走路径的同侧，从O——B路段，有多次转弯，具体见图6。

B

（100,700）

③

①

②

④

O

（0,0）

图6

就①路线而言，机器人经过了五次转弯，根据三种模型中的理论公式，需要把各个圆弧与直线长度求得，可利用MATLAB软件对其进行编程。计算结果如下：

欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

①路线机器人行走的总距离为853.7001； ②路线机器人行走的总距离为877.3841； ③路线机器人行走的总距离为990.1608； ④路线机器人行走的总距离为1.0584103；

经过比较可得①路线为最短路径，即机器人在点O从上面绕到目标点B的距离最短，期最短路线长度为853.7001 。

3、O——C路段，经过整理分析，我们得到四种方案，具体见图7，

欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

C

（700,640）

①

②

④

③

O（0,0）

图7

每条路线都是由圆弧与直线段，但是该路段与其他路段相比，又有其不同之处，在③路线中有一部分是在两个不同大小的圆的异侧和同侧（如图8，图9所示）

O1

B

A

E

O2

图8

欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

就图8容易看出，MAB12arccosE

A

rlRl12r212R2 RrRrRrRr，21arccos l12l12B

22O1

O2

图9

就图9容易得出，MABl122(Rr)2

122arccosRrRr ，21arccos l12l12利用MATLAB软件对其进行编程。计算结果如下：

①路线机器人行走的总距离为

1.2243103；

②路线机器人行走的总距离为 1.2559103； ③路线机器人行走的总距离为1.1543103； ④路线机器人行走的总距离为1.0915103；

显而易见，经过比较可得④路线为最短路径，即机器人在点O从上面绕到目标点C的距离最短，其最短路线长度为1.0915103。

欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

4、O——A——B——C——O路段，这一路段需要结合之前求得的最短路径，当机器人在A、B、C转弯时，为确定其路径最短，既使A点处在机器人的转弯圆弧上，我们设立了如图11的路径，并计算出转弯圆弧的圆心。

O1

O

由图易算出转弯圆弧的圆心坐标为：图10

欧阳道创编 2021.03.06

A

欧阳道创编 2021.03.06

B(100, 700)

C(700, 640)

A（300,300）

O（0,0）

图11

需要注意的是，在C点附近，由于其位置的特殊性，原有的线圆模型不能很好的处理，我们采用两段相切圆弧的线路。

利用MATLAB软件对其进行编程。计算结果如下：

机器人行走的总距离为2.6778103 问题（2）

机器人从O (0, 0)出发，求得到达A的最短时间路

欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

径。通过问题（1）中对各个路段最短路径的求解，我们可以做出合理假设：机器人转弯圆弧的圆心在点P（80,210）的位置，而半径我们设为。由问题（1），可以得到机器人从O点到A的时间为（参照模型一）：

其中a为O1O3长度，b为O3O2长度，c为O1O3长度，为O1O3O2，由于圆心固定，其值为固定值。通过MATLAB编程，得到Tf()的函数图象如下图所示：

从图中可以看出，当半径=11.435时，时间T最小，其大小为94.5649。 七、模型评价与推广

优点：1、该模型设计了三种基本模型，将实际线路进行简化，从而降低了计算难度；

2、提出行走矩阵的概念，在程序中对不同模型进行判断，从而简化了程序，方便了计算，使得程序更具备一般性；

3、最终结果由MATLAB编程计算，计算结果真实可靠。

缺点：1、最短路径的设计上有一定的主观性，可能会

欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

与实际有所偏差；

2、在计算到A点最短时间时，未考虑机器人加速减速的情况，使得计算值与实际值相比偏大。

3、在计算到A点最短时间时，为了方便计算，将转弯圆弧的圆心确定在点P（80,210），模型过于简单粗糙，会与实际情况有所偏差。 八、参考文献

[1] 丁绪东编著，AutoCAD2007实用教程[M]，中国电力出版社，2007。

[2] 曹戈 ， 《MATLAB教程及实训》， 机械工业出版社 2008年5月1日。

[3] 孙祥，MATLAB 7.0基础教程,北京：清华大学出版社，2005。

[4] 戴光明.避障路径规划的算法研究[D].华中科技大学，计算机科学与技术学院,2004。

[5]薛定宇，陈阳泉，高等应用数学的Matlab解．清华大学出版社．2004.183～191。

[6]冯杰，黄力伟，王琴，尹成义，数学建模原理与案例，科学出版社，2007。

欧阳道创编 2021.03.06

欧阳道创编 2021.03.06

时间：2021.03.06 欧阳道创编 2021.03.06

创作：欧阳道 附录一场景图：