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