基于学习分类器的多机器人路径规划收敛性研究  

Research on Cnvergence of Multi-Robots Path Planning Based on Learning Classifier System

作　　者：邵杰[1] 杨静宇[1] 万鸣华[1] 黄传波[1] 

机构地区：[1]南京理工大学计算机学院,南京210094

出　　处：《计算机研究与发展》2010年第5期948-955,共8页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60705020)~~

摘　　要：近年来,学习分类器LCS已广泛用于基于归纳学习的强化学习领域,但很少用于多机器人领域.提出了一种基于集成强化学习和遗传算法的学习分类器用于多机器人路径规划领域.由于遗传算法具有早熟收敛、局部最优解和占据较大的存储空间等缺陷,针对静态和动态环境因素对多机器人路径规划的不同影响,设计了在静态和动态环境下不同的适应度函数,在理论上推导并证明了信用分配算法的收敛性,为路径规划算法的收敛提供了理论保证.仿真实验结果也表明遗传算法和学习分类器结合用于多机器人的路径规划是有效的,遗传算法的早熟收敛、局部最优解、占据存储空间较大和收敛速度慢等难题得到很大改善,提高了多机器人发现安全路径的能力.所以LCS在机器人领域的应用前景是非常广阔的,是今后需要努力研究的方向.Learning classifier systems（LCS） are rule-based inductive learning systems that have been widely used in the field of reinforcement learning over the last few years,but seldom used in the multi-robots domain.In this paper a distributed learning classifier system,which combines reinforcement learning and genetic algorithm to create a set of rules on-line,is used to design optimal paths for multi-robots path planning.Due to premature convergence,local optimal solution,needing a larger storage space and other shortcomings of genetic algorithms,and targeted at the different effects of the static and dynamic environment,the authors design different fitness function in static and dynamic environment.They have derived and proved that the credit allocation algorithm is convergent and provides a theoretical guarantee for the path planning algorithms.Simulation results also show that the genetic algorithm and learning classifier system combination for multi-robots path planning is effective.Premature convergence,local optimal solution,needing a larger storage space and other shortcomings of the genetic algorithm have been significantly improved.The proposed new approach has increased multi-robots＇ ability to quickly find safe paths.So LCS has a very broad application prospects in the field of robotics and also is the future research directions.

关 键 词：路径规划 多机器人 学习分类器 收敛性 适应度函数 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] TP242[自动化与计算机技术—计算机科学与技术]