机器人避障问题

1、机器人避障问题 摘要本文研究了机器人避障最短路径和最短时间路径的问题，主要研究在一个存在12个障碍物的区域中，由出发点到达目标点以及由出发点经过途中的若干目标点到达最终目标点两种情形，要得出机器人到达目标点的最短路径，我们将路径分为两个部分组成：一部分是平面上的自然最短路径（即直线段），另一部分则是限定区域（即圆弧）。针对问题一，我们将直线和圆弧组成的路径作为机器人行走的最短路径，因此我们建立了线圆结构并构造直角三角形，运用勾股定理与两点之间的距离建立相应方程，无论多么复杂的路径，我们都可以将路径划分为若干个这种线圆结构来求解。我们利用线圆结构方法对机器人到达目标点的每一条路径进行分解，然后把

2、几条最短路径采用穷举法列举出来，通过比较得出最优路径分别为（详细的坐标路线见模型的建立于求解部分）：针对问题二，要求得机器人从O(0，0)到达A点的最短时间路径，由题意我们知道机器人的直线行走速度是一定的，所以我们考虑到增加机器人转弯时的转弯半径，从而增加转弯速度，相应的长度也发生了变化。针对这个问题我们根据机器人的最大转弯速度与问题一的分析，通过Matlab计算可得当时，机器人从O点出发到A的时间最短为94.6001秒。关键词：线圆结构 勾股定理 穷举法 最优路径 机器人避障 、问题重述1.1 背景分析机器人是整合控制论、机械电子、计算机、材料和仿生学的产物。在工业、医学、农业、建筑工业甚至

3、军事领域中均有重要用途。现在。，国际上对机器人是靠自身动力和控制能力来实现各种功能的一种机器。联合国标准化组织采纳了美国机器人协会给机器人下的定义：“一种可编程和多功能的操作机；或是为了执行不同的任务而具有可用电脑改变和可编程动作的专门系统。”在科技界，科学家会给每一个科技术语一个明确的定义，但机器人问世已有几十年，机器人的定义仍然仁者见仁，智者见智，没有一个统一的意见。机器人是虽然外表不像人，也不以人类的方法操作，但可以代替人力自动工作的机器。后来美国著名科普作家艾萨克.阿西莫夫为机器人提出了三条原则，即“机器人三定律”：第一定律机器人不得伤害人，或任何人受到伤害而无所作；第二定律机器人应服

4、从人的一切命令，但命令与第一定律相抵触时例外；第三定律机器人必须保护自身的安全，但不得与第一、第二定律相抵触。这些“定律”构成了支配机器人行为的道德标准，机器人必须按人的指令行事，为人类生产和生活服务1.2 问题的提出题中给出的是一个800×800的平面场景图，在原点O（0,0）点处有一个机器人，它只能在该平面场景活动范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物。在图中的平面场景中，障碍物外指定一点为机器人要到达的目标（要求目标与障碍物的距离至少超过10个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧式机器人转弯路径。机器人不能折线转弯，转弯路径由

5、与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最小距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。机器人直线行走的最大速度为v0=5个单位/秒。机器人转弯时，最大转弯速度为，其中是转弯半径。如超过该速度，机器人将发生侧翻，无法完成行走。现要建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图4个点O(0，0), A(300，300), B(100，700), C(700，640),具体计算：（1）机器人从O(0，0),出发，OA、OB

6、、OC和OABCO的最短路径。（2）机器人从O（0,0）出发，到达A的最短时间路径。二、问题分析2.1 问题一的分析针对问题一，我们要求定点O（0,0）按照一定的行走规则绕过障碍物到达目标点的最短路径。根据题目我们从OA点考虑到了两种最短路径，OB点我们考虑了三条途径，OC点我们考虑了六条最短路径，通过计算每一条路径我们得出最优路径。由于机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，所以我们采用线圆结构方法并对路径构造出一个直角三角形，再利用勾股定理以两点之间的距离公式建立相应的方程，

7、得到每个坐标的断点与切点，最终运用Matlab得出机器人到达目标点的最短路径。2.2 问题二的分析针对问题二，要求机器人从O（0,0）出发，到达A的最短时间路径。由题目已知条件我们知道机器人的转弯速度与直线行走的最大速度，在不能增加直线行走速度的情况下，我们考虑增加机器人的转弯半径。当圆的半径从10慢慢增大时，O到A的时间会变化，当圆的半径增加到某个临界值时，即可求得最短时间，从而得出最短时间路径。三、模型的假设与符号的说明3.1 模型的假设 （1）假设机器人在行走过程中不会出现故障 (2) 假设机器人不会与障碍物发生碰撞 (3) 机器人直线行走的最大速度为v0=5个单位/秒 (4) 机器人只

