行走机器人避障问题[1]

《行走机器人避障问题[1]》由会员分享，可在线阅读，更多相关《行走机器人避障问题[1]（19页珍藏版）》请在金锄头文库上搜索。

1、一 、问题重述下图是一个 10080 的平面场景图，在 R（0，0）点处有一个机器人，机器人只能在该 10080 的范围内活动，图中四个矩形区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述分别为 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 个单位，即矩形沿横轴方向长 52=10 个单位，10表示从中心沿纵轴方向上下各 10 个单位，即矩形沿纵轴方向长 102=20 个单位，所以，障碍物

2、B1 的中心在（20，40） ，大小为 1020 个单位的矩形，其它三个障碍物的描述完全类似。在平面场景中、障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过 1 个单位） ，为此，须要确定机器人的最优行走路线由直线段和圆弧线段组成的光滑曲线，其中圆弧线段是机器人转弯路线，机器人不能折线转弯，转弯路径是与直线相切的一圆形曲线段，也可以是两个或多个相切的圆弧曲线段组成，但每个圆形路线的半径都必须大于某个最小转弯半径，假设为 1 个单位。另外，为了不与障碍物发生碰撞，要求机器人行走线路与障碍物间的最短距离为 1 个单位，越远越安全，否则将发生碰撞，若碰撞发生，则机器人无法到达

3、目标点，行走失败。请回答如下问题：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 之间的最短路径，我们就可以连接 R和 A 之间的一段绳子

4、，以拐角处的圆弧为支撑拉紧，那么这段绳子的长度便是 R 到 A 的一条可能的最短路径） ，然后采用穷举法列出 R 到每个目标点的可能路径的最短路径，然后比较其大小便可得出 R 到目标点的最短路径。2、问题二中要求求定点 R（0， 0）经过中间的若干点按照一定的规则绕过障碍物到达目标点，这使我们考虑就不仅仅是经过障碍物拐点的问题，也应该考虑经过路径中的目标点处转弯的问题，这时简单的线圆结构就不能解决这种问题，我们在拐点及途中目标点处都采用最小转弯半径的形式，也可以适当的变换拐点处的拐弯半径，使机器人能够沿直线通过途中的目标点，然后建立优化模型对这两种方案分别进行优化，最终求得最短路径。三、 模型

5、假设1、假设障碍物全是矩形。2、假设机器人能够抽象成点来处理。四、符号说明符号 符号说明L 路径的总长度id第 段切线的长度ijl第 段圆弧的长度jr转弯半径k障碍物上的任意点与行走路径之间的最短距离五、模型的建立5.1 先来证明一个猜想：猜想一：具有圆形限定区域的最短路径是由两部分组成的：一部分是平面上的自然最短路径（即直线段） ，另一部分是限定区域的部分边界，这两部分是相切的，互相连接的。 （即问题分析中的拉绳子拉到最紧时的状况）证明：假设在平面中有 A（a，0）和 B（-a，0）两点，中间有一个半圆形的障碍物，证明从 A 到 B 的最路径为 A B。平面上连接两点最短的路径是通过这两点的

6、直线段，但是连接两点的线段于障碍物相交，所以设法尝试折线路径。在 y 轴上取一点 C（0，y） ，若 y 适当大，则折线 ACB 与障碍物不相交，折线 ACB 的长度为：2|a+ACB显然 随着 y 的减小而减小，减小 得 ，即 ,使得 与|ACBy111AC与障碍物相切，切点分别为 E 和 F,显然 是这种折线路径中最短的。由1于满足 0|AP|,又由 AE EO,所以|AP|AE,从而 AE,同理可得 BF。 再来比较 PQ 之间路径长度 和圆弧 EF 的长度的大小。若 PQ 之间的路径可有极坐标方程 ,则有 ,可得：=() 1= - - 2+23亦即路径 APQB 的长度超过路径 AEF

7、B 的长度。以上证明足以说明了AEFB 是满足条件 A 到 B 的最短路径。5.2 模型准备一有了 4.1 中的定理，我们就可以这样认为，起点到目标点无论中间障碍物有多少，最短路径都应该是若干个线圆结构所组成。在本题中存在障碍物的状况，且障碍物在拐点处的危险区域是一个半径为 1 的圆弧，所以结合定理一，我们易知，求两点之间的最短路径中的转弯半径我们应该按照最小的转弯半径来算才能达到最优。线圆结构 5.211）如上图，设 A（ 为起点，B（ 为目标点，C（ 和1， 1） 2， 2） 3， 3）D（ 分别为机器人经过拐点分别于隔离危险线拐角小圆弧的切点，圆心4， 4）为 O（ ，圆的半径为 r，A

8、B 的长度为 a，AO 的长度为 b，BO 的长度为5， 5）c，角度 = , = , = ， .求 A B 的长度，设为 L.B OC D O解法如下：如上图可得有以下关系： 22115522a()()bc()()xy： AOB在 中在 ：RtAOC=arcosb在 中：t r所以： 2从而可得： 22Lbrcr2）而对于下图两种情况我们不能直接采用线圆的结构来解决，需要做简单的变换。 情况一：线圆结构 5.22我们假设两圆心坐标分别为 和 ,半径均为 r，M 点坐标为1(,)Oxy2()xy，那么我们很容易可以求得:3(,)xy22arcs()ba123xy这样我们就可以利用 1）中的方法

