《论文机器人避障问题》由会员分享，可在线阅读，更多相关《论文机器人避障问题（25页珍藏版）》请在金锄头文库上搜索。
1、机器人避障问题【摘要】本文主要是对机器人在一个平面区域内的通过不同障碍物到指定目标点进行研究，首先通过机器人与障碍物的最小安全距离对不同障碍物的禁区进行了划分见图1，把障碍物划分为有顶点和无顶点两大类。然后证明了机器人在障碍物顶点处转弯路径最优，转弯半径最小路径最优，转弯圆心在障碍物顶点处（圆行障碍物在圆心）路径最优。问题一对于起点和目标点的的路线先用拉绳子的方法确定了可能的最短路线，然后用穷举法确定最佳路径。机器人的行进又分单目标点和多目标点两种情况。针对单目标点问题，先对只进行一次转弯的过程建立了基本线圆组合结构的解法即模型一。然后对多次转弯问题中的直线路径与圆弧路径的不同的位置关系推导出
2、了计算模型即模型二。对O-A是基本的线圆组合，直接用模型一求解得到0-A的最短路径长为471.0372个单位，所用时间为96.0178秒具体情况见文中表1。对O-B和O-C都是先用模型二对路线进行基本分割，然后用模型一进行求解得到O-B最短路径长为853.7127个单位，所用总时间为179.0851秒，具体见表2。得到O-C最短路径长为1087.6个单位，所用时间为221.9秒，具体见表3。针对多目标点问题，由于机器人不能直线转向，所以在经过目标点时，应该提前转向，且中间目标点应该在转弯弧上。因此先建立优化模型（模型三）对进行中间目标点处转弯圆弧圆心搜索求解。求出中间目标点转弯圆心后，用把中间
3、目标点的圆心看做“障碍物”的办法把问题转化为单目标点问题。然后利用模型二和模型一进行求解，解得O-A-B-C-O的最短路径长为2812.52个单位，所用时间为585.6712秒，具体见附表1。对于问题二，在问题一求出的最短路的基础上，根据转弯半径和速度的关系，在问题一求出的最短路径的模型的基础上，进行路线优化，建立以最短时间为目标的非线性规划模型，求解得最短时间为94.22825秒，转弯半径为12.9886个单位，转弯圆心坐标为（82.1414，207.1387），具体结果见表5。关键词：基本线圆组合 拉绳子法 穷举法 非线性规划 中间目标点转弯圆心1问题重述附图1是一个800800的平面场景
4、图，在原点O(0, 0)点处有一个机器人，它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述如下表：编号障碍物名称左下顶点坐标其它特性描述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)长22
5、0，宽608平行四边形(150, 600)底边长90，左上顶点坐标(180, 680)9长方形(370, 680)长60，宽12010正方形(540, 600)边长13011正方形(640, 520)边长8012长方形(500, 140)长300，宽60在图1的平面场景中，障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走
6、线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。机器人直线行走的最大速度为个单位/秒。机器人转弯时，最大转弯速度为，其中是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中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的最短时间路径。注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的
7、圆心坐标以及机器人行走的总距离和总时间。2问题分析 本问题主要是对机器人在一个平面区域内的通过不同障碍物到指定目标点进行研究，首先通过观察发现障碍物不同，因此我们先要对机器人通过不同的障碍物的情况进行讨论。在行进过程中转弯位置，转弯的半径，转弯圆心的不同都会影响路径的优劣。因此我们要先确定最佳转弯位置、半径和转弯圆心。对于问题一，分单目标点和多目标点两种情况。针对单目标点问题，从已知点到指定点有多条路径可以选择，可以先用拉绳子的办法确定可能的最短路线，然后用穷举法确定最短路径。由于机器人不能折线转弯，转弯路径由与直线路径相切的圆弧组成，因此可以把路径看成由多个基本线圆组合而成，然后在对基本线圆
8、结构建立求解模型。针对多目标点问题，不能简单的处理为求解每个两点之间的最短路径之和，因为机器人不能直线转向，所以在经过目标点时，应该考虑提前转向，且中间目标点应该在转弯弧上。因此对于中间目标点处转弯圆弧圆心的确定可以建立优化模型进行搜索求解。求出中间目标点转弯圆心后可以把中间目标点的圆心看做“障碍物”进行研究，这样问题就转化为了单目标点问题。对于问题二，可以根据转弯半径和速度的关系，在问题一求出的最短路径的模型的基础上，进行路线优化，即建立以最短时间为目标的非线性规划模型，进行求解最短时间。3模型假设为了简化计算，给出如下模型合理性的假设：【1】假设所有障碍物是固定不动的；【2】机器人性能足够
9、好，能准确地沿圆弧转弯；【3】假设机器人在初始时的速度为5个单位每秒；【4】假设机器人在直线切入弧线时的速度是瞬间变化完成的；【5】机器人行走过程中不会意外停止；【6】忽略影响机器人行走非最小转弯半径以及最小安全距离因素。 4符号说明为了简化对问题的分析和对数字的处理，做出如下符号规定：第条直线路径长度第条弧线路径长度最短路径总长度最短路径所用时间机器人直线行进速度机器人转弯速度5模型的建立与求解5.1最短路径模型（问题一）从已知点到指定点有多条路径可以选择，可以先用拉绳子的办法确定可能的最短路线，然后用穷举法确定最短路径。在行进过程中转弯位置，转弯的半径，转弯圆心的不同都会影响路径的优劣。因
10、此我们要先确定最佳转弯位置、半径和转弯圆心。本问题中对于路径的求解分为单目标路径和多目标路径两种，因此在本问题中我们分开讨论。5.1.1单目标点模型（只有起点和终点） 由于机器人不能折线转弯，转弯路径由与直线路径相切的圆弧组成，因此对于本问题可以把路径看成由多个基本线圆组合而成。5.1.1.1相关推论及证明 把机器人的行进路线看成一根有弹性的绳子，根据实际情况我们推论：禁区顶点处变向路径最小，转弯半径最小路径最短，转弯弧圆心在顶点路径最短。【1】禁区划分 由于机器人行进过程中与障碍物有最小距离的限制，因此我们先画出包络障碍物的禁区，对于有圆形障碍物来说，禁区还是一个圆，对于有顶点的障碍物来说禁
11、区拐角处为一个圆弧，具体如图1：图1 禁区示意图【2】障碍物有顶点（1）禁区顶点变向路径最小如下图2所示，机器人从指定的A点到C点，需要进行变向，从图形可以看出来，在禁区边缘变向总路径会最小，下面我们进行证明：图2 禁区顶点处变向图假设D点为禁区顶点，先不考虑转弯半径等因素，其中B为禁区外任意一点，AD变延长线交BC于E点。由三角形的任意两边之和大于第三边可以得到：两式相加得到：化简得到：即，由A点到B点，选择在顶点D处转向，总路径最短。推论得证。（2）转弯半径最小路径最短机器人从A点到B点需要绕过禁区，在禁区顶点附近（前面已证）转弯。选择的转弯半径越小，得到的路径越短。下面从物理学的角度进行
12、证明：如下图3所示，将A到B的路径看做一条可伸缩的绳子。假设其两点相连时，绳子自然伸长。如线段AB。由于机器人要绕过禁区，因此拉长绳子绕过禁区，又因为机器人有最小转弯半径为10，禁区直径也为10，因此可以把绳子直接绕过禁区边缘。由于绳子的弹性势能与伸长量的关系为：因此绳子伸长量最小时，路径最短。图3 机器人过障碍转弯半径根据最小势能原可知，当弹性体平衡时，系统势能最小。即弹性体在自由条件下，有由高势能向低势能转化的趋势。现在将圆环看成也有弹性，在如图所示的条件下为初始状态。圆环受力如图所示，此时圆环有缩小的趋势，随着圆环的缩小系统趋于平衡，弹性绳有最小势能。由能量守恒也可以说明，绳子的弹性势能
13、转化为弹性圆环的弹性势能，于是弹性绳的弹性势能减小。因此，随着圆环的半径的减小，绳子的势能减小，即最短路径变短。所以最小转弯半径最小路径最短得证。（3）转弯弧圆心在顶点路径最短 机器人在禁区顶点附近转弯时，转弯弧的圆心在顶点上，路径最短。下面进行证明： 如下图4所示，圆O和圆O均过最远点D它们的半径分别为R和R。其中圆O的圆心在垂线上。分别为过A、B点向圆O和O所引切线段和所夹圆弧长度。则需证明：因为两圆圆心不同在过点 D 所引的垂线上，且两圆交于点 D，因此它们只能有两种关系相交或相切。若两圆相切，由几何定理知切点、圆心 O、圆心 O三点共线。因点 D 和圆心O均在过D所作直线AB的垂线上，
14、圆心O在垂线外，故两圆不会相切，只能相交。要过点D则必有圆O上点到直线AB的最大距离大于圆 O上点到直线AB的最大距离。运用上文已证得的结论可得到：因此推论得证。图4 机器人过障碍转弯圆心位置（4）结论分析 结合（1）（2）（3）证明得到结论：机器人过有顶点的障碍物时，沿以顶点为圆心，最小转弯半径为半径的圆弧转弯路径最短，在本题中机器人的最小转弯半径和机器人与障碍物的最小安全距离相等。因此对于本题来说，机器人沿禁区边缘转弯路径最短。【3】障碍物为圆的情况在前面我们已经证明了障碍物有顶点的情况下，机器人过禁区时沿禁区边缘圆弧转弯路径最小。下面就机器人通过圆形障碍物的情况是否符合以上结论进行讨论。
15、如图5，分别是机器人通过圆形禁区的3种情况，其中a图为机器人人沿禁区边缘进行转弯的。b图为机器人沿以圆形障碍物边上一点为圆形，最小转弯半径为转弯半径的弧转弯图，c图为机器人沿一个刚好绕过禁区的圆弧转弯的情况。图5 机器人通过圆形障碍物由以上用弹性绳的方法进行证明发现，b图转弯路径最小，但是经过了禁区，因此不可行，另外两种方案a图路径明显要比c图小。因此机器人过禁区时沿禁区边缘圆弧转弯路径最小得结论同样适用于障碍物位圆的情况。转弯半径为： （其中为障碍物半径，为机器人距离障碍物的最小安全距离）5.1.1.2模型的建立经过以上证明得到，起点到目标点中间不管有多少障碍物，最短路径都是由若干个相切的直线和圆弧构成的，前面已经证明机器人经过所有障碍物时，禁区边缘转弯路径最短，因此转弯圆弧半径为危险区域半径。所以在下面模型中经过障碍物转弯时，都以障碍物顶点为转弯弧圆心，最小转弯半径为转弯半径。【1】途中转弯一次的模型（模型一）如图6所示，已知机器人要从起点A（）点出发绕过障碍物到终点B。途中从以障碍物顶点D（）为圆
