《2012年数学建模d题机器人避障问题论文》由会员分享，可在线阅读，更多相关《2012年数学建模d题机器人避障问题论文（39页珍藏版）》请在金锄头文库上搜索。
1、1机器人避障问题摘要我们根据题目所给的的平面区域和场景图中的 12 个不规则形状的障800 800碍物，研究讨论了机器人避障最短路径和最短时间路径的问题。 问题一：避障最短路径有两种情形： 一、由原点出发到达各个目标点的最短路径； 二、由原点出发经过途中的若干个目标点到达最终目标点。 情形一：通过我们的证明知道（猜想一、猜想二）：具有圆形限定区域的最短路 径是由两部分组成的：一部分是平面上的直线段，另一部分是限定区域的部分边界 （即圆弧段） 。这两部分是相切且连续的，依据这个结果，我们可以认为最短路径一定 是由直线段和圆弧段组成的，因此我们建立了线圆结构模型，并采用三中分法、枚举 法对可能是最
2、短路的路径分析求解。这样一来无论路径多么复杂，我们都可以将机器 人行走路径划分为若干个这样的线圆结构模型来求解。运用 matlab 求解最终得: AO 最短路径为：471.0372； BO 最短路径为：853.7001； CO 最短路径为:1090.8041； 对于第二种最短路径情形，我们在拐角处和目标点处均采用最小转弯半径 r=10 的 形式，这样才能使得机器人不仅能够安全行走，且所走路径为最短路。最后建立优化 模型运用 MATLAB 求解原点到达最终目标点的最短路径。即OCBAO最短 路径为 2716.0471。 问题二：根据问题要求，运用图论中的最短路方法，建立最短时间路径模型，求出 A
3、O 的最短时间路径，根据已知数据运行我们编制的 matlab 程序求解得机器人行走 最短时间为 94.2697。关键词关键词 避障最短路径 最短时间路径 图论 三中分法 MATLAB 软件 2一、问题重述根据题目所给800800的平面场景图，在原点处有一个机器人，该机器人只(0,0)能在平面场景范围内活动。且不能与场景图中12个不同形状的障碍物发生碰撞，障碍 物的数学描述如下表： 编号障碍物名称左下顶点坐标其它特性描述1正方形(300, 400)边长2002圆形圆心坐标(550, 450)，半径703平行四边形(360, 240)底边长140，左上顶点坐标(400, 330)4三角形(280,
4、 100)上顶点坐标(345, 210)，右下顶点坐标(410, 100)5正方形(80, 60)边长1506三角形(60, 300)上顶点坐标(150, 435)，右下顶点坐标(235, 300)7长方形(0, 470)长220，宽608平行四边形(150, 600)底边长90，左上顶点坐标(180, 680)9长方形(370, 680)长60，宽12010正方形(540, 600)边长13011正方形(640, 520)边长8012长方形(500, 140)长300，宽60 在图（1）的平面场景中，障碍物外指定一点为机器人要到达的目标点（要求目标 点与障碍物的距离至少超过10个单位）。规定
5、机器人的行走路径由直线段和圆弧组成， 其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一 段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的最小半径为10 个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离 为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。机器人直线行走的最大速度为50v个单位/秒。机器人转弯时，最大转弯速度为21 . 010 0 e1)(vvv，其中是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。 我们需要解决的问题是：建立机器人从区域中一点到达另一点的避障最短路径和 最短时间路径的数学模
6、型。对场景图中4个点O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具体计算： (1) 机器人从O(0, 0)出发，OA、OB、OC和OABCO的最短路径。 (2) 机器人从O (0, 0)出发，到达A的最短时间路径。 同时需要我们求出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标 以及机器人行走的总距离和总时间。3图1 800800平面场景图二、问题分析问题一：要求求出机器人从原点出发，按照一定的行走规则绕过障碍物到(0,0)达目标点的最短路径，以及求出经过中间的若干个点并按照一定的规则绕过障碍物到 达最终目标点的最短路径。 我们可以先采用包络
7、线画出机器人行走的危险区域，这样一来，拐角处就是一个 以障碍物某一顶点为圆心，以 10 为半径的圆弧。首先，如果假设拐角处的圆是一个滑 轮，那么我们可以通过拉绳子的方法寻找可能的最短路径， （比如求 O 和 A 之间的最短 路径，我们就可以连接 O 和 A 之间的一段绳子，以拐角处的圆弧为支撑拉紧，那么这 段绳子的长度便是 O 到 A 的一条可能的最短路径） ，其次采用枚举法列出原点 O 到每个 目标点的可能的最短路径，最后比较其大小便可得出原点 O 到达各个目标点的最短路 径。 求解从原点到最终目标点的最短路径时，我们不仅要考虑障碍物拐角处的问题， 还应该注意经过途中目标点时的转弯问题。这时
8、如果再采用简单的线圆结构就不能解 决这类问题。因此，我们在拐点及途中目标点处均采用最小转弯半径（R=10）的形式， 然后建立优化模型对方案进行优化处理，最后求得原点到达最终目标点的最短路径。 问题二：要求求得机器人从原点 O 处出发到达目标点 A 的最短时间路径。由于机器人 的行走速度与行走路径有关，且机器人的行走路径是由有直线段和圆弧段组成的。机4器人在直线行走过程中的速度为 5 个单位/秒，在圆弧段的行走时，转弯速度与圆弧的半径成正比关系21 . 010 0 e1)(vvv，半径越大速度越大。要确定半径的长度，首先我们应该找出圆心的坐标其次计算半径的长度。三、模型假设1、假设机器人能够抽象
9、成一个点来处理。 2、假设机器人在直线行走时，都以最大速度匀速行驶。 3、假设在模型二的计算过程中，直线行走速度变为转弯速度时的时间间隔为 0。四、符号说明:第 i 段切线的长度。 Lj：第 j 段圆弧的长度。 L：从原点到达最终目标点的最短路径的总长度。 K:障碍物上的任一点与行走路径之间的最短距离。5、模型的建立5.15.1 模型猜想： 猜想一：具有圆形限定区域的最短路径是由两部分组成的：一部分是平面上的直 线段，另一部分是限定区域的部分边界（即圆弧段） ，这两部分是相切的，连续的。 （即问题分析中的拉绳子拉到最紧时的状况） 证明：假设在平面中有和两点，中间有一个半圆形的障碍物，证明( ,
10、0)(,0)从 A 到 B 的最短路径为 AB。平面上连接两点最短的路径是通过这两点的直线段，但是连接两点的线段于障碍 物相交，所以设法尝试折线路径。在 y 轴上取一点，若 适当大，则折线 ACB 与(0,)障碍物不相交，折线的长度为：显然随着 的减小而减小，| = 22+ 2| 减小 得，即,使得与都与障碍物相切，切点分别为 E 和 F,显然11115是这种折线路径中最短的。由于满足的角满足OEEC 1,所以易知10 ,又OEOFP、QAP |AP| 因所以,从而同理可得。AEEO,|AP| AE AE BF 再来比较之间路径长度和圆弧的长度的大小。若之间的路径可有极坐标PQEFPQ 方程,
11、则有,可得： = () 1 =2+ 23即路径的长度超过路径的长度。以上证明足以说明是满足条件到 的最短路径。猜想二：假设一个圆环可以绕着环上一个定点转动，那么过圆环外两定点连接一 根绳子，并以该圆环为支撑拉紧绳子，达到平衡时，圆心与该顶点以及两条切线的延 长线的交点共线图 2 证明猜想： 如图 2 所示，E 点就是圆环上的一个顶点，AB 就是拉紧的绳子，2O 就是切线 AC 和BD 的延长线的交点，证明1O、E、2O 三点共线。我们可以用力学的知识进行证明，因为是拉紧的绳子，所以两边的绳子拉力相等， 设为Fv，它们的合力设为0Fv，定点对圆环的作用力设为1Fv。那么由几何学的知识我们可以知道
12、0Fv一定与12OOuuuu u r 共线，而又由力的平衡条件可知：0Fv=-1Fv即12OOuuuu u r 与2EOuuuu r 共线，1O、E和2O 三点一定共线。5.2 模型一的准备1） 、有了的定理，我们就可以认为，无论起点到目标点的途中有多少个障碍物，5.1最短路径都应该是由若干个线圆结构所组成的。根据本题中存在障碍物的情况，且障 碍物在拐角处的危险区域是一个半径为 10 的圆弧。所以结合定理 5.1，求两点之间的 最短路径时，我们应该按照最小的转弯半径来计算才可达到最优。6线圆结构 5.21 如线圆结构 5.21，设 点坐标为, 点坐标为分别为机器人经过拐点分别A(1,1)B(3
13、,3)于隔离危险线拐角小圆弧的切点，圆的半径为 ，的长度为 ，的长度为 ，的长rABcAOaBO度为 ,角度AOB=1a AOC=, BOD=，COD=.求 AB 的长度，设为Lb解法如下：如上图可得有以下关系： = | + + | =2 2 = | =2 2 =(2 1)2+ (2 1)2 =(3 2)2+ (3 2)2 =(3 1)2+ (3 1)2 = 2+ 2 2 2 = = = 2 =2 2+2 2+ 2） 、而对于下图两种情况我们不能直接采用线圆的结构来解决，需要做简单的变换。情况一如图 4 所示：7线圆结构 5.22 我们假设 点坐标为，两圆心坐标分别为和， 点坐标为A(1,1)
14、(2,2)(3,3)B,我们很容易知道 点的坐标为(4,4)M2+ 32 2+ 32?这样我们可以利用 5.21 中的方法，先求 A 到 M，再求 M 到 B，这样把整个过程分成两段进行解即：ACDEFBACL =+=+DMMEFB。同理如果有更多的转弯，同样可以按照此种方法求解。情形二：线圆结构 5.23 这里我们依然设圆心坐标分别为和半径为 ，利用 5.21 的求解方1(2,2)2(3,3)式我们可以列出在该情形下的函数关系：| =2 2 = 1 =|12|= 8 = 2| =2+ 21= 1= 2+ 2 2222=(3 1)2+ (3 1)21= 2 1 1 22= 2= 2+ 2 1221 =(4 2)2+ (4 2)22= 2 2 2 2 这样用 D 和 E 任意一点作为分割点都可以将上图分割成两个如图 2 所示的线圆结构， 这样就可以对其进行求解。求解方法运用 MATLAB 软件进行求解（程序见附录） 。同理 有多个这样的转弯时，用同样的方法都可以进行分割计算
