《机器人避障问题的解题分析建模集训》由会员分享，可在线阅读，更多相关《机器人避障问题的解题分析建模集训（19页珍藏版）》请在金锄头文库上搜索。
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)边长1506三角形(60,300)
3、上顶点坐标(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)出发，到达A的最短时间路径问题。2 静态避障问题中机器人行走最短路径的分析
5、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图6运用Dijkstra算法算出的最短路径，最短路算法如下：1、 起点O记为,终点B记为；2、 从网络的终点开
9、场，令它的标号为零，并用方框记录在图6中；3、 计算结点的标号，设结点已标号，结点指向，则的标号可按算式：求出，其中是的标号，是结点与之间的直线距离；4、 重复上述计算，直到求得起点的标号为止，此标号即为最短路的长度；5、 确定最短路径，从起点开场，顺网络的箭线前进，假设有几条箭线，则选取箭线所指标号最小且满足条件的结点为最短路径所经过的结点。在图6中，最短路径为：.应用上述算法可得到从点出发，分别到达各目标点的最短路径：图7的最短路径为： 如图7图8的最短路径为：如图8图9的最短路径为:3 最短路径计算模型3.1 单个目标点的最短路径根据前面制定的行走路径原则，起点到目标点无论中间障碍物有多
10、少，最短路径都应该是假设干个线圆构造所组成，圆弧中心为障碍物的顶点，半径为机器人转弯最小半径10个单位。观察这四条路径，发现所有行走路径都可归结为以下三种类型：类型一 图10线圆构造1如图10，设O为起点，A为目标点，C和D分别为直线与转弯圆弧的切点，障碍物的顶点即转弯圆弧的圆心，圆的半径为，的长度为，的长度为，的长度为，设的长度为L，则，由图10可得以下关系：在中：在中：在中：所以：从而可得：这个模型运算简洁，只需将起点、目标点和障碍物顶点坐标输入模型，MATLAB就能很快计算出来4，计算程序见附录1。类型二：对于图11这种线圆构造，需要做简单的变换，才能求出的路径长度。 图11线圆构造2
11、假设两圆心坐标分别为和,M点为两圆心连线和两圆公切线的交点，坐标为，则很容易可以求得:这样就可以利用类型一中的方法，先求A到M的长度，再求M到B的长度，分两段就可以求解。同理如果有更多的转弯，同样可以按照此种方法分解。 类型三图12 线圆构造3如图12，如果两圆弧的公切线平行于两圆圆心连线，求的路径长度。设各点坐标分别为起点A (,),目标点B(),障碍物顶点,障碍物顶点),半径为分别是的长度，设的长度为,则解法如下：由图12，可以得到以下关系：a=,b=,c =, ,在中，由余弦定理可得：在中,=arccos所以：同理：；=arccos；则运用MATLAB进展计算，MATLAB计算程序见附录
12、2.3.2 多个目标点的最短路径 机器人从起点出发，依次经过指定的中间目标点最后到达终点，是多个目标点的最短路径问题。比方的最短路径的计算。由于机器人的行走路线为线圆构造，不能折线转弯，因此中间目标点应位于*个半径为的圆周上，这里我们仍按照最小允许半径为10个单位，则只需计算出过A、B、C三点的圆心位置即可，这样就将多目标点的最短路径问题转化成了单目标点的最短路径问题。求过A、B、C三点的圆心位置的问题可通过建立非线性规划模型求得。（1） 过A点圆弧的圆心图13如图13，障碍物顶点,顶点,，切点，过A的圆弧圆心，最短路径为,则建立非线性规划模型s.t. 运用LINGO13编程计算，计算程序见附
13、录3.（2） 过B点圆弧的圆心图14如图14，障碍物顶点,顶点,，过B的圆弧圆心，最短路径为,则建立非线性规划模型运用LINGO13编程计算，计算程序见附录4.（3） 过C点圆弧的圆心图15如图15，障碍物顶点,顶点,，过C的圆弧圆心，圆与圆的公切线为,切点，圆与圆的公切线为,切点，最短路径为,则建立非线性规划模型运用LINGO13编程计算，计算程序见附录5.运用LINGO对模型求解，过A、B、C的圆弧圆心坐标计算结果(如表2)：表2 过A、B、C的圆弧圆心坐标经过点圆弧的圆心坐标A290.8854，304.1140B107.3884，693.2612C709.6622，637.4229 3.
14、3切点坐标的计算模型要准确计算出机器人行走路径的长度，必须要知道每一段圆弧的起点和终点，即切点坐标，通过观察上述三种线圆构造的切点主要有两种类型，一种是两圆圆心连线与公切线相交，另一种是两圆圆心连线与公切线平行。（1） 第一种类型的切点两圆圆心连线与公切线相交，则圆心连线的中点在切线上，可由两圆圆心坐标确定中点坐标，此问题就可以转化为求圆弧外的点与障碍物的转弯圆弧形成的切线的切点如图16图16设切点,起点O(,),圆心M(,)，求切点C的坐标在中由勾股定理可得：，即又因为切点C在圆M上，故联立方程组运用MATLAB解方程，求出切点的坐标, MATLAB程序见附录6。 （2） 第二种类型的切点图17两圆连线与公切线平行如图17，设切点,圆心,圆心()，半径为,求切点的坐标。解法如下：直线的斜率为，的直线方程为，
