文档介绍：2022全国大学生数学建模竞赛D题全国一等奖论文
2022高教社杯全国大学生数学建模竞赛
承 诺 书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规那么.
我们完全明白，在竞赛开始后参赛队员不能以任何方式〔们建立了从o点出发到任意目标点的0-1非线性整数规划模型，同时针对题意要求，具体构建了从o点出发到A的最短时间路径的0-1非线性整数规划模型，利用LINGO软件求解，获得了机器人从o点出发，到达A的最短时间路径， ，。相应圆弧的圆心坐标为〔，〕，两切点坐标分别为〔，〕、〔,〕。
本文确定路线思路循序渐进，先建立了有计算避障约束公式的普适性模型，再建立了以不取相交点来简化0-1变量取值关系的简化模型；给出了二种启发式算法，最短路径即最短时间路径具有一定可信度。同时第一个启发算法可以求得全局最优解，第二个启发算法是针对问题的NP属性减少求解时间而构建的，两个算法都具有较重要的意义。
【关键词】 机器人避障 最短路径 启发算法 0-1规划模型
3
一、问题重述
在一个800×800的平面场景图，在原点O(0, 0)点处有一个机器人，它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述如下表：
编号
障碍物名称
左下顶点坐标
其它特性描述
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
3
11
正方形
(640, 520)
边长80
12
长方形
(500, 140)
长300，宽60
在图1的平面场景中，障碍物外指定一点为机器人要到达的目标点〔要求目标点与障碍物的距离至少超过10个单位〕。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否那么将发生碰撞，假设碰撞发生，那么机器人无法完成行走。
机器人直线行走的最大速度为个单位/秒。机器人转弯时，最大转弯速度为，其中是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。
请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中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的最短时间路径。
注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。
二、问题分析
本问题要求机器人从区域中一点到达另一点的避障最短路径。机器人只要做到转弯时的圆弧半径最小为10个单位、与障碍物最近距离单时刻保持大于10个单位，那么可行走的路径就有无数条，假设想求得机器人从区域中一点到达另一点的避障最短路径，那么需要建立避障的最短路径模型，而建立避障的最短路径模型有一定难度。根据对问题的分析，我们认为可以从简单做起，先确定小范围内最短路径条件，如圆弧位置的影响，圆弧半径的大小，防止与障碍物碰撞条件等，通过确定最短路径条件来建立避障的最短路径模型。对于
4
最短路径的求取，我们可以通过确定穷举原那么，利用穷举法来求解，当然也可以通过构建启发式算法的进行求解。
对于要建立最短时间路径模