机器人避障问题的解题分析建模集训.doc
《机器人避障问题的解题分析建模集训.doc》由会员分享,可在线阅读,更多相关《机器人避障问题的解题分析建模集训.doc(26页珍藏版)》请在三一文库上搜索。
1、机器人避障问题的解题分析摘要:本文对2012年全国大学生数学建模竞赛D题机器人避障问题进行了全面分析,对最短路的设计进行了理论分析和证明,建立了机器人避障最短路径的几何模型,对最短时间路径问题通过建立非线性规划模型,有效地解决了转弯半径、圆弧圆心位置和行走时间等问题。关键词:机器人避障;最短路径;Dijkstra算法;几何模型;非线性规划模型1 引言随着科学技术的进步和计算机技术的发展,机器人的应用越来越广泛,在机器人的应用中如何使机器人在其工作范围内为完成一项特定的任务寻找一条安全高效的行走路径,是人工智能领域的一个重要问题。本文主要针对在一个场景中的各种静态障碍物,研究机器人绕过障碍物到达
2、指定目的地的最短路径问题和最短时间问题。本文以2012年“高教社”杯全国大学生数学建模竞赛D题“机器人避障问题”为例进行研究。假设机器人的工作范围为800800的平面正方形区域(如图1),其中有12个不同形状的静态障碍物,障碍物的数学描述(如表1):图1 800800平面场景图表1编号障碍物名称左下顶点坐标其它特性描述1正方形(300, 400)边长2002圆形圆心坐标(550, 450),半径703平行四边形(360, 240)底边长140,左上顶点坐标(400, 330)4三角形(280, 100)上顶点坐标(345, 210),右下顶点坐标(410, 100)5正方形(80, 60)边长
3、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在原点O(0, 0)点处有一个机器人,它只能在该平面场景范围内活动,机器人不能与障碍物发生碰撞,障碍物外指定一点为机器人要到达的目标点。规定机器人的行走路径由直线段和圆弧组成,其中圆弧是机器人转弯路径。机器人不能折线转弯
4、,转弯路径由与直线路径相切的一段圆弧组成,也可以由两个或多个相切的圆弧路径组成,但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞,同时要求机器人行走线路与障碍物间的最近距离为10个单位,否则将发生碰撞,若碰撞发生,则机器人无法完成行走。机器人直线行走的最大速度为个单位/秒。机器人转弯时,最大转弯速度为(是转弯半径)。如果超过该速度,机器人将发生侧翻,无法完成行走。场景图中有4个目标点O(0, 0),A(300, 300),B(100, 700),C(700, 640),下面我们将研究机器人从O(0, 0)出发,求OA、OB、OC和OABCO的最短路径,以及机器人从O(0, 0)出发,到
5、达A的最短时间路径问题。2 静态避障问题中机器人行走最短路径的分析2.1 行走路径的设计在本例中障碍物有4种不同形状:矩形、平行四边形、三角形和圆形。考虑到机器人本身的形状和大小,为研究方便起见,将机器人视为一个点。机器人与障碍物之间的距离至少为10个单位,因此可以先用包络线画出机器人行走的危险区域(如图2),包络线内是机器人的禁入区。图2 障碍物包络图对障碍物的一个角点来说,其禁入区的边界应由两条直线和一条圆弧组成,两条直线分别平行于角点的两条边,间距为10个单位,圆弧是以障碍物角点为圆心,半径为10个单位的四分之一圆弧。可以证明具有圆形限定区域的最短路径由两部分组成,一部分是平面上的自然最
6、短路径(直线段),另一部分是限定区域的部分边界(即绳子拉到最紧时的圆弧部分),这两部分是相切的,互相连接(如图3所示)。由A绕过半圆形障碍物到达B点的路径有多条,其中最短路径为(E、F为切点),其他路径与AB直线围成的区域都覆盖这一路径与AB直线围成的区域,由此证明1。图3由此可以确定机器人的行走路径应为线圆结构,那么是否是转弯半径越小,行走路径就越短呢?为此需要求在已知两个固定点和圆弧圆心坐标的情况下,圆弧半径r为何值,才能使机器人的行走路径最短。图4如图4,已知两个固定点,圆心,可以求得两切点坐标,设半径为,圆弧所对的圆心角为,的路径长度为,则 将路径函数对求导,得因为,,所以.,则函数为
7、单调递增函数,因此当圆弧半径逐渐增加时,机器人的行走路径会增大,逐渐降低时,机器人的行走路径会减小2,本题规定转弯半径最小为10个单位,所以在路径设定时应将转弯半径设定为最小值10个单位。根据以上分析,对于静态障碍物机器人的行走路径应遵循以下三个原则:原则一:机器人的行走路径为线圆结构,由两条切线和一段圆弧组成;原则二:每个路口至多发生一次转弯,并以障碍物顶点为转弯圆弧的中心;原则三:机器人转弯圆弧半径为最小允许半径10个单位。2.2 最短路径的选择 从起点到达目标点有多条路径,根据Dijkstra算法可以找出从起点到达每一个目标点的最短路径。本文采用带权的有向图表示机器人的行走路径,途中节点
8、为障碍物的角点,边表示障碍物之间的联系,权表示线路的长度(节点之间的直线距离)。从顶点出发,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径就是所求最短路径,Dijkstra算法就是按路径的长度递增次序产生最短路径的算法3。 下面以 为例,确定的最短路径。如图5所示,根据障碍物的形状和位置,本文给出了机器人从O(0, 0)出发避过障碍物到达目标B点的4条较优路径。 图5画出的非循环网络图(如图6):B621306O230601121712259921647017978162238B5B3B6B2B4B1B9B77B8017111299569237399705159508329图
9、6运用Dijkstra算法算出的最短路径,最短路算法如下:1、 起点O记为,终点B记为;2、 从网络的终点开始,令它的标号为零,并用方框记录在图6中;3、 计算结点的标号,设结点已标号,结点指向,则的标号可按算式:求出,其中是的标号,是结点与之间的直线距离;4、 重复上述计算,直到求得起点的标号为止,此标号即为最短路的长度;5、 确定最短路径,从起点开始,顺网络的箭线前进,若有几条箭线,则选取箭线所指标号最小且满足条件的结点为最短路径所经过的结点。在图6中,最短路径为:.应用上述算法可得到从点出发,分别到达各目标点的最短路径:图7的最短路径为: (如图7)图8的最短路径为:(如图8)图9的最短
10、路径为:3 最短路径计算模型3.1 单个目标点的最短路径根据前面制定的行走路径原则,起点到目标点无论中间障碍物有多少,最短路径都应该是若干个线圆结构所组成,圆弧中心为障碍物的顶点,半径为机器人转弯最小半径10个单位。观察这四条路径,发现所有行走路径都可归结为以下三种类型:类型一 图10 线圆结构1如图10,设O()为起点,A()为目标点,C和D分别为直线与转弯圆弧的切点,障碍物的顶点(即转弯圆弧的圆心),圆的半径为,的长度为,的长度为,的长度为,设的长度为L,则,由图10可得以下关系: 在中: 在中: 在中: 所以: 从而可得: 这个模型运算简洁,只需将起点、目标点和障碍物顶点坐标输入模型,M
11、ATLAB就能很快计算出来4,计算程序见附录1。类型二:对于图11这种线圆结构,需要做简单的变换,才能求出的路径长度。 图11 线圆结构2 假设两圆心坐标分别为和,M点为两圆心连线和两圆公切线的交点,坐标为,那么很容易可以求得:这样就可以利用类型一中的方法,先求A到M的长度,再求M到B的长度,分两段就可以求解。同理如果有更多的转弯,同样可以按照此种方法分解。 类型三图12 线圆结构3如图12,如果两圆弧的公切线平行于两圆圆心连线,求的路径长度。设各点坐标分别为起点A (,),目标点B(),障碍物顶点,障碍物顶点),半径为分别是的长度,设的长度为,则解法如下:由图12,可以得到以下关系:a=,b
12、=,c =, , 在中,由余弦定理可得:在中,=arccos所以: 同理:;=arccos;则 运用MATLAB进行计算,MATLAB计算程序见附录2.3.2 多个目标点的最短路径 机器人从起点出发,依次经过指定的中间目标点最后到达终点,是多个目标点的最短路径问题。比如的最短路径的计算。由于机器人的行走路线为线圆结构,不能折线转弯,因此中间目标点应位于某个半径为的圆周上,这里我们仍按照最小允许半径为10个单位,则只需计算出过A、B、C三点的圆心位置即可,这样就将多目标点的最短路径问题转化成了单目标点的最短路径问题。求过A、B、C三点的圆心位置的问题可通过建立非线性规划模型求得。(1) 过A点圆
13、弧的圆心图13如图13,障碍物顶点,顶点,,切点,过A的圆弧圆心,最短路径为,则建立非线性规划模型s.t. 运用LINGO13编程计算,计算程序见附录3.(2) 过B点圆弧的圆心图14如图14,障碍物顶点,顶点,,过B的圆弧圆心,最短路径为,则建立非线性规划模型运用LINGO13编程计算,计算程序见附录4.(3) 过C点圆弧的圆心图15如图15,障碍物顶点,顶点,,过C的圆弧圆心,圆与圆的公切线为,切点,圆与圆的公切线为,切点,最短路径为,则 建立非线性规划模型 运用LINGO13编程计算,计算程序见附录5.运用LINGO对模型求解,过A、B、C的圆弧圆心坐标计算结果(如表2):表2 过A、B
14、、C的圆弧圆心坐标经过点圆弧的圆心坐标A(290.8854,304.1140)B(107.3884,693.2612)C(709.6622,637.4229) 3.3 切点坐标的计算模型要准确计算出机器人行走路径的长度,必须要知道每一段圆弧的起点和终点,即切点坐标,通过观察上述三种线圆结构的切点主要有两种类型,一种是两圆圆心连线与公切线相交,另一种是两圆圆心连线与公切线平行。(1) 第一种类型的切点两圆圆心连线与公切线相交,则圆心连线的中点在切线上,可由两圆圆心坐标确定中点坐标,此问题就可以转化为求圆弧外的点与障碍物的转弯圆弧形成的切线的切点(如图16)图16设切点,起点O(,),圆心M(,)
15、,求切点C的坐标在中由勾股定理可得:,即又因为切点C在圆M上,故联立方程组运用MATLAB解方程,求出切点的坐标, MATLAB程序见附录6。 (2) 第二种类型的切点图17两圆连线与公切线平行(如图17),设切点,圆心,圆心(),半径为,求切点的坐标。解法如下:直线的斜率为,的直线方程为,因为,所以DE的直线的斜率也为在DE直线上找一点,则DE直线方程为,即,又因为切点D在圆上,满足圆的方程,故,建立方程组,解方程可求得D点的坐标, MATLAB程序见附录7。 如果公切线在障碍物中心连线的下方,模型需要做以下变换再计算。根据以上模型可计算出、以及的所有切点坐标,直线段长度和圆弧长度,计算结果
16、见附录8。4 最短时间路径模型的建立和求解机器人的行走速度与转弯半径有关,假设行走速度与转弯半径之间满足(其中为直线行走速度),那么与最短路径问题不同,转弯半径不再是越小越好,转弯半径越小,虽然行走的距离也越短,但是速度会变慢,这样行走速度反而可能会增加,因此,应选择一个适当的转弯半径,使得行走时间最短5。 以为例,研究最短时间路径问题。以机器人从原点出发到达点的时间最少为目标建立优化模型。转弯半径越大速度越快,走最短距离的时间不一定是最短的到达时间,因此应对转弯半径、转弯所走的圆弧的圆心进行重新搜素,建立非线性规划模型6。图18如图18,起点,目标点,障碍物5的顶点,切点,转弯圆弧的圆心,圆
17、心角为,半径为,的路径为,时间为.则 建立目标函数编写LINGO程序,应用LINGO13求解,计算程序见附录9,计算结果(如表3):表3 的最短时间路径路径起点坐标终点坐标圆弧圆心坐标圆弧半径总路程总时间0.00000.000069.8049212.7391469.896894.340569.8049212.739176.9877220.117880.9394209.085611.718676.9877220.1178300.0000300.00005 模型的评价与推广5.1 模型的优点(1)将机器人避障行走路线用若干个线圆结构组成建立的模型各点坐标和长度都能直接得出结果,用解析几何方法进行计
18、算,精确度较高。(2)运用多个方案进行优化,在相对优化中能取得最优解。(3)模型简单易懂,便于实际检验及应用。5.2 模型的缺点(1)此模型需要全局优化来求解,求解结果往往因为迭代产生一定的误差,但是这个误差在可允许的范围内。(2)在障碍物较多时,且形状不规则时,模型显得较为繁琐。非线性变量越来越多会导致求解时间越来越长,解的可求性也越来越差。5.3 模型的改进及推广本题只涉及12个障碍物,如果障碍物较多,到达目标点的路径就较多,这时可应用网络模型计算最短路。如果障碍物形状较复杂,单纯用解析几何知识计算较困难,模型需要进一步改进。机器人避障模型可以应用于货物运输、管道输送等领域,应用此模型能较
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 机器人 问题 解题 分析 建模 集训
链接地址:https://www.31doc.com/p-2552489.html