机器人路径规划(二)

本论文在其他论文栏目，由论文格式网整理,转载请注明来源www.lwgsw.com,更多论文,请点论文格式范文查看
http://www.91paofun.net/Article/HardTech/ControlTech/200412/248.html
黄玉芳　赵京. 具有容错性能的冗余度机器人轨迹规划
http://www.wenloo.com/WenLooPage174353-7.htm
董玉成陈义华 .基于蚂蚁算法的移动机器人路径规划
http://www.madio.net/Soft/Class8/Class73/Class139/200411/2189.html
李团结 , 张学锋 , 陈永琴.一种全向滚动球形机器人的运动分析与轨迹规划
http://vip.ilib.cn/A-xadzkjdx200701007.html
佚名. 我国的仿人形机器人研究
http://brilliantwangym.bokee.com/2514668.html
B、选择“雅虎”http://www.yahoo.com.cn/查找相关网页：
查找到相关网页数约：777,480篇。检索与本课题相关的文献为:
1. 王科俊，徐晶,王磊，张燕. 基于可拓遗传算法的机器人路径规划
http://web.gdut.edu.cn/~extenics/lw15.htm
2. 佚名.基于遗传算法的足球机器人路径规划
http://blog.csdn.net/aqua4/archive/2006/04/07/654217.aspx
3. 王挺.基于极坐标、栅格法和模糊方法的路径规划
http://hi.baidu.com/rayen/blog/item/f0f4baeca2337b2662d09f29.html
秦元庆, 孙德宝, 李宁, 马强.基于粒子群算法的移动机器人路径规划
http://www.sia.ac.cn/qikan/front/viewone.php?id=851&Language=0&ClassId=0
佚名. 基于模糊逻辑的移动机器人无碰撞路径规划(dzx23)
http://www.studa.net/dianzijixie/050608/172439.html
C、选择“网易”http://www.163.com/查找相关网页：
查找到相关网页数约：8900篇。检索与本课题相关的文献为:
. 黄祎, 孙德宝, 秦元庆.基于粒子群算法的移动机器人路径规划
http://www.4bao.net/A-bgzdh200604023.html
2. 朱庆保.复杂环境下的机器人路径规划蚂蚁算法
http://ckrd.cnki.net/grid20/detail.aspx?dbname=cjfd2006&filename=moto200604014
佚名.基于模糊逻辑的移动机器人无碰撞路径规划(dzx23)
http://www.lwhoo.com/mac/11728503698117.html
霍迎辉，张连明.一种移动机器人的路径规划算法
http://91tech.net/Article/SoftTech/TheoryTech/200501/312.html
张晓丽.基于微分进化算法的机器人路径规划方法
http://www.cczzdd.com/viewthread.php?tid=67617
朱庆保, 张玉兰.基于栅格法的机器人路径规划蚁群算法
http://www.4bao.net/A-jqr200502008.html
徐晶.基于可拓遗传算法的机器人路径规划
http://youth.hrbeu.edu.cn/exhibition/Show.asp?id=394
四、评估检索结果：
通过这门课程的学习，让我学会了如何通过检索的方式查出我所需要的东西，只要按着步骤做就能得出想要结果。我在完成这次作业的过程中遇到了很多的问题，主要有以下几点：
1.在手工检索时找相关的资料挺难找到的，也许是所找的范围挺小，还是没有找对地方用了很久的时间。在査外文相关的内容时，困难更是很大，不但在写相关内容是太难书写，而且更主要的是所需相关内容找不上，英语底子太薄弱，在这里明显就明显得感觉到好无能为力啊。
2.深有体会地感觉到这门课在检索的格式上要求很严格，必须按着规定来做，使操作起来觉得挺麻烦的，这就是所谓没有规矩不成方圆的道理吧。
3.利用中文数据库检索相关内容时，由于平时没有接触过，对其的操作挺生疏的，但是只要掌握了方法要找所需内容是很快捷方便的，利用它能够找到平时想找都很难找上的好用的资料，这点是我们这在大学里所能感受到的很有利的资源，听老师给我们解说，只有通过学校的网络才能进到这些数据库网站，在外面是根本进不去的，除非是你交费的。可见，这个资源的宝贵之处了，对于我们学生来说，最值得一提的是它们对我们来说是免费的！好处多多吧！要倍加利用好这个资源！
4.在完成这个综合检索时，遇到了挺多的困难，通过问同学他们不厌其烦的给我解说，是我学到了很多，我很感谢他们，使那些原来看起来根本就无从下手的东西变得简单起来。
5.学了这门课程，由以前几乎不太会搜索资料到现在感觉挺轻松的就能找到所需的资料，心里上都觉得有种成就感了，能有今天的进步最主要的就事带我们课的周春宏老师，没有他的特别细心和和有耐心的教我们，我想是不会有今天满足感了。感谢您——周老师！！
五、课程论文：
机器人路径规划中的双向Dijkstra二叉树算法
(Bi-directional Dijkstra with Binary Tree Sorted Algorithmin Robot Path Plan)
作者：周躜，王腾飞，戴光明
(中国地质大学计算机学院，武汉430074)
摘要：在分析现有路径规划和碰撞检测方法的基础上，提出了一种新的机器人路径规划方法：双向Dijkstra二叉树算法。在机器人路径规划中应用传统的Dijkstra算法时间复杂度是O(n2)，应用该文提出的算法进行路径规划的时间复杂度为O(nlog2n)。通过一些数据的检测，验证了在机器人路径规划中，尤其是在测试数据较多的情况下，该算法可以有效提高效率。
关键词：机器人路径规划；最短路径；双向Dijkstra；二叉树
中图分类号：TP312 文献标识码：A
ZHOU Zuan,WANG Tengfei,DAI Guangming
(School of Computer,China University of Geosciences,Wuhan 430074)
【Abstract】On the basis of analysis of current path plan methods and collision examining methods,a new robot path plan method is put forward:
bi-directional Dijkstra with binary tree sorted algorithm.It is well known that Dijkstra algorithm solves the path plan problem in time O(n2).As an
improvement on Dijkstra algorithm,because it begins from start point and end point at one time when it executes the algorithm,and sorts the set of
the points which have not been marked by binary tree,the algorithm solves path planning problem in time O(nlog n).And the enhancement on the
efficiency in robot path plan with the algorithm has been proved by testing some data,especially in the situation where the number of testing data is
very large.
【Key words】Robot path plan;Shortcut;Bi-directional Dijkstra;Binary tree
在机器人路径规划中，常常需要考虑给定两点S、T和若干障碍物，要求找出机器人从S到T并避开所有障碍物的最短路径，也就是所谓的ESPO问题。对于二维的ESPO问题，可以将两点和各障碍物之间关系转换成带权图，从而将二维ESPO问题转化成带权图的最短路径问题。最短路径算法有很多，包括图论基本方法、启发式搜索方法、动态规划方法、神经网络方法等。传统的最短路径算法主要有Floyd算法和迪杰斯特拉(Dijkstra)算法等。其中Floyd算法用于计算网络中每一对顶点之间的最短路径；Dijkstra算法用于计算一个源节点到所有其它节点的最短代价路径。Dijkstra算法由于适应网络拓扑的变化，性能稳定，因此在计算机网络拓扑路径选择得到广泛的应用。但是它们的时间复杂度与图的顶点数的平方成正比，在顶点较多的情况下就难以满足实际运算的需要。比如在我们的研究过程中，当机器人要避开的障碍物较多时，将障碍物的信息转化为无项带权图的时候顶点数目较多，运行所需的时间就较多。本文提出的双向Dijkstra二叉树算法就是为解决上述问题对Dijkstra算法的一种改进，经实验证明，在顶点数较多的图上是一种很理想的最短路径算法。
1.经典Dijkstra算法简介
Dijkstra算法用于计算一个源节点到所有其它节点的最短代价路径，它是按路径长度递增的次序来产生最短路径的算法。
1.1 Dijkstra算法的网络表示方法
交通网络图中的路段和节点，可以抽象为边和顶点，这样整个交通网络就抽象为一张图。对于一张N个节点的图，用一个二维C[N][N]数组存储网络中的数据，若节点I与节点J之间有边，则C[I][J]中存储节点I到节点J的边的权值。
1.2 Dijkstra算法的实现标号方法
这是大多数最短路径算法的核心过程，Dijkstra算法就是采用这种方法进行最短路径搜索。下面是Dijkstra算法的实现流程。其中数组D[i]记录当前节点I到源点S的最短路径。初始化D[i]=MaxInt，D[s]=0；mark[i]是个布尔数组，若已经求得从S到I的最短路径，则将mark[i]=true，对于所有的I，初始化mark[i]=flase；C[i][j]表示图中从节点I到节点J的路径长度，如果从I到J没有通路，则C[i][j]=MaxInt。(1)While mark[t]=flase do begin(2)选取节点u，满足u=min{D[x]|其中mark[x]=false}，(3)for每个从u出发的节点v do(4)D[v]<-min{D[v]，D[u]+c[u][v]};(5)mark[u]<-true;(6)end while
2.双向Dijkstra二叉树算法
2.1使用二叉树对当前最优节点选择的改进
从上述经典Dijkstra算法流程可知，该算法的效率取决于算法的(2)～(4)步，为了提高效率，可以使用优先队列来存储满足mark[x]=false的所有节点。通常，可以用二叉树来表示这个优先队列。同时，规定二叉树每个结点的优先级高于其自己子节点的优先级，具体到这个问题来说，就是D[i]值小于子节点值。使用数组T[n]来存储二叉树，n为数组元素个数，节点T[i]的左右子树分别为T[2i]和T[2i+1]，则节点T[1]为D[i]中最小的元素对于二叉树定义如下操作：
Push(x)：往优先队列后面插入一个新节点，并不停地与比其优先级低的父节点换位，称为向上调整，使得二叉树仍然满足“父节点优先级低于子节点优先级”的性质。
Pop()：删除优先队列的根结点，此节点即为当前最优节点。将最后一个叶子节点作为新的根节点，然后不停地与比其优先级高的子节点交换，称为向下调整。
Update(i)：先将节点i不停地向上调整，然后不停地向下调整。这是为了实现算法第4步优先队列中节点优先级改变时，对节点的调整，使其仍然满足性质。由于每次都将新节点都加在数组T末尾，因此二叉树高度始终为log2n。调整时最坏是将一个节点从最低层升到最高
层，所以最坏情况下需进行log2n次操作，因此上述操作时间复杂度为O(log2n)。所以使用优化队列的Dijkstra算法复杂度为O(nlog2n)，比经典算法有了较大的改进。
2.2双向Dijkstra二叉树算法
(1)算法思路
通常在基本Dijkstra算法中，要找到到终点的最短路径，必须先找到所有比终点最短路径短的所有最短路径，在顶点分布均匀的情况下，所要找到的最短路径条数和两顶点之间的距离的平方成正比。如果从两个端点同时开始搜索，到相遇时(即从两个端点都找到了到达同一顶点的最短路径)所要找到的最短路径条数只有基本Dijkstra算法的一半，然后再
从结果中找出最短路径，从而在图的顶点较多时能大幅度缩短搜索时间。若起点为S，终点为T，搜索时在节点K相遇，则SK＋KT为从S到T的一条路径，然后与已保存的最短路径比较，看是否要更优，是则保存为最短路径。若搜索时当前路径长度长于最短路径，舍弃该节点，不进行拓展。
(2)算法实现
1)图的表示
定义一个数据类型：typedef struct ttype{int id;//与其相连的节点号double cost;//边的权值struct ttype*next;//下一个相邻的节点信息}vtype; Vtype map[maxnode];//map[i]表示第I个节点的信息
2)算法过程
配合上述的二叉树算法，本文的双向Dijkstra二叉树算法如下。使用一个Flag[n]表，表示节点n是否已经被访问过。Flag[i]初始为0。1表示被正向访问过，-1表示被反向访问过。建两个堆f、b，分别代表从正、反向计算时的优先队列。堆初始时各只有一个元素，分别为计算的出发点s和t。While(f、b不都为空)do beginIf(f不为空)then beginOut<-f.pop();If(out花费大于最短路径长度)then不处理节点outElse if(out逆向计算时已经被访问过)then比较并更新最短路径Else begin标记Flag，out被正向计算访问过For每个从out出发可到达的节点do更新优先队列的值End begin End if End beginIf(b不为空)then begin Out<-b.pop();If(out花费大于最短路径长度)then不处理节点out Else if(out反向计算时已经被访问过)then比较并更新最短路径 Else begin标记Flag[out]被逆向计算访问过For每个从out出发可到达的节点do更新优先队列的值End begin End if End begin End while 输出最短路径
(3)时间复杂度分析
本算法从两个方面降低经典算法的时间复杂度：(1)两端开始的搜索，每一端要访问的节点平均不会超过n/2；(2)在标记完一个节点并更新为标记节点到起点或终点的路径长度后，要从未标记节点中选取到起点或终点路径长度最短的顶点。本算法采取优先队列的方法，与经典算法相比，只需要O(log2n)时间。综上所述，本文算法的时间复杂度为2O (n logn)，所以，总的时间花费要比O(n2)少很多。
3.算法检验
根据以上介绍的方法，笔者在VC中实现了双向Dijkstra二叉树算法，数据是随机生成的。
4.结论
本文提出的双向Dijkstra二叉树算法原理简单，实现方便，虽然这种方法增加了其它开销，但在顶点较多的图上，效果很明显，是一种优秀的最短路径求解方法。
5 .总结
在基于分布构件的软件中，为了使得软件模型能够使用工具自动地转换为性能模型，必须提供一种将性能相关信息标注在软件模型中的方法。现有的标注方法不适用于分布化、构件化应用的特征，本文提出了扩展CCPE Profile以及基于CCPE Profile的软件模型标注方法，以满足分布构件化软件模型转换成性能模型的需要。本方法使性能预测过程与软件开发过程集成起来，以减小性能预测周期和代价。
参考文献:
[1] 周培德.计算几何－－算法分析与设计[M].北京:清华大学出版社,2005-04.
[2] 司连法,王文静.快速Dijkstra最短路径优化算法的实现[J].测绘通报,2005,(8):15.
[3] 康志谕,王明生.城市交通网中最短路径算法及其实现[J].国防交通工程与技术,2005,(1):57.
[4] 王晓东,陈国龙,林柏钢.网络最短路问题的改进算法[J].小型微型计算机系统,2002,23(9).
[5] 李宁宁,刘玉树.改进的Dijkstra算法在GIS路径规划中的应用[J].计算机与现代化,2004,(9):12.
[6] 孟正大,王小忠.机器人无碰撞路径规划方法研究及实现[J].华中科技大学学报,2004,32(增刊).

首页上一页 1 2 下一页尾页 2/2/2