计算机应用 ›› 2017, Vol. 37 ›› Issue (7): 1967-1971.DOI: 10.11772/j.issn.1001-9081.2017.07.1967

• 人工智能 • 上一篇    下一篇

基于改进遗传算法的餐厅服务机器人路径规划

徐林, 范昕炜   

  1. 中国计量大学 质量与安全工程学院, 杭州 310018
  • 收稿日期:2017-01-09 修回日期:2017-03-01 出版日期:2017-07-10 发布日期:2017-07-18
  • 通讯作者: 徐林
  • 作者简介:徐林(1990-),男,安徽阜阳人,硕士研究生,主要研究方向:服务机器人、智能控制、路径规划;范昕炜(1973-),男,江西广丰人,高级工程师,博士,主要研究方向:机器人、模式识别与智能控制、数据挖掘。
  • 基金资助:
    国家公益性行业科研项目(201410028-02)。

Path planning for restaurant service robot based on improved genetic algorithm

XU Lin, FAN Xinwei   

  1. College of Quality and Safety Engineering, China Jiliang University, Hangzhou Zhejiang 310018, China
  • Received:2017-01-09 Revised:2017-03-01 Online:2017-07-10 Published:2017-07-18
  • Supported by:
    This work is partially supported by the National Public Welfare Industry Research Projects (201410028-02).

摘要: 针对遗传算法(GA)易产生早熟现象和收敛速度慢的问题,提出了一种基于传统遗传算法(TGA)的改进遗传算法——HLGA,用于实际餐厅服务机器人的路径规划。首先,通过基于编辑距离的相似度方法对拟随机序列产生的初始种群进行优化;其次,采用自适应算法的改进交叉概率和变异概率调整公式,对选择操作后的个体进行交叉、变异操作;最后,计算具有安全性评价因子函数的个体适应度值,进一步对比、迭代得到全局最优解。理论分析和Matlab仿真表明,与TGA和基于个体相似度改进的自适应遗传算法(ISAGA)相比,HLGA的运行时间分别缩短了6.92 s和1.79 s,且规划的实际路径更具有安全性和平滑性。实验结果表明HLGA在实际应用中能有效提高路径规划质量,同时缩小搜索空间、减少规划时间。

关键词: 遗传算法, 餐厅服务机器人, 拟随机序列, 编辑距离, 路径规划

Abstract: Since the Genetic Algorithm (GA) is easy to produce premature phenomenon and has slow convergence rate, an improved GA based on Traditional GA (TGA), called HLGA (Halton-Levenshtein Genetic Algorithm), was proposed for path planning of real restaurant service robots. Firstly, the similarity method based on edit distance optimized the initial population of quasi-random sequence; secondly, the improved crossover probability and mutation probability adjustment formula based on the adaptive algorithm were adopted to cross and mutate the individuals after they had been selected. Finally, the individual fitness values of the safety evaluation factor functions were calculated, and the global optimal solution was obtained by comparison and iteration. Through theoretical analysis and Matlab simulation, the running time of HLGA was decreased by 6.92 seconds and 1.79 seconds compared with TGA and Adaptive Genetic Algorithm based on Improved independent Similarity (ISAGA), and the actual path of planning was more secure and smooth. The simulation results show that HLGA can effectively improve the quality of path planning in practical applications, meanwhile reduces the searching space and the planning time.

Key words: Genetic Algorithm (GA), restaurant service robot, quasi-random sequence, edit distance, path planning

中图分类号: