基于弹性绳索拉伸的机器人避障问题摘要本文研究了机器人避障的相关问题。

在一个已知区域中存在12个障碍物，使用基于弹性绳索拉伸的方法，求解了由出发点到目标点的最短路径和最短时间路径。

我们在禁区顶点以最小转弯半径转向为最优的前提下，对障碍物进行了加工，即将限定区域向外扩展并将顶点圆角化。

那么最短路径就由两部分组成：一部分是平面上的直线段，另一部分是限定区域上部分弧构成。

由于最短路径一定是由直线线段和圆弧做组成，而弹性绳索紧贴障碍物时，弹性绳索与直线线段和圆弧重合，并且弹性绳索有自然缩短的趋势，弹性绳处于紧绷状态，此时弹性绳长就是最短路径。

问题一，将绳索系与起点和终点，使用拉伸弹性绳索的方法，找到所有符合要求的绳索连结成的路径并计算路径长度，最终最短的绳长即为所求。

由于符合要求的路径可能比较多，我们又使用了尺规作图进行简化了以及一般情况下的Dijkstra求解最短路径的方法。

最终求得：O→A最短路径长度为471.037O→B最短路径长度为 853.13O→C最短路径长度为1092.82O→A→B→C→O最短路径长度为2714.31问题二，由于机器人转弯时所行走的速度和转弯半径有关。

而当转弯半径最小时相应的速度也最小。

就必须平衡转弯半径和转弯时速度的这一对矛盾。

本文通过极限状态的求解，计算出可能的最短时间路径。

关键字：最短路径切线长弧长一、问题的重述图1是一个800×800的平面场景图，在原点O(0, 0)点处有一个机器人，它只能在该平面场景范围内活动。

图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述如下表：编号障碍物名称 左下顶点坐标 其它特性描述1正方形 (300, 400) 边长200 2圆形 圆心坐标(550, 450)，半径70 3平行四边形 (360, 240) 底边长140，左上顶点坐标(400, 330) 4三角形 (280, 100) 上顶点坐标(345, 210)，右下顶点坐标(410, 100) 5正方形 (80, 60) 边长150 6三角形 (60, 300) 上顶点坐标(150, 435)，右下顶点坐标(235, 300) 7长方形 (0, 470) 长220，宽60 8平行四边形 (150, 600) 底边长90，左上顶点坐标(180, 680) 9长方形 (370, 680) 长60，宽120 10正方形 (540, 600) 边长130 11正方形 (640, 520) 边长80 12 长方形 (500, 140) 长300，宽60 在图1的平面场景中，障碍物外指定一点为机器人要到达的目标点(要求目标点与障碍物的距离至少超过10个单位)。

规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。

机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。

为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。

机器人直线行走的最大速度为50=v 个单位/秒。

