《机器人避障问题——国家一等奖论文 经典》由会员分享，可在线阅读，更多相关《机器人避障问题——国家一等奖论文 经典（38页珍藏版）》请在金锄头文库上搜索。
1、1D D 题题 机器人避障问题机器人避障问题摘 要本文综合运用分析法、图论方法、非线性规划方法，讨论了机器人避障最短路径和最短时间路径求解问题。针对问题一，首先，通过分析，建立了靠近障碍物顶点处转弯得到的路径最短、转弯时圆弧的半径最小时和转弯圆弧的圆心为障碍物的顶点时路径最短、转弯在中间目标点附近时，中间目标点位于弧段中点有最短路径的三个原理，基于三个原理，其次对模型进行变换，对障碍物进行加工，扩充为符合条件的新的区域并在转弯处圆角化构成障碍图，并通过扩充的跨立实验，得到切线和圆弧是否在可避障区的算法，第三，计算起点、中间目标点和最终目标点和各圆弧及圆弧之间的所有可避障切线和圆弧路径，最后给这
2、些定点赋一个等于切线长度或弧度的权值构成一个网络图，然后利用 Dijkstra 算法求出了 O-A、O-B，O-C 的最短路径为 O-A：471.0372 个单位，O-B：853.7001 个单位，O-C：1086.0677 个单位；对于需要经中间目标点的路径，可运用启发规则分别以相邻的目标点作为起点和终点计算，确定路径的大致情况，在进一步调整可得到 O-A-B-C-O 的最短路径为 2748.699 个单位。针对问题二，主要研究的是由出发点到达目标点 A 点的最短时间路径，我们在第一问的基础上考虑路径尽可能短且圆弧转弯时的圆弧尽量靠近障碍物的顶点，即确定了圆弧半径最小时的圆弧内切于要确定的圆
3、弧时存在最小时间路径，建立以总时间最短为目标函数，采用非线性规划模型通过 Matlab 编程求解出最短时间路径为最短时间路程为 472.4822 个单位，其中圆弧的圆心坐标为，最短时间为 94.3332 秒。圆弧两切点的坐标分别为(81.430,209.41)（70.88,212.92） 、 （77.66,219.87） 。关键字： Dijkstra 算法 跨立实验 分析法 非线性规划模型 2一.问题的重述图是一个800800的平面场景图，在原点O(0, 0)点处有一个机器人，它只 能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发 生碰撞的障碍物，障碍物的数学描述如下表：
4、编号障碍物名 称左下顶点坐 标其它特性描述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)上顶点坐标(150, 435)，右下顶点坐标 (235, 300)7长方形(0, 470)长220，宽608平行四边 形(150, 600)底边长90，左上顶点坐标(180, 680)9长方形(370, 680)长60，宽12010正方形(5
5、40, 600)边长13011正方形(640, 520)边长8012长方形(500, 140)长300，宽60在图1的平面场景中，障碍物外指定一点为机器人要到达的目标点(要求目 标点与障碍物的距离至少超过10个单位)。规定机器人的行走路径由直线段和圆 弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直 线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每 个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行3走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则 机器人无法完成行走。机器人直线行走的最大速度为个单位/秒。机器人
6、转弯时，最大转弯50v速度为，其中是转弯半径。如果超过该速度，机器人将20 10 0.1( ) 1 evvv 发生侧翻，无法完成行走。请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中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的最短时间路径。注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标 以及机器人行走的总距离和总时间。4图 800800平面场景图二.问题的分析
7、本问题的难点在于机器人要到达指定的目标点需要满足以下两个约束条件：1. 机器人的行走路径由直线段和圆弧组成，不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，且每个圆弧的半径最小为10个单位；2. 要求机器人行走线路与障碍物间的最近距离为10个单位。因此，我们在建立模型求解机器人到达目标点的最短路径时需优先考虑这 两个约束条件。首先我们可以根据约束条件将机器人行走的危险区域进行扩张，即所有的 障碍物都向外扩张了10个单位。机器人所走的路径都是直线与圆弧的构成，故 存在线和弧、弧与弧之间的切线，可以考虑在所有代表出发点与其它圆弧之间 切线的顶点与源点连成一条边，权值均为0，同理在所有代表目标
8、点到其它圆弧 切线的顶点与终点连成一条边，权值均为0，这样题目就转化成了求源点到达终 点之间的最短路径问题了。 对于问题二，要求最短时间路径，则要考虑的是要以最大速度行走。直线 行走时就是最大速度，但在转弯圆弧处因为转弯半径越小，行走的速度就越慢， 则需在第一问的前提下增大圆弧的半径，则圆弧的转弯半径和圆心都不确定， 通过建立模型确定O-A之间的转弯时圆弧的半径和圆心。三、模型的基本假设根据对该问题的分析，本文对所建立的模型提出以下基本假设：1.机器人的性能足够好，能准确地沿圆弧转弯2.机器人行走过程中不会意外停止3.图中所给数据障碍物都是真实的4.机器人能够抽象成点来处理四、符号说明指每段路
9、径的长度:il：机器人直线行走时的最大速度0v：机器人的最大转弯速度v5：每段路径所用的时间it五、模型的建立与求解5.1 模型的准备 模型的准备一首先给出以下三个前提及其证明：1.靠近障碍物顶点处转弯得到的路径最短如图1所示：图 1设A为起点，B为终点，矩形的阴影部分是障碍区，C为障碍物的顶点，D为 障碍物外任意一点，连接AD，BD，AC，BC延长交AD于E点，因为在三角形中两边 之和大于第三边，所以有：BD+DEBE；BE=BC+CE；AE+CEAC；AD=AE+DE；两个不等式相加，得：AE+DE+AE+CEBE+AC；即：BD+ADAC+BC.于是，得证由A到B在顶点C处转弯时为最短路
10、径。2.转弯时圆弧的半径最小时路径最短和转弯圆弧的圆心为障碍物的顶点时 路径最短要证明机器人转弯时圆弧的半径最小时路径最短，则可以把P到A的路径比 拟成一条弹性绳，由于路径要绕过障碍物，故要拉长弹性绳以绕过障碍物，由6于机器人转弯时只能是走圆弧路径且有圆弧半径约束，即可以在障碍物的顶点处加入圆环，将其圆心固定在顶点处，由于弹性绳的弹性势能和伸长量pE存在如下能量关系：，故弹性绳弹性势能最小时伸长量最小，此x21 2pEk x时正是路径最短的情况：如图 2 所示：图 2 根据最小势能原理可知，当弹性体平衡时，系统势能最小。即弹性体在自 由条件下，有由高势能向低势能转化的趋势。现在将圆环看成也有弹
11、性，在如图所示的条件下为初始状态。圆环受力为F，此时圆环有缩小的趋势，随着圆环 的缩小系统趋于平衡，弹性绳有最小势能。由能量守恒也可以说明，弹性绳的 弹性势能转化为弹性圆环的弹性势能，于是弹性绳的弹性势能减小。因此，随着圆环的半径的减小，弹性绳的势能减小，即最短路径变短。所 以转弯时圆弧的半径最小时路径最短。转弯圆弧的圆心为障碍物的顶点时路径 最短。3.转弯在中间目标点附近时，中间目标点位于弧段中点有最短路径当机器人从O点出发不能直接到达另一目标点，而需经过中间目标点A时， 则必须在A点转弯处形成一个圆弧，中间目标点位于弧段中点时且半径最小时有 最短路径，下面给予证明：由上述2的证明可仍然采用
12、此证法，设从两转向处引出一根弹性绳，要使其经过A 点，如图所示，在其自然伸长的前提下，必 定会在A 点出弯折。由于机器人有转弯时圆弧的半径最小时路径最短，从两转 向处引出一根弹性绳，要使其经过A 点，如图所示，在其自然伸长的前提下，7必定会在A 点出弯折。由于机器人有最小转弯半径约束，故在A 处加一最小转 弯半经的圆，即r=10个单位，使其受力平衡时，即为路径的最优解。根据以上证明作出如下图形(图3)：图 3作法：过 A 点分别作圆上 M,N 的切线，作的角平分线，在 上距离MANl A 点 10 个单位处选取一点 O，以 O 为圆心，10 个单位为半径，作圆 O，再过 M,N 分别作圆 O
13、的切线，即为路径。模型准备二：切线的剔除：基于上述准备一的三个前提条件和题中给出的两约束条件即（1）机器人的 行走路径由直线段和圆弧组成，不能折线转弯，转弯路径由与直线路径相切的 一段圆弧组成，且每个圆弧的半径最小为10个单位（2）要求机器人行走线路与 障碍物间的最近距离为10个单位。故存在一些不符合要求的切线，要将这些切 线剔除，可做示意图如下：8图 4如图所示，阴影部分为障碍物，用圆来代表弧，AC、BC、AD、BD、EH、FG 分别如图示的切线，由于AD、BC、BD、FG、EH经过障碍物，所以要剔除，AC为 符合要求切线。(图中应该剔除的切线用虚线表示)。模型准备三由上准备一和准备三可知，
14、对于机器人转弯的路径按照一个圆弧、两个圆 弧、三个圆弧等多个圆弧枚举出转弯的情况：转过了一个圆弧,如图5:图 59如图，设()，O()，()，、的坐标分别为和B11,x y22,xyA33,xyEF44,xy，, 则: ,55,xyBOaBAbOAccosrBOFara，222 cos2acbBOAaraccosrAOEarc又=，可知：2EOFBOFBOAAOE，22 2121()()axxyy，22 3131()()bxxyy，22 3232()()cxxyy故 B 到 A 的路径长度为： 。EAEFBFLAB)其中，rEF)22raBF22rcEA即。2222rcrarLAB并且利用相切
15、的关系可以得出下面两个方程： 2222 515122 5252()()()()arxxyyxxyyr 可以解出切点，同理可以解出切点。55(,)F xy44(,)E xy转过了两个圆弧，转过了两个圆弧，如图 6：情况一：10图 6假设两圆心坐标分别为和,半径均为 ，O 点坐标为11( ,)O x y22(,)O xyr，则容易求得:33(,)xy12 312 3,2,2xxxyyy这样我们就可以利用只有一个圆弧中的方法，先求A到O，再求O到B，于是 分两段就可以求解。同理如果有更多的转弯，同样可按照此种方法分解。情况二：图 711设圆心坐标分别为和,半径均为 ，),(22yxO),(33yxOr),(),(4411yxQyxP的长为,长为,长为 ，长为，长为 ；，POaOObPOcQOdQOe 1POO，；由这些点2POA 3QOO 4QO D1AOB2COD的几何关系可以得到：22 2121()() ,axxyy22 3232()() ,bxxyy22 3131()() ,cxxyy22 4242()() ,dxxyy22 4343()() .exxyy其中：，2221cos2abcarab2cosrara2223arcos2bed be， ，.4cosrare1123 22343 2则，22PAar1ABr) ) BCb2CDr) )2
