《行走机器人避障问题》由会员分享，可在线阅读，更多相关《行走机器人避障问题（21页珍藏版）》请在金锄头文库上搜索。
1、机器人行走问题摘要本文研究了机器人避障最短路径的问题。主要研究了在一个区域中存在四个 障碍物，由出发点到达目标点以及由出发点经过途中的若干目标点到达最终目标 点的两种情形。我们通过证明具有圆形限定区域的最短路径是由两部分组成的： 一部分是平面上的自然最短路径（即直线段），另一部分是限定区域的部分边界， 这两部分是相切的，互相连接的。依据这个结果，我们可以认为最短路径一定是 由线和圆弧做组成，因此我们建立了线圆结构，这样无论路径多么复杂，我们都 可以将路径划分为若干个这种线圆结构来求解。对于途中经过节点的再到达目标 点的状况，我们采用了两种方案，一种是在拐点和节点都采用最小转弯半径的形 式，另一
2、种是适当扩大拐点处的转弯半径，使得机器人能够沿直线通过途中的目 标点。然后建立了最优化模型对两种方案分别进行求解。问题一，我们很容易分解成线圆结构来求解，然后把可能路径的最短路径采 用穷举法列举出来，最终得出最短路径：R TA最短路径为：70.5076R TB最短路径为：107.9587R TC 最短路径为： 102.0514问题二，我们方案都进行优化，求得最终结果：第一种方案最短路径为： 156.471第二种方案最短路径为： 157.752关键词最短路径 最优化模型 避障路径 解析几何一 、问题重述下图是一个100X80的平面场景图，在R （0, 0）点处有一个机器人，机器 人只能在该100
3、X80的范围内活动，图中四个矩形区域是机器人不能与之发生碰 撞的障碍物，障碍物的数学描述分别为 B1（20， 40；5， 10）、B2（30， 30；10， 15）、B3（70， 50；15， 5）、B4（85， 15；5， 10），其中 B1（20， 40；5， 10） 表示一个矩形障碍物，其中心坐标为（20， 40）， 5 表示从中心沿横轴方向左右 各 5 个单位，即矩形沿横轴方向长 5X2=10 个单位， 10 表示从中心沿纵轴方向 上下各10个单位，即矩形沿纵轴方向长10X2=20个单位，所以，障碍物B1的 中心在（20， 40 ） ，大小为1 0 X 2 0个单位的矩形，其它三个障碍
4、物的描述完全类 似。1i e11(20/0;5,1C）B(75,60)53(70,.50;15,5)34(857 5;5,10)在平面场景中、障碍物外指定一点为机器人要到达的目标点（要求目标点与 障碍物的距离至少超过1个单位），为此，须要确定机器人的最优行走路线 由直线段和圆弧线段组成的光滑曲线，其中圆弧线段是机器人转弯路线，机器人 不能折线转弯，转弯路径是与直线相切的一圆形曲线段，也可以是两个或多个相 切的圆弧曲线段组成，但每个圆形路线的半径都必须大于某个最小转弯半径，假 设为 1 个单位。另外，为了不与障碍物发生碰撞，要求机器人行走线路与障碍物 间的最短距离为 1 个单位，越远越安全，否则
5、将发生碰撞，若碰撞发生，则机器 人无法到达目标点，行走失败。请回答如下问题：1. 场景图中有三个目标点 A（50， 40）、 B（75， 60）、 C（95， 20），请用数学建 模的方法给出机器人从R （0, 0）出发安全到达每个目标点的最短路线。2. 求机器人从R （0，0）出发，依次安全通过A、B到达C的最短路线。二、问题分析1、问题一中要求求定点R （0,0）按照一定的行走规则绕过障碍物到达目标点的最短路径，我们先可以包络线画出机器人行走的危险区域，这样的话，拐 角处就是一个半径为1的四分之一圆弧，那么然后采用拉绳子的方法寻找可 能的最短路径（比如求R和A之间的最短路径，我们就可以连接
6、R和A之间 的一段绳子，以拐角处的圆弧为支撑拉紧，那么这段绳子的长度便是 R 到 A 的一条可能的最短路径），然后采用穷举法列出 R 到每个目标点的可能路径的 最短路径，然后比较其大小便可得出 R 到目标点的最短路径。2、问题二中要求求定点 R（0，0）经过中间的若干点按照一定的规则绕过障碍物到达目标点，这使我们考虑就不仅仅是经过障碍物拐点的问题，也应该考 虑经过路径中的目标点处转弯的问题，这时简单的线圆结构就不能解决这种 问题，我们在拐点及途中目标点处都采用最小转弯半径的形式，也可以适当的变换拐点处的拐弯半径，使机器人能够沿直线通过途中的目标点，然后建立优化模型对这两种方案分别进行优化，最终
7、求得最短路径。三、模型假设1、假设障碍物全是矩形。2、假设机器人能够抽象成点来处理。四、符号说明符号符号说明L路径的总长度di第i段切线的长度lj第j段圆弧的长度r转弯半径k障碍物上的任意点与行走路径之间的最短距离五、模型的建立5.1先来证明一个猜想：猜想一：具有圆形限定区域的最短路径是由两部分组成的：一部分是平面上的自然最短路径（即直线段），另一部分是限定区域的部分边界，这两部分是相切的，互相连接的。（即问题分析中的拉绳子拉到最紧时的状况）证明：假设在平面中有A (a, 0)和B (-a, 0)两点，中间有一个半圆形的 障碍物，证明从A到B的最路径为A兰B。平面上连接两点最短的路径是通过这两
8、点的直线段,但是连接两点的线段于障碍 物相交，所以设法尝试折线路径。在y轴上取一点C(0, y)，若y适当大，则 折线ACB与障碍物不相交，折线ACB的长度为：IACB 1= 2pa2+y2显然I ACB I随着y的减小而减小，减小y得y t y，即C T C，使得AC与CB与1 1 1 1障碍物相切，切点分别为E和F,显然ACB是这种折线路径中最短的。由于满足10-的角满足:心二:,所以易知弧度EF小于ECF的长，即兰E1匚,从而2 1 _AE + -+FB ACB ,记线段AE、弧度EF、线段FB为AEFB,那么AEFB比任何折线 1路径都短。下面在考察一条不穿过障碍物的任何一条路径，设其
9、分别于OE和OF的延长线交与P、Q两点，记A和P之间的路径长度为|AP|,又由AE丄EO, 所以|AP|AE,从而JAE,同理可得乂BF。再来比较PQ之间路径长度亍;和圆弧EF的长度的大小。若PQ之间的路径可有极坐标方程：二:T，则有:：可得:丁= - 一 - ?-兰3亦即路径APQB的长度超过路径AEFB的长度。以上证明足以说明了 AEFB 是满足条件A到B的最短路径。5.2 模型准备一有了4.1中的定理，我们就可以这样认为，起点到目标点无论中间障碍物有 多少，最短路径都应该是若干个线圆结构所组成。在本题中存在障碍物的状况， 且障碍物在拐点处的危险区域是一个半径为 1 的圆弧，所以结合定理一
10、，我们易 知，求两点之间的最短路径中的转弯半径我们应该按照最小的转弯半径来算才能 达到最优。线圆结构 5.211）如上图，设A （:二）为起点，B （：二）为目标点，C （二/：）和D（二_，二）分别为机器人经过拐点分别于隔离危险线拐角小圆弧的切点，圆心为O（：/：），圆的半径为r，AB的长度为a，AO的长度为b，BO的长度为c，角度ZAOB =cc, ZAOCZBOD 才，ZCOD =Q .求 ACHE 的长度，设为 L. 解法如下： 如上图可得有以下关系a = J(x - x )2 + (y - y )2y2121b = d (x - x )2 + (y - y )2v 5151c = J
11、(x - x )2 + (y - y )2I 5252在AAOB中:b 2 + c 2 - a 2、 a = arccos()2bc在 RtAAOC :P = arccos -b在 Rt AAOC 中：ry = arccos -c 所以：0 = 2兀-a - P -y从而可得：L =、；b2 r 2 + pc 2 r 2 + r02）而对于下图两种情况我们不能直接采用线圆的结构来解决，需要做简单的变 换。情况一：BFE0MDCA线圆结构 5.22我们假设两圆心坐标分别为O(x , y )和O(x , y ),半径均为r, M点坐标为1 1 2 2(x ,y )，那么我们很容易可以求得:33y3
12、这样我们就可以利用1)中的方法，先求A到M,再求M到B这样分两段就可 以求解。同理如果有更多的转弯，我们同样可以按照此种方法分解。情况二：线圆结构 5.23这里我们依然设圆心坐标分别为O (x , y )和O(x, y )，半径均为r,这样我1 1 2 2们可以得到：“ y - yK = T 100f x 一 x21那么OO,直线方程为：y 二 K (xx) + yOO11因为公切线DE与OO平行，那么 DE 的直线方程可以表示为： y 二 K (x x ) + y + C0O11其中：C = r. ：1 + K200f那么把公切线的方程于圆的方程联立，渴可以求得切点D和E的坐标。这样用D 和
13、 E 任意一点作为分割点都可以将上图分割成两个 4.21 所示的线圆结构，这样 就可以对其进行求解。同理多个这样的转弯时，用同样的方法可以进行分割。5.3 模型准备二一、对于从起点经过若干点然后再到达目标点的状况，因为不能走折线路 径，我们就必须考虑在经过路径中的一个目标点时转弯的状况。为了研究这个问 题的方便，我们先来证明一个猜想：猜想二:如果一个圆环可以绕着环上一个定点转动，那么过圆环外两定点连 接一根绳子，并以该圆环为支撑拉紧绳子，达到平衡状态时，圆心与该顶点以 及两条切线的延长线的交点共线。图 5.31证明猜想：如图4.31所示，E点就是圆环上的一个顶点，A=B就是拉紧的绳子，O就2
14、是切线AC和BD的延长线的交点，证明O、E、O三点共线。12 我们可以用力学的知识进行证明，因为是拉紧的绳子，所以两边的绳子拉力 相等，设为F，它们的合力设为F，定点对圆环的作用力设为F。01那么由几何学的知识我们可以知道F一定与OO共线，而又由力的平衡条0 1 2件可知：F =- F01即OO与EO共线。1 2 2综上所述O、E和O三点一定共线。12二、有了以上这个定理我们可以建立以下模型：如图4.32，要求求出机器人从A绕过障碍物经过M点到达目标点B的最短 路径，我们采用以下方法：用一根钉子使一个圆环定在M点，使这个圆环能够绕M点转动。然后连接A 和 B 的绳子并以这些转弯处的圆弧为支撑(
15、这里转弯处圆弧的半径均按照最小转 弯半径来计算)，拉紧绳子，那么绳子的长度就是A到B的最短距离。我们可以 把路径图抽象为以下的几何图形。下面我们对这段路径求解：如图，A(x ,y )是起点，B(x ,y )是终点，O (x ,y )和O (x ,y )是两个固定1 1 2 2 1 3 3 3 4 4的圆，O是一个可以绕M(p, q)点转动的圆环，三个圆的半径均为r，C、D、E、2F、G、H 均为切点。a、b、c、e，f 分别是 AO、O O、AO、AO、OO 的长1 1 2 2 3 2 3度。 A、 B、 O 、 O 均是已知点， O 是未知点。那么最短路径就可以表示为：1 3 2L=|AC| + =+|DE|+三+|FG| + ：P+|HB|因为O点的坐
