硅谷杂志：基于线性规划的机器人避障问题 |
| 2012-11-11 11:40 作者：张文川 来源：硅谷网 HV： 编辑： 【搜索试试】
|
|
[硅谷网11月11日文] 据《硅谷》杂志2012年第17期刊文称，机器人避障最短路径及最短时间路径其实就是研究具有圆形限定区域的最短路径的问题，主要研究机器人在有若干个障碍物一个区域中，由出发点到达目标点以及由出发点经过途中的若干目标点到达最终目标点的两种情形。通过分析我们可以得出最短路径是由两部分组成的：一部分是在一个平面两点之间的最短路即直线路径，另一部分是障碍物区域的部分边界，这两部分是相切连接的。除此之外我们还发现最小转向曲率半径和障碍物区域大小的浮动对结果都有影响。根据这个结果，可以得出最短路径一定是由直线和圆弧做组成，为此可以建立线圆结构模型，这样不管障碍物有多少，路径有多复杂，我们都可以将路径划分为若干个这种线圆结构来求解。对于路径当中经过障碍物再到达目标点的状况，采用两种方案，一种是在障碍物拐点和节点都采用最小转弯半径的形式，另一种是适当扩大障碍物拐点处的转弯半径，使得机器人能够尽大可能沿直线通过路径中的障碍物到达目标点。建立最优化模型对两种方案分别进行求解。
1模型分析
对于从起点经过若干点然后再到达目标点的状况，因为不能走折线路径，我们就必须考虑在经过路径中的一个目标点时转弯的状况。为了研究这个问题的方便，我们先来证明一个猜想：
猜想：如果一个圆环可以绕着环上一个定点转动，那么过圆环外两定点连接一根绳子，并以该圆环为支撑拉紧绳子，达到平衡状态时，圆心与该顶点以及两条切线的延长线的交点共线。
2模型建立思路
从日常生活中的直接感官出发，将点到点的路径看成一根无质量的弹性绳，弹性绳有自然缩短的趋势，将弹性绳两端拴在起点和终点，使其自然伸长，然后拉开使其绕过障碍物，在弹性绳绷紧时的状态，就是局部最优解。于是我们可以给出如下前提：
1）禁区顶点处转向最优；
2）最小曲率半径转向最优；
3）转向曲率圆圆心无偏最优。
3模型建立
如下图所示，要求求出机器人从A绕过障碍物经过M点到达目标点B的最短路径，根据以上猜想，我们采用以下方法：用一根钉子使一个圆环定在M点，使这个圆环能够绕M点转动。然后连接A和B的绳子并以这些转弯处的圆弧为支撑（这里转弯处圆弧的半径均按照最小转弯半径来计算），拉紧绳子，那么绳子的长度就是A到B的最短距离。我们可以把路径图抽象为以下的几何图形。下面我们对这段路径求解：
图4.32
如图，A是起点，B是终点，和是两个固定的圆，是一个可以绕M(p，q)点转动的圆环，三个圆的半径均为r，C、D、E、F、G、H均为切点。a、b、c、e，f分别是A、、A、A、的长度。A、B、、均是已知点，是未知点。那么最短路径就可以表示为：
L=|AC|++|DE|++|FG|++|HB|因为点的坐标未知，所以我们就不能用模型一中的线圆结构对其进行求解。故得先求出点的坐标。设坐标为（m，n），、、、、分别为（=1、2、3、4、5），、、分别为、、。这样便有以下关系：
在中：
在中：
在中：
在中：
则：
又因为一定会在的角平分线上，所以满足：，我们采用向量的形式来求，易知的一个方向向量：，而与垂直，故其一个方向向量：，而：。所以：
综合以上式子可以求得的坐标，从而可以得出路径的长为：
=+HB，这可以采用模型一中的线圆结构来求解。
4结论
本文主要研究了机器人避障最优路径问题，我们可以先求出所有的切线，包括出发点和目标点到所有圆弧的切线以及所有圆弧与圆弧之间的切线，然后把这且曲线看成若干定点，给这些定点赋一个等于切线长度的权值，如果某两条切线有一个公切圆弧，则代表这两条曲线的顶点是一条直线的两个端点，边上的权值等于这两条切线之间的劣弧长度。然后在加一个源点和终点，那么在所有代表出发点与其它圆弧之间切线的顶点与源点连成一条边，权值均为0，同理在所有代表目标点到其它圆弧切线的顶点与终点连成一条边，权值均为0，这样题目就转化成了求源点到达终点之间的最短路径问题了，这里最短路径就是指经过所有顶点与边的权值之和最小。
参考文献：
[1]谭永基，数学模型，上海：复旦大学出版社，2011.
[2]邦迪，图论及其应用，西安：西安科学出版社，1984.
[3]胡海星，RPG游戏中精灵的移动问题，杂志《程序员》，2011.
[4]尤承业，解析几何，北京：北京大学出版社，2004.
[5]周培德，计算几何—算法与设计，北京清华大学出版社，2005.
作者简介：
张文川，硕士，助教，兰州石化职业技术学院信息处理与控制工程系。
|
|
|
|
【对“硅谷杂志：基于线性规划的机器人避障问题”发布评论】 |
版权及免责声明：
① 本网站部分投稿来源于“网友”，涉及投资、理财、消费等内容，请亲们反复甄别，切勿轻信。本网站部分由赞助商提供的内容属于【广告】性质，仅供阅读，不构成具体实施建议，请谨慎对待。据此操作，风险自担。
② 内容来源注明“硅谷网”及其相关称谓的文字、图片和音视频，版权均属本网站所有，任何媒体、网站或个人需经本网站许可方可复制或转载，并在使用时必须注明来源【硅谷网】或对应来源，违者本网站将依法追究责任。
③ 注明来源为各大报纸、杂志、网站及其他媒体的文章，文章原作者享有著作权，本网站转载其他媒体稿件是为传播更多的信息，并不代表赞同其观点和对其真实性负责，本网站不承担此类稿件侵权行为的连带责任。
④ 本网站不对非自身发布内容的真实性、合法性、准确性作担保。若硅谷网因为自身和转载内容，涉及到侵权、违法等问题，请有关单位或个人速与本网站取得联系（联系电话：01057255600），我们将第一时间核实处理。
|
|
|
|