8、在限定的平面场景中行走 （5）假设机器人能够抽象成点来处理 （6 ）机器人在直线段路径中一直保持最大行走速度（7) 机器人转弯时不会发生侧翻 (8) 机器人不会折线走符号诠释（x, y）点的坐标L路径的长度第i行段切线的长度第j段圆弧的长度转弯半径拉力障碍物上的任意点与行走路径之间的最短距离 表3-1 符号说明表 四、模型的建立及求解4.1 模型I的建立 针对问题一要得出机器人到达目标点的最短路径，首先我们要知道每个点的坐标，在有障碍物的情况下，机器人将沿圆的圆弧行走，即机器人到达每一个目标点都是由若干段线段以及若干个圆弧构成的。将机器人从O（0，0）到达目标点分为几小段，将每一小段上已知的两

9、个坐标与圆弧的圆心连接起来，从而构造出一个直角三角形，我们设两个点的坐标分别为（a1,b1、（a2,b2）、所以、切点坐标为（x,y），两条变的长度分别为、，如下图4-1所示。rm() 图4-1 构造直角三角形示意图 由图中构造的三角形，运用勾股定理我们可以得出： 则由此我们可以根据两点的距离公式，推导得出以下方程组： 由此图中各点的坐标都是已知的，针对每一条路径所经过的点与障碍物的坐标，运用Matlab软件编程把每一组数据代入方程组即可计算出每条路径相应切点的坐标（详见附件）。 模型准备 1 定理：具有圆形限定区域的最短路径是由两部分组成的：一部分是平面上的自然最短路径（即直线段），另一部分

10、是限定区域的部分边界， 这两部分是由相切的，互相连接的。 有了上述定理，我们就可以这样认为，起点到终点中间无论障碍物有多少，最短路径都应该是若干个线圆结构所组成。在本题中存在障碍物的状况，且障碍物在拐点处的危险区域是一个半径为10个单位的圆弧，所以结合上面定理，我们易知，求两点之间的最短路径中的转弯半径我们应该按照最小的转弯半径来算才能达到最优。下面分析我们在题目中将会碰到的线圆结构：DACB 图4-4线圆结构 1）如图，设A为起点，B为目标点，C和D分为机器人经过拐点分别于隔离危险线拐角小圆弧的切点，圆心为O(x5,y5),圆的半径为r,AB的长度为a,AO的长度为b,BO的长度为c,角解法

11、如下：求ACBD的长度，设为L,如上图可得以下关系: （2）而对于下面两种情况我们不能直接采用线圆的结构来解决，需要做简单的变换。 情况一图4-5 线圆结构 我们假设两圆心坐标分别为 这样我们就可以利用1）中的方法，先求出A到M,再求M到B, 这样分两段就可以求解。同理如果与更多的转弯，我们同样可以按照此种方法分解。 情况二:CDAOOOOEFBO 图4-6线圆结构这里我们依然设圆心坐标分别为O,半径均为r，这样我们可以的到： 那么OO直线方程为： 因为公切线DE与OO平行，那么DE的直线方程可表示为： 其中： 那么把公切线的方程与圆的方程联立，可以求得切点D和E的坐标。这样用D和E的中点分为

12、分割点都可以讲上图分割成两个图所示的线圆结构，这样就可以对其进行求解。用同样的方法可以进行分割。模型准备2 对于从起点经过若干点然后在到达目标点的状况，因为不能走折线路径，我们就必须考虑在经过路径中的一个目标点时转弯的状况。为了研究这个问题的方便，我们先来证明本文中的一个猜想：猜想、；如果一个圆环可以绕着环上一个定点转动，那么过圆环外两定点链接一根绳子，并与该圆环为支撑拉紧绳子，达到平衡状态时，圆心与该顶点以及两条切线的延长线的交点共线。 证明：如图4-7所示，E点就是圆环上的一个顶点，ACDB就是拉紧绳子，B 用力学的知识进行证明，因为是拉紧的绳子，所以两边的绳子拉力相等，设为,它们的合力设

13、为。DCAE图4-7两切线相交示意图由几何的知识可以知道共线，而又由力的平衡条件可知： 即4.2模型的建立通过以上这个定理我们可以建立以下模型：如图4-8，要求出机器人从O点出发，OABCO的最短路径，我们采用以下方法：分别用钉子使圆环定在A，B、C三点上，使这些圆环能够分别绕点A，B、C转动。然后连接的绳子并以这些转弯处的圆弧为支撑（这里转弯处圆弧的半径均按照最小转弯处半径来计算），拉紧绳子，那么绳子的长度就是 的最短距离。假设机器人从起点O到目标点,由上面可知路劲一定是由圆弧和线段组成，设有m条线段，n条圆弧。那么目标函数可表示为： 用此模型就可以对起点到目标点之间的路径进行优化求解。4.

