计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (31): 245-248.DOI: 10.3778/j.issn.1002-8331.2009.31.073

• 工程与应用 • 上一篇    

机器人全覆盖最优路径规划的改进遗传算法

刘 松1,李志蜀1,李 奇2   

  1. 1.四川大学 计算机学院,成都 610064
    2.四川师范大学 软件重点实验室,成都 610066
  • 收稿日期:2008-06-18 修回日期:2008-10-22 出版日期:2009-11-01 发布日期:2009-11-01
  • 通讯作者: 刘 松

Improved Genetic Algorithms optimal area covering path planning for family robot

LIU Song1,LI Zhi-shu1,LI Qi2   

  1. 1.Department of Computer Science,Sichuan University,Chengdu 610064,China
    2.Key Lab of Software,Sichuan Normal University,Chengdu 610066,China
  • Received:2008-06-18 Revised:2008-10-22 Online:2009-11-01 Published:2009-11-01
  • Contact: LIU Song

摘要: 全区域覆盖是一种特殊的路径规划,要求遍历环境中所有的可达区域。目前已经提的许多算法,如模板算法、分块算法等,都只能保证覆盖所有的区域,对于寻找全局最优解却无能为力。提出了一种基于遗传算法的全区域覆盖算法,结合分块算法和模板算法的优点。先采用矩形分解法将环境划分成若干个相邻的子模块,并为每一个子模块选用相应的模板,从而生成覆盖路径,然后采用遗传算法找出最优的路径。算法在虚拟环境中进行了实验,实验结果证明了其可行性和有效性。

关键词: 全区域覆盖路径规划, 遗传算法, 矩形分解法, 模板算法

Abstract: A special kind of path planning is complete coverage path planning.There are a lot of algorithms on this problem have been developed,e.g.template based,cellular decomposition.But these algorithms just cover the complete area;they are not designed to optimize the process.This paper presents a method of complete coverage path planning based on genetic algorithms,which combine the advantages of cellular decomposition and template algorithm.The environment is divided in sub-regions as in rectangular decomposition method,and then Genetic Algorithms(GA) is used to compute and find the order of the sub-regions and the appropriate template for each region. The algorithm is tested in the virtual environment;the simulation results confirm the feasibility of this method.

Key words: complete coverage path planning, Genetic Algorithms(GA), rectangular decomposition method, template algorithm

中图分类号: