基于蚁群算法的机器人路径规划研究

【作者】 陈杰；

【导师】 郭毓；

【作者基本信息】 南京理工大学 ， 控制理论与控制工程， 2009， 硕士

【摘要】 移动机器人路径规划是机器人研究领域的核心内容之一,具有复杂性、约束性和非线性等特点。蚁群算法(ACA)是最近十几年发展起来的仿生优化算法,该算法在解决许多复杂问题方面已经展现出其优异的性能和巨大的发展潜力。本文主要研究静态环境下基于蚁群算法的移动机器人全局路径规划。首先,采用栅格法建立环境模型,并利用做过改进的基本蚁群算法在栅格环境模型中进行路径规划,这些改进有:利用伪随机比例规则代替随机比例规则进行路径转移;限制了蚂蚁行至当前栅格时下一步允许选择的栅格范围;对启发函数进行了重新定义;让蚂蚁根据转移概率利用“轮盘赌”方法选择下一个栅格。其次,针对基本蚁群算法在某些方面的不足和缺陷提出了三种改进算法:针对蚂蚁在搜索路径过程中落入障碍物陷阱而导致的算法停滞现象,提出了带夭折策略的蚁群算法;针对蚁群在路径搜索初始阶段建立的非最优路径上的信息素对以后蚁群的信息误导作用,提出了带奖罚机制的蚁群算法;针对机器人在实际工作中的安全避碰问题,提出了基于保守蚂蚁的蚁群算法。最后,在蚁群算法的基础上结合遗传算法(GA)提出了两种改进算法:GA-ACA算法和ACA-GA算法,并将其应用于机器人路径规划。为了验证本文所提各种算法的有效性,基于MATLAB 7.5软件开发环境设计了基于蚁群算法的移动机器人路径规划仿真系统。仿真结果验证了所提算法的有效性。更多还原

【Abstract】 The path planning for mobile robots is one of the core contents of the filed of robotics research with complex, restrictive and nonlinear characteristics. The ant colony algorithm (ACA) is a new bionics optimization algorithm developed in the past decade, it shows excellent performance and great potential for development when solving many complex problems.This thesis mainly studies global path planning for mobile robots based on ACA in static environment.Firstly, grid method is used to establish the environment model and some modifications are made to accommodate ACA to path planning in grid-based environment. These modifications include: using the pesudorandom proportional rule instead of the random proportional rule to choose path; limiting the scope of the next grid allowed to be chosen by the ants; redefining the heuristic function; using the roulette to choose the next grid for the ants.Secondly, three improved algorithm are proposed to overcome certain defects. In order to avoid algorithm stagnation caused by the ants falling into the obstacle trap, ACA with abortion strategy is proposed; In order to eliminate the misleading of the pheromone that the ants release in initial stage of path planning, ACA with reward and punishment mechanism is proposed; In order to search the optimal path with collision avoidance, ACA based conservative ants is proposed.Finally, two improved algorithm are proposed based on ACA and genetic algorithm(GA): GA-ACA algorithm and ACA-GA algorithm.In order to verify the effectiveness of all the proposed algorithm, path planning simulation system for mobile robots is designed based on MATLAB 7.5 development environment. Simulation results showed that the proposed algorithm can reach a preferable performance.更多还原