【作者】 蒋卓强；

【导师】 黄席樾；

【作者基本信息】 重庆大学 ， 导航、制导与控制， 2007， 硕士

【摘要】 移动机器人路径规划是一个很复杂的问题,不仅要寻求一条无碰撞的最短路径,而且还要求该路径尽可能平滑并满足一定的安全性。本论文在分析了目前各种路径规划方法优缺点的基础上,选择遗传模拟退火算法来解决静态环境下移动机器人的路径规划问题。本文首先介绍了路径规划技术的发展现状以及应用方法,并指出了本课题的研究意义和主要研究的内容。其次通过对遗传算法和模拟退火算法的研究,分析了各自的优缺点。并把这两个算法结合构成了遗传模拟退火算法,它兼备了很强的全局和局部搜索能力。接着针对路径规划问题的特点,对遗传模拟退火算法具体应用的各个环节进行了细致的分析,包括工作环境的建立、染色体的表示和编码、适应度函数的设计、遗传算子的设计、模拟退火算法参数的分析和选取等。在执行规划程序之前应用神经网络模型先建立了机器人的工作环境,利用简单的神经网络结构定义描述静态环境,不经过训练学习便得出网络的结构和权值,不再单独利用遗传算法的适应度函数实现约束条件要求,而且利用神经网络模型建立中间路径点不在障碍物内的约束条件与该模型输出的关系。然后执行基于遗传模拟退火算法的路径规划算法,在此算法中:路径编码时采用快速排斥和跨立实验实现路径点连线不与障碍物边线段相交的约束条件要求。在适应度函数选择时,通过综合考虑路径的可行性、路径的光滑性和路径长度,选用不同的平滑度和间隔度函数权重形式和构造方式,制定了有效的适应度函数。选择策略采用比例选择法;交叉算子采用单点交叉策略;变异算子首先采用启发式变异,然后在每条路径上随机选择一个变异点,最后对此点以一定的概率进行变异。模拟退火中的随机移动准则采用Metropolis准则;也使用了有效的温度更新函数。最后用MATLAB编写程序,在静态环境下对遗传算法和遗传模拟退火算法都进行了仿真。仿真结果表明,遗传模拟退火算法比标准遗传算法能够更好更快地在工作环境里规划出一条最优的路径,证明了算法的有效性和高效性。更多还原

【Abstract】 Path planning for mobile robots is a complex problem that not only guarantees a collision-free path with minimum traveling distance but also requires smoothness and security. This dissertation presents a genetic simulated annealing algorithm approach for solving the path planning problem in static mobile robot environments.Firstly, we summarize and analyze the status and research method of path planning in several active areas. Meanwhile the significance and the contents of the research are pointed out. Secondly, we develop a genetic simulated annealing algorithm, a hybrid of genetic and simulated annealing algorithm, by analyzing and comparing the advantages and disadvantages of them. The new algorithm has better capability of searching globally and locally. Thirdly, according to the characteristic of path planning problem, every component of the algorithm is analyzed carefully, including environment representation, chromosome coding, fitness function design, genetic operators design and simulated annealing algorithm parameters selection.Before path planning process, robot’s working environment is built by neural network method. Get the network structure without training and learning, and use the output of the neural network model to carry out the constraint together with the fitness function of the genetic algorithm. Rapid rejection and cross experiments are used to make sure that the path not intersect with the roadblock. The security, smoothness and length of a path determine an efficient fitness function. Select strategy uses proportion select method; crossover operator is one-point crossover strategy. Mutation operator firstly uses heuristic mutation to transform all the paths to feasible paths; then the algorithm randomly selects a mutation point in each path and mutates the point at certain probability. In the simulated annealing, random moving rule uses Metropolis rule and devise efficient temperature update function. The simulation of simple genetic algorithm and genetic simulated annealing algorithm in a static environment is carried out in MATLAB.The simulation results show that the genetic simulated annealing algorithm is faster to plan a better path in complex environment than the simple genetic algorithm, and validated the effectiveness of the proposed approach.更多还原