第九届“挑战杯”

甘肃省大学生课外学术科技作品竞赛

定西师范高等专科学校 数学系

机器人避障问题的优化模型建立与分析

（定西师范高等专科学校 数学系，指导老师：xxx x x）

【摘 要】本文针对机器人避障布置问题，从不同角度出发，以最短路径和最短时间路径为目标函数，建立了多个优化模型。做出了满足条件的机器人绕过障碍物行走的最短路径，并对A、B、C处各点所在圆弧的圆心的确定进行了详细的模型分析；通过建立方程模型，分析计算了机器人从O出发到达A点，机器人在圆弧路径上行走时对应的圆心位置，并研究了该圆心位置在一定的范围内变化对时间的影响，确定了机器人行走的最短时间路径。

针对问题一，先根据问题情况进行分类分析，一类是O-A,O-B,O-C两点之间用直线和圆弧光滑连接，可利用Autocad软件直接作图；另一类是经过中间点的连线O-A-B-C-O,需对各个中间点处的圆弧位置作分析推理，找出使路径最短的圆弧圆心。然后根据已有数据，充分利用Autocad软件的切点捕捉及标注功能等进行切线和圆弧作图、各条路径的线性标注和圆弧标注，再根据标注值对各路径上切线长和弧长求和并比较大小，选择出避障的最短路径。并对路径的各点建立模型，运用Mathematica软件求解，确定过各点的圆弧的圆心坐标，求解满足给定条件的机器人绕过障碍物行走的最短路径。

针对问题二，在保证障碍物顶点离圆弧最近（10个单位）的前提下利用Mathematica软件, 建模求解弧半径-时间函数，确定圆弧圆心和半径，并用Autocad作图、标注，通过计算推出机器人从O出发，到达A的行走最短时间路径。

【关键词】最短路径 优化模型 避障 Autocad软件 Mathematica软件

一、问题重述

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

在图1的平面场景中，障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。其框形图如图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的最短时间路径。

注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。

图2给出了根据问题要求和已知数据确定的机器人可自由行直的区域（障碍物外10个单位的轮廓线外空白区域）。

二、基本假设

1. 设障碍物外指定一点为机器人要到达的目标点，则目标点与障碍物的距离至少超过10个单位；

2. 规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径；

3. 机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位；

4. 为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走；

5. 除障碍物外机器人不受任何别的因素影响；

6. 机器人直线行走时以最大速度为个单位/秒匀速运行；

7. 机器人转弯时以最大转弯速度为做匀速率运行。如果超过该速度，机器人将发生侧翻，无法完成行走；

8. 直道和弯道连接点处速度变化瞬时完成，所需要的时间很短，可以忽略不计；

9. 设机器人为一质点模型，则体积大小可以忽略不计。

三、变量设置

四、符号说明

:第i个障碍物从左下第一个起逆时针到第j个顶点

五、模型的建立与求解

问题一的分析与求解

关键是绘制、标注出机器人绕过障碍物行走的最短路径及坐标，要求用直线与圆弧或圆弧与圆弧之间光滑连接，而不考虑行走的时间。因此，圆弧半径取最小值10个单位，以尽量减少弯道路径，行走路径尽量取过以各个障碍物顶点为圆心的弧的切线。对此：

(1)根据已有数据，充分利用Autocad软件的切点捕捉功能进行切线和圆弧作图，用Autocad软件的标注功能做各条路径的线性标注和圆弧标注，再根据标注值对各路径上切线长和弧长求和并比较大小，选择出避障的最短路径。

(2)对路径O-A-B-C-O,建立模型并用Mathematica软件求解，以确定过点A、B、C的圆弧的圆心。

1. 路径O-A的图示分析

(1)长度标注：

(2)坐标标注：

图4中的路径为O到A的最短路径，其长度为471.04（见表5），连接点及圆心坐标如表1所示。

表1：最短路径上连接点坐标

2. 路径O-B的图示分析

(1)可能的路径：

(2)路径长度标注：

说明：图6中OB后的1，2 ，3，4 , 5，6 分别表示O到B的路径序号，其中奇数序号表示各图中的左侧路径，偶数序号表示各图中的右侧路径。

比较各条路径的长度，知路径OB1最短，其长度为849.42（见表5）。

(3)最短路径上各连接点及圆心坐标标注（见右图和表2）

表2：最短路径上连接点及圆心的坐标

3. 路径O-C的图示分析

(1)可能的路径：

(2)路径长度标注：

(3)最短路径上各连接点及圆心坐标标注图如下：

图11中的路径为O到C的最短路径，其长度为1087.02（见表5），连接点及圆心坐标如表3所示。

表3：最短路径上连接点及圆心的坐标

4. 路径O-A-B-C-O的图示分析

考虑A、B、C处不能沿折线行走，需要确定过这些点的圆弧的圆心，作如下分析：

(1)对A点的模型分析:

图12 过A点的圆弧的圆心

设过A点的圆弧圆心为（如图3），则有以下关系：

,

建立路径PQRT的长度模型：

用Mathematica软件求上述二元函数的极值（见附件 ），结果为：

当9.1146， 4.1140时路径PQRT有最小值482.2310个单位，

所以过A点的圆弧的圆心坐标应为（9.1146，4.1140）。

(2)对B点的模型分析：

根据图，建立路径长度模型如下：

用Mathematica求解，得：

当时有最小值391.8719.

图14中的路径为O-A-B-C-O的最短路径，其长度为461.67（见表5），连接点及圆心坐标如表4所示。

表4：路径上连接点及圆心的坐标

注：表中含底纹部分为最短路径值。

问题二的分析与求解

由问题1知从O经附近到A的路径是本问题的唯一选择。

考虑求最短时间路径，假设机器人在附近圆弧轨道距的最小距离为10个单位，圆弧的圆心在内偏离横向个单位，纵向人单位，建立弧长模型如下：

时间与弯道半径的函数模型如下：

用Mathematica求解，有如下结论：

当时有最小值94.4636。

经检验得知，此值受圆弧圆心变动的影响很小，可以忽略不计。因而作图时可在Z5内取，得优化函数模型如下：

问题二的图示分析：

参考文献

[1] 姜启源，谢金星，叶俊，《数学模型》，北京：高等教育出版社，2003年。

[2] 王同科，张东丽，王彩华，《 Mathematica与数值分析实验》，北京：清华大学出版社, 2011年。

[3] 段绍娥，《AUTO CAD 2010实用教程》，长沙：中南大学出版社, 2011年

附 录

1.问题2公式推导

圆心在对角线上：

2.弯道速度与半径关系分析：

Plot[5/(1+Exp[10-0.1r2]),{r,10,30},PlotRange All]

全国大学生数学建模竞赛论文D