9、，先求 A 到 M，再求 M 到 B，这样分两段就可以求解。同理如果有更多的转弯，我们同样可以按照此种方法分解。情况二：线圆结构 5.23这里我们依然设圆心坐标分别为 和 ,半径均为 r，这样我1(,)Oxy2()xy们可以得到： 21OyKx那么 直线方程为：O 1()Oyy因为公切线 DE 与 平行，那么 DE 的直线方程可以表示为： 1()KxC其中： 2OCr那么把公切线的方程于圆的方程联立，渴可以求得切点 D 和 E 的坐标。这样用D 和 E 任意一点作为分割点都可以将上图分割成两个 4.21 所示的线圆结构，这样就可以对其进行求解。同理多个这样的转弯时，用同样的方法可以进行分割。5

10、.3 模型准备二 一、对于从起点经过若干点然后再到达目标点的状况，因为不能走折线路径，我们就必须考虑在经过路径中的一个目标点时转弯的状况。为了研究这个问题的方便，我们先来证明一个猜想：猜想二:如果一个圆环可以绕着环上一个定点转动，那么过圆环外两定点连接一根绳子，并以该圆环为支撑拉紧绳子，达到平衡状态时，圆心与该顶点以及两条切线的延长线的交点共线。图 5.31证明猜想：如图 4.31 所示，E 点就是圆环上的一个顶点，A B 就是拉紧的绳子，就是切线 AC 和 BD 的延长线的交点，证明 、 E、 三点共线。2O1O2我们可以用力学的知识进行证明，因为是拉紧的绳子，所以两边的绳子拉力相等，设为

11、，它们的合力设为 ，定点对圆环的作用力设为 。F0F 1F那么由几何学的知识我们可以知道 一定与 共线，而又由力的平衡条12件可知：=-01即 与 共线。12OE综上所述 、 和 三点一定共线。2二、有了以上这个定理我们可以建立以下模型：如图 4.32，要求求出机器人从 A 绕过障碍物经过 M 点到达目标点 B 的最短路径，我们采用以下方法：用一根钉子使一个圆环定在 M 点，使这个圆环能够绕 M 点转动。然后连接A 和 B 的绳子并以这些转弯处的圆弧为支撑（这里转弯处圆弧的半径均按照最小转弯半径来计算） ，拉紧绳子，那么绳子的长度就是 A 到 B 的最短距离。我们可以把路径图抽象为以下的几何图

12、形。下面我们对这段路径求解：图 5.32如图，A 是起点，B 是终点， 和 是两个固1(,)xy2(,)xy1O3(,)xy34(,)xy定的圆， 是一个可以绕 M(p，q)点转动的圆环，三个圆的半径均为2Or，C、D、E、F、G、H 均为切点。a、b、c、e，f 分别是 A 、 、A 、A12O、 的长度。A、B、 、 均是已知点， 是未知点。那么最短路径就32313O2可以表示为：L=|AC|+ +|DE|+ +|FG|+ +|HB| 因为 点的坐标未知，所以我们就不能用模型一中的线圆结构对其进行求解。2O故得先求出 点的坐标。设 坐标为（m，n） ， 、 、 、2O1AOC1221AO、

13、 分别为 （ =1、2、3、4、5） ， 、 、23A2FiDEF分别为 、 、 。这样便有以下关系：2EOM1222131322114422()()()()()()axybmncexyfn在 中：1RtAOC1arcos在 中：12 222arcosbc223rabc在 中：23AO224arcosfe在 中：2RtNF52arcosf则： 1122345又因为 一定会在 的角平分线上，所以满足：2MO2EF2我们采用向量的形式来求，易知 的一个方向向量：212O21(,)ymxnl而 与 垂直，故其一个方向向量：2OE1222(1,)xlym而： 2(,)OMpqn所以： 2arcos|l

14、综合以上式子可以求得 的坐标，从而可以得出路径的长为：2O2 2120()fLarbrrl= +HB，这可以采用模型一中的线圆结构来求解。0l5.4 模型准备三求解从起点经过若干个点再到达目标点的问题，与 4.4 不同，我们还可以有另一种方案，即适当扩大障碍物拐点处的拐弯半径使机器人能够沿直线通过路径中的目标点。这样拐点处拐弯圆弧的半径和圆心都是个变量，对于该题，那么我们可以首先设定三个圆心 、 、 ,然后按照以下步骤进行作图：1O231） 给定 ，以 为圆心， 为半径，画圆，然后过 R 点做圆 的切线 ，切1R1R1O1L点为 D。然后过 A 点做 的切线设为 ，切点为 E。12L2） 然后

15、做 F 垂直于 ，垂足为 F， F 的长就是 ，然后以 为圆心，2O2LO22为半径画圆。很显然 能由 来确定，即 。R2R11=f(R)3） 然后过 B 点做 的切线为 ，切点为 G，再过 F 垂直于 ，垂足为 H，2333L那么 H 的长度就是 ，然后以 为圆心， 为半径，画圆。很显然3O3O能由 来确定，即 = 。3R23R2f()4） 过 C 做 的切线。这就完成了由 R 经过 A 和 B 在到达 C 的路径。O5） 然后再变换 、 、 、 、 、 ，可得到新的路径。找出最小者即123123可。5.5 模型的建立假设机器人从起点 R 到到目标点 ，由 4.2 知路径一定是由圆弧和线段0M组成，设有 m 条线段，n 条圆弧。那么目标函数可以表示为： 11inmnijiLdl.rkst用此模型就可以对起点到目标点之间的路径进行优化求解。六、模型的求解6.1 问题一一、以下给出了 R 到个目标点的可能路径的最短路径：1）如图一，解决的就是 R 到目标点 A 的最短路径问题，很显然的一个问题是机器人从 的上方走的最短路径肯定是大于机器人