14、3模型I的求解一、以下给出机器人从O点到目标点的可能路径的最短路径：（1）如图4-9，解决的就是O到目标点A的最短路径问题，很显然的一个问题是机器人可以从5号障碍物的上方走，也可以从5好障碍物的下方走，我们可以分别计算出这两条可能为最短路径的路径长度，然后进行比较，取最小者就是O到目标点A的最短路径。图4-9 2) 如图4-10，解决的是O到目标点B的最短路径问题，图中给出了可能的三条路径的最短路径，我们可以分别计算出三条可能为最短路径长度，然后进行比较，取最小者就是O到目标点B的最短路径。 图4-10 图4-113）如图4-11，解决的是O到目标点C的最短路径问题。OC的可能路径共有六条，图

15、中只画出了其中一条可能路径的最短路径，我们同样可以分别计算出六条可能的最短路径，取最小者就是OC的最优路径。4）图4-12 ，求解的是OABCO的最短路径问题，这使我们考虑的不仅仅是经过障碍物拐点的问题，应该考虑经过路径中的目标点处转弯的问题，这是简单的线圆结构就不能解决这种问题，我们在拐点及途中目标点处都采用最小转弯半径的形式，也可以适当的变换拐点半径，使机器人能够沿直线通过途中的目标点，最终求得最短途径。图4-12 OABCO的路径示意图二，然后用Matlab求解结果如下：（1） O到目标点A的可能路径有两条，就有两条可能的最短路径，如图，机器人走上面这条路径到达A，运用Matlab求得该

16、路径的总距离为471.0372。而机器人走上面这条路径到达A ，求得该路径的总距离为498.4259.所以机器人从O出发OA的最短路径的总距离为471.0372，具体坐标路线为：（0,0）（70.5059,213.1405） （坐标路线1）（2）O到目标点B的可能路径有三条，即就有三条可能的最短路径。 如图，机器人走最上面这条路径到达B这条路径有六条线段和五段圆弧组成，直接用Matlab求得最短路径为：845.7001。二机器人经过中间一条路径到达B，这条路径也是有六条线段和五段圆弧组成，直接用Matlab求得这条路径的结果为877.3949。机器人经过最下边一条路径，同理求得这条路径的结果为

17、947.825。综上所述，O到目标点B的最短路径为845.701。具体的坐标路线为：（3）O到目标点C的可能路径有六条，和2中的方法一样，最终求解结果O到目标点C的最短路径为1076.6094，具体的坐标路线为： (4)的最短路径如图所示，最终求解结果为：2602.3058，具体坐标路线为：（0,0）4.4 模型II的求解 题目中要求建立机器人从区域中一点到达另一点的避障最短时间路径的数学模型，在第一问的基础上，因为第一问我们是建立的避障最短路径模型，当路径最短（固定）的情况下，时间是随着速度的变化而变化的，但是机器人直线行走的最大速度为v0=5个单位/秒。机器人转弯时，最大转弯速度为可知，直

18、线行走，机器人的速度已经不可增加了，但是转弯时，机器人的速度是随着转弯半径的增大而增大的，但是不可能超过v0, 所以我们要尽量节省时间的途径只有一条，那就是增加机器人的转弯时的转弯半径，但是此时转弯圆弧的圆心不能还是一开始的（80,120）点了，如果还是在（80,120），而半径增大时，会增大O到A的路径长度，所以转弯圆弧的圆心要沿圆的切线AT1和AT2组成的角的角平分线往下移动（如下图），但是该圆始终与圆心为（80,120），半径为10的圆内切。当圆的半径从10慢慢增大时，O到A的时间会变化，当圆的半径增加到某个临界值时，即可求得最短时间，从而得出最短时间路径。 图4-13最短时间路径示意图

19、根据问题1的分析，可以求得过圆的两条切线AT1和AT2长，和弧线的长度 坐标路线5五、模型的评价5.1模型优点1、巧妙运用了Matlab软件来计算；2、模型优化后用解析几何进行求解，精确度较高；3、假设符合实际情况，模型对问题的描述合理准确，推导严谨，因此结果比较准确，模型具有实用性；4、建立的规划模型能与实际紧密联系，结合实际情况对问题进行求解，使得模型具有很好的通用性和推广型；5.2模型缺点1、此模型适于全局规划，获得精确却失去了效率。2、在障碍物较多时，且形状不规则时，模型需要进一步改进。六、模型的改进及推广6.1模型的改进本文采用了穷举法来对每一条路径的数据进行分析，求出坐标点的同时计算中存在一些误差，在以后的论文中，遇到类似模型时，我们将把误差减少到最低。6.2模型的推广本题所应有的模型实用性较高，在本文所研究的机器人躲避障碍物行走的最短路径问题，通过对本问题的分析以及建立的模型来看，我们可以将模型推广到社会上的一些实际问题，比如：运输问题，追踪问题等等。在实际生活中，我们利用此种模型可以减少许多人力，精力以及财力，且适合于由于多种因素影响目标时的判断方法。参考文献：（1） 谭永基，数学建模，上海，复旦大学出版社，2011.（2） 邦迪，图论及其应用，西安，县科学出版社 1984（3） 胡海星，RPG游戏中精灵的移动