2012年数学建模D题机器人避障问题论文..docVIP

机器人避障问题 摘要 我们根据题目所给的800×800的平面区域和场景图中的12个不规则形状的障碍物，研究讨论了机器人避障最短路径和最短时间路径的问题。 问题一：避障最短路径有两种情形： 一、由原点出发到达各个目标点的最短路径； 二、由原点出发经过途中的若干个目标点到达最终目标点。 情形一：通过我们的证明知道（猜想一、猜想二）：具有圆形限定区域的最短路径是由两部分组成的：一部分是平面上的直线段，另一部分是限定区域的部分边界（即圆弧段）。这两部分是相切且连续的，依据这个结果，我们可以认为最短路径一定是由直线段和圆弧段组成的，因此我们建立了线圆结构模型，并采用三中分法、枚举法对可能是最短路的路径分析求解。这样一来无论路径多么复杂，我们都可以将机器人行走路径划分为若干个这样的线圆结构模型来求解。运用matlab求解最终得: 最短路径为：471.0372； 最短路径为：853.7001； 最短路径为:1090.8041； 对于第二种最短路径情形，我们在拐角处和目标点处均采用最小转弯半径r=10的形式，这样才能使得机器人不仅能够安全行走，且所走路径为最短路。最后建立优化模型运用MATLAB求解原点到达最终目标点的最短路径。即最短路径为2716.0471。 问题二：根据问题要求，运用图论中的最短路方法，建立最短时间路径模型，求出的最短时间路径，根据已知数据运行我们编制的matlab程序求解得机器人行走最短时间为94.2697。 关键词 避障最短路径 最短时间路径 图论 三中分法 MATLAB软件 一、问题重述 根据题目所给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的最短时间路径。 同时需要我们求出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。 图1 800×800平面场景图 二、问题分析 问题一：要求求出机器人从原点O(0,0)出发，按照一定的行走规则绕过障碍物到达目标点的最短路径，以及求出经过中间的若干个点并按照一定的规则绕过障碍物到达最终目标点的最短路径。 我们可以先采用包络线画出机器人行走的危险区域，这样一来，拐角处就是一个以障碍物某一顶点为圆心，以10为半径的圆弧。首先，如果假设拐角处的圆是一个滑轮，那么我们可以通过拉绳子的方法寻找可能的最短路径，（比如求O和A之间的最短路径，我们就可以连接O和A之间的一段绳子，以拐角处的圆弧为支撑拉紧，那么这段绳子的长度便是O到A的一条可能的最短路径），其次采用枚举法列出原点O到每个目标点的可能的最短路径，