《机器人避障问题讲义》由会员分享，可在线阅读，更多相关《机器人避障问题讲义（24页珍藏版）》请在金锄头文库上搜索。
1、机器人避障问题摘要本文研究讨论的是机器人避过障碍到达任意目标点的最短路径和最短时间路径的问题。从该区域的一点到另一点避过该场景的12个障碍物，且不能折线转弯，那么机器人的行走路径只能由直线段和圆弧组成，所以机器人所走的路径的距离多个圆弧的周长和直线段长度的和。而对于时间最短路径的求解则保证所走的路径尽量短的情况下使得机器人行走的速度尽量大。因此从一点到另一点路线上的选择尤为重要。 本文首先提出了机器人行走的基本规则，并将路障结构进行了分析，确定了最短路径的基本结构线圆结构。通过将机器人的行走路线分割为基本结构，从而建立了区域上任意两点最短路径的数学模型，并用于计算地图上定点OA、OB、OC最短
2、路径；通过考虑指定点的弧线化问题，建立了经过指定点最短路径模型，并用于计算地图上OABCO的最短路径；在建立转弯速度和转弯半径之间的函数关系基础上，本文建立了任意两点时间最短路径模型，并计算了OA的最短时间和最短时间路径。由于障碍物较多，用穷举法显然不合适，所以我们将地图简化后，用计算最短路径的经典算法Froyd法粗略的计算出起点到终点可能的最短路径，然后上面建立的最短路径模型进行详细的求解，大大的简化了计算量。关键词 最短路径模型，最短时间路径模型，Froyd算法，解析几何，避障路径一、问题重述与分析1.1 问题重述图1是一个800800的平面场景图，在原点O(0, 0)点处有一个机器人，它
3、只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，图1在图1的平面场景中，障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。本文要求建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学
4、模型。并计算：(1) 机器人从O(0, 0)出发，OA、OB、OC和OABCO的最短路径。(2) 机器人从O(0, 0)出发，到达A的最短时间路径。1.2问题分析首先我们先找出机器人行走过程中的可行区域，即找出距离每一个障碍物危险区的边界，如下图所示：图2在图2中，黑色的线段为障碍物的边界，为了不与障碍物发生碰撞，要求机器人行走线路与障碍物间的最近距离为10个单位，即图中的红色的线段和弧线。1.2.1 机器人行走的基本原则由题意知，机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。因此，我们首先建立机器人的行走路径基本原则：（1）在无障碍的情况下，机器人只能直线行走，不会进行转弯。
5、考虑到所求问题为路径最短问题，一旦转弯路径就会变长，所以只有遇到障碍的情况下机器人才会转弯。（2）根据文献1中的定理一，在求两点之间最短距离时，转弯处的转弯半径以最小的半径来算得到圆弧长最短，机器人所走的路径才能达到最短。1.2.2 问题分析（1）区域中一点到达另一点的避障最短路径模型。根据机器人行走的基本原则以及题目规定机器人的路径是由直线段和圆弧组成，所以机器人行走的路径可以简化成以下两种几何图形：情况一：只有一个障碍（如下图所示）图3 由文献1知，点A绕障碍物到点B的最短路径为点A到B拉紧的绳子的长度，即图3中所示A到B的最短距离为，其中是以为圆心，10为半径的圆弧。情况二：多个障碍（如
6、下图所示） 图4经过合理的划分，多个障碍的问题可以归结为一个障碍的情况，因此本文在进行最短路径计算时，图4所示的线圆结构为计算的基本结构。（2）机器人在行走避障的同时，经过指定点的最短路径模型。在计算经过指定点A,B,C,然后回到起点完成的最短路径问题，我们可以先分别求解出的最短路径，由于机器人不能进行折线转弯，因此需要对必经的定点A,B,C作相应的弧线处理，进而求出所需要的最短路径。（3）区域中一点到达另一点的时间最短路径模型。由题知，机器人直线行走的最大速度为个单位/秒。机器人转弯时，最大转弯速度为，其中是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。可以看出，机器人在弧线部分
7、行走的时间受到转弯半径的影响，因此我们可以通过建立行走时间和转弯半径的函数关系，来研究最短时间问题。二、模型假设和符号说明2.1 模型假设：（1） 假设机器人是一个点（2） 假设机器人可以瞬间加速到想要的速度，无缓冲过程2.2 符号说明 符号符号说明L路径的总长度转弯圆弧半径行走时间三、最短路径模型的建立3.1 点到点的最短路径模型3.1.1模型分析首先我们建立1.2.2节提到的基本线圆结构的最短路径模型。如图5所示的三角形障碍物，障碍物外层的切线与圆弧为进入危险区的界限，设机器人的起点为，终点，三角形左下顶点即圆心，半径，其中A,B,O,均已知。设机器人经过拐点隔离危险线拐角小圆弧的切点分别
8、为M、N，图5则点A到B的路径距离为：在直角三角形AMO中，在直角三角形BON中，在、则，由此得圆弧从而得到路径距离L。对于一个障碍物，我们可以穷举出所有从点A到B的路径，并计算出距离：则一个障碍物的最短路径模型为：（*）对于本文的地图情况分析：（1）由1.2.2节的分析可知，如图4所示，地图中的任何路线都可以分解为基本线圆结构，若点A与点B跨越多个障碍时，只需要将多障碍拆分成基本线圆结构即可。具体的方法是：以两圆弧所在圆的公切线的中点为划分点。（2） 由于本题障碍物较多，如果将该区域中的一点到另一点的所有路径用穷举法一一列出，然后再用上面建立的最短路径模型进行求解，计算量太大也不符合实际，所
9、以本文利用最短路径中的Froyd算法粗略的计算出起点到终点的可能最短路径，然后用建立的最短路径模型进行详细的求解。具体方法是：首先在地图上标记出障碍物顶点，如图6中所示。对所有的障碍物的顶点进行如图所示的命名，连接所有的顶点，连接后的线段凡是穿过障碍物全部舍弃，然后用Froyd算法进行编程算出任意两点避过障碍物的最短距离，然后在对顶点处的转弯处进行圆弧处理。3.1.2模型的建立根据上面的分析，我们建立求机器人在区域上一点A到另一点B的壁障最短路径的数学模型如下：（1）对计算区域进行简化，使用Froyd算法计算出从A到B的近似最短路径，找到最短路径经过的障碍顶点；（2）将路径拆分成基本线圆结构；
10、（3）利用（*）式所建立的模型进行计算。 图63.1.3模型应用与求解（1）的最短路径利用最短路径中的Froyd算法（程序见附录1）确定出两条可能的最短路线： 路线1： 路线2： 通过Mathematica7.0求解出的路径（程序见附录2）：路线一：=498.41路线二：=471.02所以的最短路径为=471.02，走完共用时96s。机器人的行走构成中的坐标：从O点行至（70.5，213.1），进入以（80，210）为圆心的弧线，于（76.6，219.4）出弧线，进入直线最终到达A（300，300）。（2）的最短路径利用最短路径中的Froyd算法（程序见附录1）确定出六条可能的最短路线: 路线
11、一： 路线二： 路线三： 路线四： 路线五： 路线六： 通过Mathematica7.0求解出的路径： 路线一： 路线二： 路线三： 路线四： 路线五： 路线六： 通过比较如所示路径最短，即，走完共用时179.1s。机器人的行走构成中的坐标：从O点（0，0）出发走直线到（55.9，301.6）进入圆心为（60，300）的圆弧，于（51.67，305.54）出圆弧进入直线，行于（141.67，440.54）进入圆心为（150，435）的圆弧，于（147.96，444，79）出圆弧进入直线，行于（222，460）进入圆心为（220，470）的圆弧，于（230，470）出圆弧进入直线，于（230，5
12、30）出直线，进入圆心为（220，530）的圆弧，于（225.49，538.35）出圆弧入直线，于（144.5，591.6）入圆心为（150，600）的圆弧，于（140.7，596.3）进直线最终到达B点（100，700）。（3）的最短路径利用最短路径中的Froyd算法（程序见附录1）确定出可能的最短路线，通过Mathematica7.0求解出的路径（程序见附录2）： 路线一： 路线二 路线三： 路线四： 路线五： 路线一： 路线二： 路线三： 路线四： 路线五： 通过比较如所示路径最短，即，走完共用时220.648s。机器人的行走构成中的坐标：从O点行至（232.1，50.2）进入以（230
13、，60）为圆心的弧线，于（238.8，55.2）出圆弧进入直线，行至（390.8，334.1），进入以（400，330）为圆心的弧线，于（398.1，339.8）出弧线走直线到（564.9，371.4），进入以（550，470）为圆心的弧线，于（606.4，393.2）出弧线进入直线走到（725.9，511.9），进入以（720，520）为圆心的弧线，于（730，520）出弧线，走直线至（730，600）进入以（720，600）为圆心的圆弧，至（727.7，606，4）出弧线直行至终点C（700，640）。3.2 经过指定点的最短路径模型3.2.1 模型分析当机器人从出发点出发需要经过一个或多
14、个定点再到达终点求最短路径，可以通过以下思想建立适当的路径结构模型。文献1指出，用一根钉子使一个圆环定在P点，使这个圆环能够绕P点转动。然后连接O和Z的绳子并以这些转弯处的圆弧为支撑（这里转弯处圆弧的半径均按照最小转弯半径来计算），拉紧绳子，那么绳子的长度就是O到Z的最短距离。把路径图简化成以下几何图形进行讨论：图7设：解法如下：在中：则机器人从的最短距离L就可以用所建立的路径最短模型来进行求解了。3.2.2 模型建立根据上面的分析，我们建立求机器人在区域上右A到B经指定点C的壁障最短路径的数学模型如下：（1）使用3.1节建立的点到点的最短路径模型，计算出从A到C的最短路径以及C到B的最短路径；（2）使用3.2.1节建立的模型求出经过点
