基于图的机器人路径规划蚂蚁算法-运筹学与控制论专业论文.docxVIP

南京帅范大学2006年坝一一学位论文 南京帅范大学2006年坝一一学位论文 基于削的机器人路径规划蚂蚁优化算法 Abstract The path planning for mobile robots especially in the uncertain environment plays an important role in the field of robotics．It is arising many scholars口nteresting and it’s already got a series ofachievements in this field．At present，there are many advanced algorithms used to solve this optimal problem．But this problem is NP-Hard problem，so，to find a better algorithm becomes the hot topic in the researching field of the robotics，therefore，a graph—based ant algorithm is proposed according to the present condition of the studying and the intellective and bionics tendency of the fieldN development．First，the workplace is modeled by grid method and expressed by a state—matrix，based on which，a connected graph will be obtained．Then，a group of ants traverse on the graph simulating the behavior of foraging and the optimal path will be obtained．At last，using the branching random process and birth．death process to analyze the convergence of the proposed algorithm theoretically,based on it，some computer simulations are taken and the results show that the method of this paper is effective and convergent Keywords：unknown environment，path planning of mobile robot， graph-based ant algorithm，convergence，branching process， birth—death process II 南京师范大学2006年坝：J：学位论义 南京师范大学2006年坝：J：学位论义 基于蹦的机{}5；人路径规划蚂蚁优化竹渍 序言 迄今为止，对于未知环境下机器人路径规划，人们已经探索出了许多有效的求解方法。 诸如虚拟力场法、基于学习或Q学习的规划方法、滚动窗121规划方法、非启发式方法及各 类定位、导航方法等等。近年来，不少学者用改进的遗传算法、神经网络、随机树、蚁群算 法等方法对未知环境下机器人路径进行了规划。机器人路径规划算法向智能化、仿生化发展 是一个明显的趋势。由于已有算法不同程度的存在一定局限性，诸如有哪些信誉好的足球投注网站空间大、算法复杂、 效率不高等．尤其对于未知环境，不少路径规划算法的复杂度较高，甚至无法求解。根据目 前的研究现状和不足，本文提出了一种用于解决未知环境下机器人路径规划的基于图的蚂蚁 算法。理论分析和实验结果都证明了本文算法的有效性和收敛性。 一、本课题研究的主要内容 本文在用栅格法对机器人的工作空间进行建模的基础上，用一个状态矩阵表示其状态， 由此构造一个连通图，由一组蚂蚁在图上模拟蚂蚁的觅食行为，从而得到避碰的优化路径， 并借鉴分枝随机过程和生灭过程的理论知识，用概率的方法从理论上对该算法的收敛性进行 了分析，结合计算机仿真，证明了本文算法的有效性和收敛性。 二、论文的组织结构 本论文共分为七章 第一章对机器人路径规划进行了简要概述，简介了路径规划的定义，路径规划问题的分 类等基础性问题，阐述了机器人路径规划(包括环境已知和