机器人转弯时，最大转弯速度为21.0100e1)(ρρ-+==v v v ，其中ρ是转弯半径。

如果超过该速度，机器人将发生侧 翻，无法完成行走。

请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。

对场景图中4个点O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具体计算：(1) 机器人从O(0, 0)出发，O→A 、O→B 、O→C 和O→A→B→C→O 的最短路径。

(2) 机器人从O (0, 0)出发，到达A 的最短时间路径。

注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。

图1 800×800平面场景图二、模型假设1、机器人可以抽象成为点；2、未到达终点前机器人行走过程不会意外停止；3、忽略影响机器人行走的外界因素，机器人可以准确转弯。

4、假设路径是一条带有弹性的橡皮绳，有自动缩短的趋势三、符号说明符号符号说明S 起点G 终点D机器人离障碍物的最小距离转弯半径P i 切点四、问题分析问题一：根据题中的限定条件，机器人的行走路线一定为直线和与直线相切的圆弧，我们对障碍物进行改造，使得障碍物也为直线和圆弧构成。

求出所有符合条件的切线和直线段的长度，并寻求最短的路径即为我们需要的最短路径。

另外这条路径还可以看做是栓在起点的一条弹性绳索，经由各个障碍物，并以障碍物的拐角处的圆弧为支撑拉紧最终到达终点的路径，此时这段绳子的长度便是一条可能的最短路径。

具体在搜索路径时，我们知道两点确定的直线段最短。

那么就将起点和终点用弹性绳索连结，分别向上方和下方拉伸绳索，让绳索绕过障碍物。

由于绳索带有弹性，将自动贴紧改造后的障碍物。

此时的绳长就是需要的自然直线段和弧长的总和。

问题二：由于机器人转弯时所行走的速度和转弯半径有关。

转弯速度v 是转弯半径ρ的增函数，当转弯半径最小时相应的速度也最小。

就必须平衡转弯半径和转弯时速度的这一对矛盾。

通过考虑各种极限状态，求解最短时间路径。

五、模型的建立5.1相关定理证明1.禁区顶点转弯最优，以最小转弯半径转向最优[1]如图所示：假设在平面中有A(a ，0)和B(-a ，0)两点，中间有一个半圆形的障碍物，证明从A 到B 的最优路径为A 错误！未找到引用源。

B 。

平面上连接两点最短的路径是通过这两点的直线段，但是连接两点的线段于障碍物相交，所以设法尝试折线路径。

在y 轴上取一点C(0，y)，若y 适当大，则折线ACB 与障碍物不相交，折线ACB 的长度为：22||2a +y ACB =显然||ACB 随着y 的减小而减小，减小y 得y →1y ，即1C C →,使得1AC 与1C B 与障碍物相切，切点分别为E 和F,显然1AC B 是这种折线路径中最短的。

由于满足0<错误！未找到引用源。

<2π的角满足错误！未找到引用源。

<错误！未找到引用源。

,所以易知弧度EF 小于1EC F 的长， 即错误！未找到引用源。

<E 错误！未找到引用源。

,从而AE +错误！未找到引用源。

+FB<1AC B ,记线段AE 、弧度EF 、线段FB 为AEFB,那么AEFB 比任何折线路径都短。

下面再考察一条不穿过障碍物的任何一条路径，设其分别于OE 和OF 的延长线交与P 、Q 两点，记A 和P 之间的路径长度为错误！未找到引用源。

，显然错误！未找到引用源。

>|AP|,又由AE ⊥EO,所以|AP|>AE,从而错误！未找到引用源。

>AE,同理可得错误！未找到引用源。

>BF 。

再来比较PQ 之间路径长度错误！未找到引用源。

和圆弧EF 的长度的大小。

若PQ 之间的路径可有极坐标方程错误！未找到引用源。

,则有错误！未找到引用源。

,可得：错误！未找到引用源。

=错误！未找到引用源。

≥错误！未找到引用源。

-3π-错误！未找到引用源。

亦即路径APQB 的长度超过路径A 错误！未找到引用源。

B 的长度。

以上证明足以说明了A 错误！未找到引用源。

B 是满足条件A 到B 的最短路径。

2.在中间目标点附近转向，且中间目标点位于圆弧中点处最优[1]如图所示：E 点就是圆环上的一个顶点，A 错误！未找到引用源。

B 就是拉紧的绳子，2O 就是切线AC 和BD 的延长线的交点，证明1O 、E 、2O 三点共线。

我们可以用力学的知识进行证明，因为是拉紧的绳子，所以两边的绳子拉力相等，设为F ，它们的合力设为0F ，定点对圆环的作用力设为1F 。

那么由几何学的知识我们可以知道0F 一定与12O O 共线，而又由力的平衡条件可知：0F =-1F即12O O 与2EO 共线。

综上所述1O 、E 和2O 三点一定共线。

5.2 障碍区域扩展题中要求机器人与障碍物距离d 个单位，转弯半径最小为ρ个单位，那么我们将障碍物区域向外扩展形成新的禁区。

如下图：5.3 弹性绳索拉伸构造路径两点确定的直线段最短。

将起点和终点用弹性绳索连结，分别向上方和下方拉伸绳索，让绳索绕过障碍物。

由于绳索带有弹性，将自动贴紧改造后的障碍物。

下图为示意图：5.4 禁区类型分析由于禁区顶点转弯最优，以最小转弯半径转向最优。

我们将弹性绳索绕过圆角矩形的障碍区域，绳索与圆角矩形的顶点关系有3种。

分别计算这三种情况的直线段与弧长。

计算过程中涉及到的解析几何的公式见文献[3]情况一：起点和终点之间只有一个障碍区域，此情况可以抽象为下图所示：起点到终点的路径长度为：12S PP G。

通过几何的方法我们可以计算出切点、路径长度，具体计算见附录中算法LengthA 。

情况二：起点和终点之间经过两个障碍区域，并且这两个障碍区域在弹性绳索的两dρ侧，此种情况如下图所示：通过几何方法分析，可以得出两圆心连线的中点为公切线的中点。

那么就可以转化为两个情况一的组合，分别按照情况一计算并求和即可。

起点到终点的路径长度为：1223SPP F F P PG +，其中F 为23P P 的中点。

这种情况下的中点坐标F(x ，y)计算较简单121222x x x y y y +⎧=⎪⎪⎨+⎪=⎪⎩。

路径长度见算法LengthC 。

情况三：起点和终点之间两个障碍区域，并且这两个障碍区域在弹性绳索的同侧，此种情况如下图所示：此种情况中2312//P P O O ，可以计算出23P P 的直线方程，该直线方程联立圆的方程即可算出切点23P P 、。

再由中点坐标公式计算出23P P 的中点P 。

P 做为左侧图形的终点，右侧图形的起点，此时该情况就转化成了两个情况一。

分别计算并求和即可。

起点到终点的路径长度为：1223SPP P PP PG +，其中P 为23P P 的中点。

中点坐标计算方法见附录中算法M 。

路径长度见算法LengthB 。

5.5 中间结点的弧化处理机器人由O 点出发经由A 、B 、C 到达O 点时，因为机器人不能折现转弯，因此机器人在到达中间结点时就应该提前转向，即中间结点的弧化处理。

我们可以想象，在中间节点A 上，套上半径为R 的圆环。

弹性绳索经过节点A 的最P佳拉法即为最优解。

直观的看绳索绷紧后，A 点与目标点的连线在两条切线的角平分线上时，目标点的位置最优。

设中间目标点(a,b),最小转弯半径为ρ。

圆的中心位于轨迹22020)()(ρ=-+-b y a x 上。

圆的方程为22020)()(ρ=-+-y y x x 。

那么最优路径中的机器人中间目标点位于圆弧的中点，圆心与中间目标点的连线为圆环的两条切线的角平分线上。