基于惩罚函数NPGA的足球机器人动态目标规划
|
摘要
当前,随着计算机网络技术的迅速发展,计算机快速转向开放的、网络平台的、协同工作方式。基于Agent理论和技术尤其是MAS(Multi-Agent Systems)的理论和技术带来了设计和实现分布与开放环境中运行的软件系统一个全新模式。
机器人世界杯足球赛(The Robot World Cup,简称RoboCup),是典型的MAS,是MAS标准问题。在RoboCup中,路径规划的目的主要是为了在充满对抗的赛场上规划出一条满足某项评价指标的无碰撞路径。路径规划主要应用于机器人底层策略中,作为足球机器人基本动作实现的基础,他的优劣将直接影响动作的实时性和准确性,因此,每个足球机器人研究人员都把它作为一个研究重点。
论文通过分析传统的机器人路径规划方法,将足球机器人路径规划归结为一个多目标优化问题,总结了足球机器人体力的三元组模型,并且建立的动态目标路径规划的运动模型,并给出了基于惩罚函数的小生境遗传算法(PNPGA,Penalty Function Niche Pareto GeneticAlgorithm)的路径规划算法。论文的主要工作及创新点是:
(1)论文详细的分析了SoccerServer中关于足球机器人体力的部分,提出了足球机器人体力的三元组模型:球员体力使用的效率、球员的体力的恢复速率、路径规划所需时间。并且将体力作为多目标优化中的一个目标。
(2)论文提出了一种针对移动目标进行路径规划的运动模型,并且结合足球机器人的体力模型,利用惩罚函数和小生境遗传算法进行多目标优化。
(3)在详细分析遗传算法以及小生境遗传算法(NPGA)的基本理论以及NPGA的三种标准实现方法的基础上,论文在NPGA中引入一个惩罚函数,这样可以保证在一个小生境内只有一个最优值,防止收敛于局部最优解,加快了算法的收敛的速度。
Presently, along with rapid development of computer network technology, the computer fast changes to the opening, network platform, cooperation working mode. Agent based theory and technical, especially multi-agent systems, bring us a brand-new mode to design and implement software system which run in a distribution and opening environment.
RoboCup (The RobotWorld Cup Initiative) is a typical multi-agent system, has currently chosen soccer as its standard task. In the RoboCup, the purpose of the path planning is to find a path without collision which satisfied some estimate criterions. The path planning is applied in the lower policy which uses as the foundation of the robots' basic actions, the planning result directly has an effect on the action's real-time and the veracity. So, everyone who study on the robot look path planning as an emphases.
On the base of analyzing the traditional path planning methods of the robots, the paper looks path planning as a multi-object optimize problem. We summarize the stamina model of the robot as an ternary set, and then we set the athletics model which can planning the path for the dynamic object. At last we give the planning algorithm based on the penalty function niche pareto genetic algorithm. The innovation and the main work of the paper list as bellows:
(1)On the base of detailedly analyzing the SoccerServer of the robot's stamina, we bring forward the robot's stamina model: a ternary set. The using efficiency of the player, the stamina resume rate of the player and the needed time of path planning. And we regard stamina model as an object of the multi-object optimize.
(2)In this paper we bring forward an athletics model which aim at dynamic object path planning, and we combine with the stamina model. At last we use the niche pareto genetic algorithm based on penalty function.
(3)On the base detailedly analyzing genetic algorithm and niche pareto genetic algorithm base theoretics, then analyzing the three standard realizations of the niche pareto genetic algorithm(NPGA). In the paper we bring forward a penalty function, so we can assure that in a niche there will be only one best root. So we can avoid constringency local classic root, and accelerate the constringency speed.
机器人世界杯足球赛(The Robot World Cup,简称RoboCup),是典型的MAS,是MAS标准问题。在RoboCup中,路径规划的目的主要是为了在充满对抗的赛场上规划出一条满足某项评价指标的无碰撞路径。路径规划主要应用于机器人底层策略中,作为足球机器人基本动作实现的基础,他的优劣将直接影响动作的实时性和准确性,因此,每个足球机器人研究人员都把它作为一个研究重点。
论文通过分析传统的机器人路径规划方法,将足球机器人路径规划归结为一个多目标优化问题,总结了足球机器人体力的三元组模型,并且建立的动态目标路径规划的运动模型,并给出了基于惩罚函数的小生境遗传算法(PNPGA,Penalty Function Niche Pareto GeneticAlgorithm)的路径规划算法。论文的主要工作及创新点是:
(1)论文详细的分析了SoccerServer中关于足球机器人体力的部分,提出了足球机器人体力的三元组模型:球员体力使用的效率、球员的体力的恢复速率、路径规划所需时间。并且将体力作为多目标优化中的一个目标。
(2)论文提出了一种针对移动目标进行路径规划的运动模型,并且结合足球机器人的体力模型,利用惩罚函数和小生境遗传算法进行多目标优化。
(3)在详细分析遗传算法以及小生境遗传算法(NPGA)的基本理论以及NPGA的三种标准实现方法的基础上,论文在NPGA中引入一个惩罚函数,这样可以保证在一个小生境内只有一个最优值,防止收敛于局部最优解,加快了算法的收敛的速度。
Presently, along with rapid development of computer network technology, the computer fast changes to the opening, network platform, cooperation working mode. Agent based theory and technical, especially multi-agent systems, bring us a brand-new mode to design and implement software system which run in a distribution and opening environment.
RoboCup (The RobotWorld Cup Initiative) is a typical multi-agent system, has currently chosen soccer as its standard task. In the RoboCup, the purpose of the path planning is to find a path without collision which satisfied some estimate criterions. The path planning is applied in the lower policy which uses as the foundation of the robots' basic actions, the planning result directly has an effect on the action's real-time and the veracity. So, everyone who study on the robot look path planning as an emphases.
On the base of analyzing the traditional path planning methods of the robots, the paper looks path planning as a multi-object optimize problem. We summarize the stamina model of the robot as an ternary set, and then we set the athletics model which can planning the path for the dynamic object. At last we give the planning algorithm based on the penalty function niche pareto genetic algorithm. The innovation and the main work of the paper list as bellows:
(1)On the base of detailedly analyzing the SoccerServer of the robot's stamina, we bring forward the robot's stamina model: a ternary set. The using efficiency of the player, the stamina resume rate of the player and the needed time of path planning. And we regard stamina model as an object of the multi-object optimize.
(2)In this paper we bring forward an athletics model which aim at dynamic object path planning, and we combine with the stamina model. At last we use the niche pareto genetic algorithm based on penalty function.
(3)On the base detailedly analyzing genetic algorithm and niche pareto genetic algorithm base theoretics, then analyzing the three standard realizations of the niche pareto genetic algorithm(NPGA). In the paper we bring forward a penalty function, so we can assure that in a niche there will be only one best root. So we can avoid constringency local classic root, and accelerate the constringency speed.
引文
[1]http://www.robocup.org
[2]M.Asada,H.Kitano,I.Noda,et al.RoboCup:Today and tomorrow-What we have have learned.[J]Artificial Intelligence.1999,110:193-214
[3]H.Kitano,M.Tambe,P.Stone,et al.The RoboCup Synthetic Agent Challenge 97[A].San Francisco,CA:Morgan Kaufmann,1997,24-29
[4]Rosenberg R S,Simulation of genetic populations with biochemical properties[C].Ph.D.thesis,University of Michigan,Ann Harbor,Michigan,1967.
[5]Cheng,R.and M.Gen,A survey of genetic multi-objective optimizations[J],Technical report,Ashikaga Institute of Technology,1998.
[6]Ishibuchi,H.and T.Murata,A multi-objective genetic local search algorithm and its application to flow shop scheduling[C],IEEE Transactions on Systems,Man and Cybernetics,1998,28(3):392403.
[7]Murata,T.,H.Ishibuchi,and H.Tanaka,Multi-objective genetic algorithm and its application to flow shop scheduling[J],Computers and Industrial Engineering,1996,30(4):957968.
[8]Fonseca C M,Fleming P J.An overview of evolutionary algorithms in multi-objective optimization[J].Evolutionary Computation,1995,3(1):1-16
[9]Srinivas N,Deb K.Multi-objective Optimization Using Non-dominated Sorting in Genetic Algorithms.Evolutionary Computation[J],1994,2(3):221248
[10]Rudolph G.Evolutionary search under partially ordered sets[Z].Technical Report No 1-67/99,Dortmund:Department of Computer Science/LS11,University of Dortmund,Germany,1999.
[11]Zitzler E,Deb K,Thiele L.Comparison of multi-objective evolutionary algorithms:Empirical results[J].Evolutionary Computation,Journal,1999,8(2):173-196.
[12]Knowles J.Come D.The Pareto archived evolution strategy:a new baseline algorithm for multi-objective optimization[A].Proceedings of the 1999 Congress on Evolutionary Computation[C],Piscatway,New Jersey.IEEE Service Center 1999.
[13]Deb K,Aarawal S,Pratap A,et al.A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization:NSGA-Ⅱ[A].Proc of the Parallel Problem Solving from Nature VI Conf[C].Paria,2000.849-858.
[14]朱常琳,马浩全,郭光辉.一种移动机器人的路径规划与路径跟踪控制[J].兰州铁道学院学报,2003,(01)
[15]王志文,郭戈.一种新的移动机器人路径跟踪控制策略[J].兰州理工大学学报,2006,(04)
[16]Cao Qixin,Huang Yanwen,Zhou Jingliang.An Evolutionary Artificial Potential Field Algorithm for Dynamic Path Planning of Mobile Robot[J].Intelligent Robots and Systems,2006 IEEE/RSJ International Conference on Oct.2006 Page(s):3331-3336
[17]J.C Latombe.Robot Motion Planning[M].Kluwer,Norwell.M A.1991
[18]Chakravorty,S.Junkins,J.L.A Methodology for Intelligent Path Planning[C].Intelligent Control,2005.Proceedings of the 2005 IEEE International Symposium on,Mediterrean Conference on Control and Automation 27-29 June 2005 Page(s):592-597
[19]李宏超,黄亚楼,阙嘉岚等.基于四叉树环境模型的轮式移动机器人平滑路径生成方法.机器人[J],2001,23(5):427-428
[20]Moshaiov,A.Avigad,G.The Extended Concept-based Multi-objective Path Planning and its A-life implications[J].Artificial Life,2007.ALIFE '07.IEEE Symposium on 1-5 April 2007Page(s):259-265
[21]Yahja A,Singh S Stentz.An efficient on-line path planner for out door mobile robots[J].Robotics and Autonomous Systems.2000,32(2-3):129-143
[22]Razavian,A.A.Sun,J.Cognitive based adaptive path planning algorithm for autonomous robotic vehicles[C].Southeast Conference,2005.Proceedings.IEEE 8-10 April 2005Page(s):153-160
[23]Chen,J.Li-Ren Li.Path planning protocol for collaborative multi-robot systems[J].Computational Intelligence in Robotics and Automation,2005.CIRA 2005.Proceedings.2005IEEE International Symposium on 27-30 June 2005 Page(s):721-726
[24]Lin lei,Houjun,Wang,Qinsong Wu.Improved Genetic Algorithms Based Path planning of Mobile Robot Under Dynamic Unknown Environment[C].Mechatronics and Automation,Proceedings of the 2006 IEEE International Conference on 25-28 June 2006 Page(s):1728-1732
[25]Kaneshige,A.Akamatsu,T.Terashima,K.The development of an autonomous overhead traveling crane with real time path planning based on the potential method[C].Control and Automation,2005.ICCA '05.International Conference on Volume 2,26-29 June 2005Page(s):1079-1084 Vol.2
[26]袁曾任,高明.在动态环境中移动机器人导航和避碰的一种新方法[J].机器人,2000,22(2):81-87
[27]王会丽,傅卫平,方宗德等.基于改进势场函数的移动机器人路径规划[J].机床与液压,2002,10(6):67-68
[28]Petres,C,Pailhas,Y.Patron,P.Petillot,Y.Evans,J.Lane,D.Path Planning for Autonomous Underwater Vehicles[C].Robotics,IEEE Transactions on[see also Robotics and Automation,IEEE Transactions on]Volutne 23.Issue 2.April 2007 Page(s):331-341
[29]杨明,王宏,何克忠.基于激光雷达的移动机器人环境建模与避障[J].清华大学学报(自然科学版),2000,20(7):112-114
[30]王醒策,张汝波,顾国昌.基于势场栅格法的机器人全局路径规划[J].哈尔滨工程大学学报2003,24(4):170-172
[31]Guo Tong-ying;Qu Dao-kui;Dong Zai-li.Research of Path Planning for Polishing Robot Based on Improved Genetic Algorithm[C].Robotics and Biomimetics,2004.ROBIO 2004.IEEE International Conference on 22-26 Aug.2004 Page(s):334-338
[32]Aiharak.Chao tic Neural Networks[J].Phys LettA,1990,144(6,7):334-340
[33]Xinying Xu;Keming Xie.Path Planning and Obstacle-Avoidance for Soccer Robot Based on Artificial Potential Field and Genetic Algorithm[C],Intelligent Control and Automation,2006.WCICA 2006.The Sixth World Congress on Volume 1,2006 Page(s):3494-3498
[34]李智军,吕恬生.遗传算法在自主移动机器人局部路径规划中的应用[J].机械设计,2000,12(7):27-28
[35]Shakir,H.;Won-jong Kim.Nanoscale path planning and motion control[C].American Control Conference,2005.Proceedings of the 2005 8-10 June 2005 Page(s):3604-3609 vol.5
[36]周明,孙树栋.遗传算法原理及应用[M].国防工业出版社,1999.6
[37]吴青松,基于遗传算法的移动机器人路径规划研究[D],电子科技大学,2005.5,24-25
[38]Bagheri,E.;Deldari,H.;Dejong Function Optimization by Means of a Parallel Approach to Fuzzified Genetic Algorithm[C].Computers and Communications,2006.ISCC '06.Proceedings.11th IEEE Symposium on 26-29 June 2006 Page(s):675-680
[39]Horn,J.Nafpliotis,N.Goldberg,D.E.A niched Pareto genetic algorithm for multiobjective optimization[C].Evolutionary Computation,1994.IEEE World Congress on Computational Intelligence.,Proceedings of the First IEEE Conference on 27-29 June 1994 Page(s):82-87vol.1
[40]Bagheri,E.;Deldari,H.;Dejong Function Optimization by Means of a Parallel Approach to Fuzzified Genetic Algorithm[C].Computers and Communications,2006.ISCC '06.Proceedings.11th IEEE Symposium on 26-29 June 2006 Page(s):675-680
[41]Yanrong Hu;Yang,S.X.;A knowledge based genetic algorithm for path planning of a mobile robot[C].Robotics and Automation,2004.Proceedings.ICRA '04.2004 IEEE International Conference on Volume 5,26 April-1 May 2004 Page(s):4350-4355 Vol.5
[42]Xiaofeng Wang,Shoukui Si Xijing Sun.The Study of Improved Genetic Algorithm to Solve Flight Optimization Problem[C]。 Chinese Control Conference,2006 7-11 Aug.2006Page(s):1438-1441
[2]M.Asada,H.Kitano,I.Noda,et al.RoboCup:Today and tomorrow-What we have have learned.[J]Artificial Intelligence.1999,110:193-214
[3]H.Kitano,M.Tambe,P.Stone,et al.The RoboCup Synthetic Agent Challenge 97[A].San Francisco,CA:Morgan Kaufmann,1997,24-29
[4]Rosenberg R S,Simulation of genetic populations with biochemical properties[C].Ph.D.thesis,University of Michigan,Ann Harbor,Michigan,1967.
[5]Cheng,R.and M.Gen,A survey of genetic multi-objective optimizations[J],Technical report,Ashikaga Institute of Technology,1998.
[6]Ishibuchi,H.and T.Murata,A multi-objective genetic local search algorithm and its application to flow shop scheduling[C],IEEE Transactions on Systems,Man and Cybernetics,1998,28(3):392403.
[7]Murata,T.,H.Ishibuchi,and H.Tanaka,Multi-objective genetic algorithm and its application to flow shop scheduling[J],Computers and Industrial Engineering,1996,30(4):957968.
[8]Fonseca C M,Fleming P J.An overview of evolutionary algorithms in multi-objective optimization[J].Evolutionary Computation,1995,3(1):1-16
[9]Srinivas N,Deb K.Multi-objective Optimization Using Non-dominated Sorting in Genetic Algorithms.Evolutionary Computation[J],1994,2(3):221248
[10]Rudolph G.Evolutionary search under partially ordered sets[Z].Technical Report No 1-67/99,Dortmund:Department of Computer Science/LS11,University of Dortmund,Germany,1999.
[11]Zitzler E,Deb K,Thiele L.Comparison of multi-objective evolutionary algorithms:Empirical results[J].Evolutionary Computation,Journal,1999,8(2):173-196.
[12]Knowles J.Come D.The Pareto archived evolution strategy:a new baseline algorithm for multi-objective optimization[A].Proceedings of the 1999 Congress on Evolutionary Computation[C],Piscatway,New Jersey.IEEE Service Center 1999.
[13]Deb K,Aarawal S,Pratap A,et al.A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization:NSGA-Ⅱ[A].Proc of the Parallel Problem Solving from Nature VI Conf[C].Paria,2000.849-858.
[14]朱常琳,马浩全,郭光辉.一种移动机器人的路径规划与路径跟踪控制[J].兰州铁道学院学报,2003,(01)
[15]王志文,郭戈.一种新的移动机器人路径跟踪控制策略[J].兰州理工大学学报,2006,(04)
[16]Cao Qixin,Huang Yanwen,Zhou Jingliang.An Evolutionary Artificial Potential Field Algorithm for Dynamic Path Planning of Mobile Robot[J].Intelligent Robots and Systems,2006 IEEE/RSJ International Conference on Oct.2006 Page(s):3331-3336
[17]J.C Latombe.Robot Motion Planning[M].Kluwer,Norwell.M A.1991
[18]Chakravorty,S.Junkins,J.L.A Methodology for Intelligent Path Planning[C].Intelligent Control,2005.Proceedings of the 2005 IEEE International Symposium on,Mediterrean Conference on Control and Automation 27-29 June 2005 Page(s):592-597
[19]李宏超,黄亚楼,阙嘉岚等.基于四叉树环境模型的轮式移动机器人平滑路径生成方法.机器人[J],2001,23(5):427-428
[20]Moshaiov,A.Avigad,G.The Extended Concept-based Multi-objective Path Planning and its A-life implications[J].Artificial Life,2007.ALIFE '07.IEEE Symposium on 1-5 April 2007Page(s):259-265
[21]Yahja A,Singh S Stentz.An efficient on-line path planner for out door mobile robots[J].Robotics and Autonomous Systems.2000,32(2-3):129-143
[22]Razavian,A.A.Sun,J.Cognitive based adaptive path planning algorithm for autonomous robotic vehicles[C].Southeast Conference,2005.Proceedings.IEEE 8-10 April 2005Page(s):153-160
[23]Chen,J.Li-Ren Li.Path planning protocol for collaborative multi-robot systems[J].Computational Intelligence in Robotics and Automation,2005.CIRA 2005.Proceedings.2005IEEE International Symposium on 27-30 June 2005 Page(s):721-726
[24]Lin lei,Houjun,Wang,Qinsong Wu.Improved Genetic Algorithms Based Path planning of Mobile Robot Under Dynamic Unknown Environment[C].Mechatronics and Automation,Proceedings of the 2006 IEEE International Conference on 25-28 June 2006 Page(s):1728-1732
[25]Kaneshige,A.Akamatsu,T.Terashima,K.The development of an autonomous overhead traveling crane with real time path planning based on the potential method[C].Control and Automation,2005.ICCA '05.International Conference on Volume 2,26-29 June 2005Page(s):1079-1084 Vol.2
[26]袁曾任,高明.在动态环境中移动机器人导航和避碰的一种新方法[J].机器人,2000,22(2):81-87
[27]王会丽,傅卫平,方宗德等.基于改进势场函数的移动机器人路径规划[J].机床与液压,2002,10(6):67-68
[28]Petres,C,Pailhas,Y.Patron,P.Petillot,Y.Evans,J.Lane,D.Path Planning for Autonomous Underwater Vehicles[C].Robotics,IEEE Transactions on[see also Robotics and Automation,IEEE Transactions on]Volutne 23.Issue 2.April 2007 Page(s):331-341
[29]杨明,王宏,何克忠.基于激光雷达的移动机器人环境建模与避障[J].清华大学学报(自然科学版),2000,20(7):112-114
[30]王醒策,张汝波,顾国昌.基于势场栅格法的机器人全局路径规划[J].哈尔滨工程大学学报2003,24(4):170-172
[31]Guo Tong-ying;Qu Dao-kui;Dong Zai-li.Research of Path Planning for Polishing Robot Based on Improved Genetic Algorithm[C].Robotics and Biomimetics,2004.ROBIO 2004.IEEE International Conference on 22-26 Aug.2004 Page(s):334-338
[32]Aiharak.Chao tic Neural Networks[J].Phys LettA,1990,144(6,7):334-340
[33]Xinying Xu;Keming Xie.Path Planning and Obstacle-Avoidance for Soccer Robot Based on Artificial Potential Field and Genetic Algorithm[C],Intelligent Control and Automation,2006.WCICA 2006.The Sixth World Congress on Volume 1,2006 Page(s):3494-3498
[34]李智军,吕恬生.遗传算法在自主移动机器人局部路径规划中的应用[J].机械设计,2000,12(7):27-28
[35]Shakir,H.;Won-jong Kim.Nanoscale path planning and motion control[C].American Control Conference,2005.Proceedings of the 2005 8-10 June 2005 Page(s):3604-3609 vol.5
[36]周明,孙树栋.遗传算法原理及应用[M].国防工业出版社,1999.6
[37]吴青松,基于遗传算法的移动机器人路径规划研究[D],电子科技大学,2005.5,24-25
[38]Bagheri,E.;Deldari,H.;Dejong Function Optimization by Means of a Parallel Approach to Fuzzified Genetic Algorithm[C].Computers and Communications,2006.ISCC '06.Proceedings.11th IEEE Symposium on 26-29 June 2006 Page(s):675-680
[39]Horn,J.Nafpliotis,N.Goldberg,D.E.A niched Pareto genetic algorithm for multiobjective optimization[C].Evolutionary Computation,1994.IEEE World Congress on Computational Intelligence.,Proceedings of the First IEEE Conference on 27-29 June 1994 Page(s):82-87vol.1
[40]Bagheri,E.;Deldari,H.;Dejong Function Optimization by Means of a Parallel Approach to Fuzzified Genetic Algorithm[C].Computers and Communications,2006.ISCC '06.Proceedings.11th IEEE Symposium on 26-29 June 2006 Page(s):675-680
[41]Yanrong Hu;Yang,S.X.;A knowledge based genetic algorithm for path planning of a mobile robot[C].Robotics and Automation,2004.Proceedings.ICRA '04.2004 IEEE International Conference on Volume 5,26 April-1 May 2004 Page(s):4350-4355 Vol.5
[42]Xiaofeng Wang,Shoukui Si Xijing Sun.The Study of Improved Genetic Algorithm to Solve Flight Optimization Problem[C]。 Chinese Control Conference,2006 7-11 Aug.2006Page(s):1438-1441