全国大学生数学建模竞赛-机器人避障问题南昌理工学院.docVIP

PAGE1

机器人避障问题

摘要

本文是机器人避障路线设计问题，要求我们建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。

针对问题一，为使机器人不与障碍物碰撞，在原障碍物的边界向外延伸10个单位，并在顶点处以半径为10个单位向外做圆，形成一条机器人行走的“安全路径”，即机器人可以贴着“安全路径”行走。

首先，通过证明可以在众多的行走路线中适当减少些路径，再由这些潜在的最短路径，利用图论的知识对其进行最短路径的求解，通过Floyd算法得到机器人从O(0,0)出发，O→A、O→B、O→C和O→A→B→C→O的折线最短距离分别为：471.041、853.088、1092.819、2716.431折线最短总时间分别为：96.018、179.241、233.329、568.318。

然后，对模型一进行优化，考虑机器人圆弧转弯路径，通过定理的证明可知在半径最小时并把拐弯圆弧的圆心定在各个端点。运用几何定理对每段最短路径分段处理，联立方程组建立模型二，利用lingo12求解各切点即每次的起点与终点坐标。最后，利用matlab7.0求解直线和弧长及行走时间（结果见表五至表八）。

针对问题二，求解到的最短时间路径，此时最短时间与最短线路、最短线路上拐弯次数以及拐弯半径的大小有关，由拐弯半径与速度的函数关系式：用matlab7.0绘制图像分析和探讨可知：在半径满足时，机器人拐弯速度趋近极大值。所以，在一定的半径范围之内，速度不再是限制时间最小的约束条件，那么最短时间的确定就可以转化成最短路径的求解。因此，在拐弯时速度不再发生改变时，半径越小对最短拐弯时间越有利。对于怎么样去确定合适的半径使得行走的时间最短，我们利用问题一中求解的由到的最短线路中切点的坐标来确定模型三中机器人行走直线段的方程。并利用题目的数据及相关的限制条件对问题二建立非线性目标规划的有哪些信誉好的足球投注网站模型，并利用lingo对其进行有哪些信誉好的足球投注网站，从而找到最合适半径以及此时对应的拐弯圆弧的圆心坐标。随着拐弯半径及圆心的改变会使得有哪些信誉好的足球投注网站出来路径中的切点发生改变得到两切点坐标为、，此时机器人拐弯行走路程的最短时间为：。

关键词：机器人避撞图论Floyd算法非线性目标规划最佳半径

一问题重述

图1是一个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

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的最短时间路径。

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

图1800×800平面场景图

二问题分析

问题一：求解两点之间通过拐