多机器人系统中围捕策略的研究
|
摘要
随着分布式人工智能技术的发展,多机器人系统的研究得到越来越多的关注。多机器人系统在大型船舶制造,现代物流系统中的仓库管理,空间探测,无人作战系统,还有社会和家庭服务等行业中都有广阔的应用前景。多机器人的智能围捕是一个常用的检验机器人学习策略优劣的平台,对智能移动机器人的产业化具有重要的意义。
论文推导出了多机器人围捕的临界条件。在深入分析多机器人围捕数学模型的基础上,论文用求极值的方法,推导出了围捕机器人与逃跑者速度的最小比值。在智能水平和视野范围都相同的情况下,围捕机器人和逃跑者的速度之比只有大于这个临界值,围捕任务才可能完成。这个理论为实际工程设计中的资源分配提供了参考依据。
论文提出了一种新的多机器人围捕方案。当围捕机器人的速度小于逃跑者时,采用常规的围捕方法很难完成任务。利用这种新的智能伏击策略,让各个围捕机器人相互协作,将逃跑者驱入最佳围捕区,然后按照文中提出的智能围捕策略实施围捕任务,提高了围捕的成功率。
论文设计出了一种智能的逃跑策略。为了增大围捕任务的难度,缩小仿真实验与实际情况的差距,论文改进了“最近避让策略”,将围捕机器人的速度和方向都考虑在内,然后采用加权矢量和的方法确定逃跑的方向。这样提高了智能围捕平台测试结果的可信度。
最后的仿真实验结果证明了围捕临界条件的存在性和新的围捕方案的可行性。
As the development of Distributed Artificial Intelligence technology, the research of Multi-Robot System (MRS) is receiving more and more attention. MRS can be widely applied in industries such as large scale manufacturing like large ship manufacturing, warehouse management in modern logistics, space exploring, and unmanned combat system, as well as private and public service industry. The intelligent capture among the MARS is a testing platform for the effectiveness of robot learning strategy,it is of great significance to put intelligent mobile robot into industrial utility.
Firstly, this thesis deduces the critical condition of collective capture. Analyzing thoroughly the mathematical model of MRS, this thesis deduces the minimum velocity ratio between the capture robot and evader with the method of working out the extreme value. Provided their intelligence and field of view are equal, the task of capture can be accomplished only if the velocity ratio between capture robot and evader are larger than this critical value. This theory provides guidance for the resources-allocating task in real engineering design.
Secondly, it proposes a novel Multi-Robot scheme. It is rather difficult to complete the task with the general capture approach when the velocity of capture robot is less than that of the evader. Chasing the evader to the optimum capture zone with cooperation between capture robots, and implementing the intelligent capture strategy to finish the task, this new intelligent ambush strategy increases the success rate of capture. Thirdly, it designs an intelligent evasion strategy. In order to increase the difficulty of this task and fill the gap between the simulation experiment and real game, this paper improves Evading the Most Nearest Object Approach by taking into account of the vectors of all evasion direction and adding them all together. Thus it makes the testing result of the intelligent capture platform more convincible.
Finally the statistics of the simulation experiment data justifies the existence of the critical condition under which the task is implemented and the feasibility of the scheme devised.
论文推导出了多机器人围捕的临界条件。在深入分析多机器人围捕数学模型的基础上,论文用求极值的方法,推导出了围捕机器人与逃跑者速度的最小比值。在智能水平和视野范围都相同的情况下,围捕机器人和逃跑者的速度之比只有大于这个临界值,围捕任务才可能完成。这个理论为实际工程设计中的资源分配提供了参考依据。
论文提出了一种新的多机器人围捕方案。当围捕机器人的速度小于逃跑者时,采用常规的围捕方法很难完成任务。利用这种新的智能伏击策略,让各个围捕机器人相互协作,将逃跑者驱入最佳围捕区,然后按照文中提出的智能围捕策略实施围捕任务,提高了围捕的成功率。
论文设计出了一种智能的逃跑策略。为了增大围捕任务的难度,缩小仿真实验与实际情况的差距,论文改进了“最近避让策略”,将围捕机器人的速度和方向都考虑在内,然后采用加权矢量和的方法确定逃跑的方向。这样提高了智能围捕平台测试结果的可信度。
最后的仿真实验结果证明了围捕临界条件的存在性和新的围捕方案的可行性。
As the development of Distributed Artificial Intelligence technology, the research of Multi-Robot System (MRS) is receiving more and more attention. MRS can be widely applied in industries such as large scale manufacturing like large ship manufacturing, warehouse management in modern logistics, space exploring, and unmanned combat system, as well as private and public service industry. The intelligent capture among the MARS is a testing platform for the effectiveness of robot learning strategy,it is of great significance to put intelligent mobile robot into industrial utility.
Firstly, this thesis deduces the critical condition of collective capture. Analyzing thoroughly the mathematical model of MRS, this thesis deduces the minimum velocity ratio between the capture robot and evader with the method of working out the extreme value. Provided their intelligence and field of view are equal, the task of capture can be accomplished only if the velocity ratio between capture robot and evader are larger than this critical value. This theory provides guidance for the resources-allocating task in real engineering design.
Secondly, it proposes a novel Multi-Robot scheme. It is rather difficult to complete the task with the general capture approach when the velocity of capture robot is less than that of the evader. Chasing the evader to the optimum capture zone with cooperation between capture robots, and implementing the intelligent capture strategy to finish the task, this new intelligent ambush strategy increases the success rate of capture. Thirdly, it designs an intelligent evasion strategy. In order to increase the difficulty of this task and fill the gap between the simulation experiment and real game, this paper improves Evading the Most Nearest Object Approach by taking into account of the vectors of all evasion direction and adding them all together. Thus it makes the testing result of the intelligent capture platform more convincible.
Finally the statistics of the simulation experiment data justifies the existence of the critical condition under which the task is implemented and the feasibility of the scheme devised.
引文
[1]金周英.关于我国智能机器人发展的几点思考.机器人技术与应用, 2001, 4:5~7.
[2]张海英,刘祚时,林桂娟.群体机器人研究的现状和发展.电子技术应用, 2004, 2:1~3.
[3]王宏,艾海舟.移动机器人体系结构与系统设计.机器人, 1993, 15(1):49~54.
[4]卢韶芳,刘大维.自主式移动机器人导航研究现状及其相关技术.农业机械学报, 2002, 33(2):112-116.
[5]王天然.一种开放式移动机器人体系结构.机器人, 1995. 17(5):193-199.
[6] W Burgard, M Moors, D Fox et al. Collaborative Multi-Robot Exploration. Proceedings of the IEEE International Conference on Robotics and Automation, 2000:476~481.
[7] Y U Cao, A. S. Fukunaga, A. B. Kahng. Cooperative Mobile Robotics: Antecedences and Directions. Autonomous Robots, 1997. 4(1):7~27.
[8] G. Dudek, M. Jenkin, E. E. Milios et al. A Taxonomy for Multi-Agent Robotics. Autonomous Robots, 1996. 3(4):375~397.
[9]李实,徐旭明,叶榛等.国际机器人足球比赛及其相关技术机器人.机器人, 2000,22(5):20~26.
[10]顾国昌,李亚波.基于总体势减小的动态调度技术解决多机器人的路径规划.机器人, 2001, 23(2):172~174.
[11]郑大钟.线性系统理论.北京:清华大学出版社, 1990, 57~59.
[12] PerezT Lozano. Spatial Planning: A Configuration Space Approach, IEEE Trans Computers, 1983, 32(2):108~120.
[13] R. A. Brooks, PerezT Lozano. A Subdivision Algorithm in Configuration Space for Finding Path with Rotation. IEEE Trans System, Man Cybernetics, 1985, 15(2):224~233.
[14]于红斌,李孝安.基于栅格法的机器人快速路径规划.微电子学与计算机, 2005, 6(22):98~100.
[15]李宏超黄亚楼阙嘉岚等.基于四叉树环境模型的轮式移动机器人平滑路径生成方法.机器人, 2001, 23(5):32~36.
[16]邰宜斌.一种机器人路径规划的新方法.上海交通大学报. 1996, 30(4):94~100.
[17]朱嘉钢. A*算法中引入前视机制的探讨.无锡轻工大学学报, 2001, 20(5):531~533.
[18]蒋新松.机器人学导论.辽宁科学技术出版社, 1994:511~516,543~554.
[19] Ames L. Crowly. Navigation for an intelligent mobile robot. IEEE Journal of Robotics and Automation, 1985, 1(1):31~40.
[20]袁曾任,姜焕东.智能移动机器人的一种全局路径规划方法和基于知识的路径控制器.机器人, 1992, 14(2):25~30.
[21]霍迎辉,张连明,杨宜民.移动机器人路径规划的最短切线路径算法.广东自动化与信息工程, 2003, 1(5):45~48.
[22] Franz. Aurenhammer. Voronoi Diagrams-A Survey of Fundamental Geometric Data Structure. ACM Computing Surveys, 1991, 23(1):345~495.
[23]范红.一种基于APF的点式移动机器人全局路径规划方法.科技通报, 2003, 19(4):285~287.
[24]张棋,杨宜民.基于改进人工势场法的足球机器人避碰控制.机器人, 2002 ,24(1):12~15.
[25]王会丽,傅卫平,方宗德等.基于改进的势场函数的移动机器人路径规划.机床与液压, 2002,1(6):67~69.
[26]赵晓东,王树国,严艳军等.障碍环境下空间机器人的路径规划算法及仿真.高技术通讯, 2003,13(6):54~58.
[27]张培艳,吕恬生.基于模拟退火-人工势场法的足球机器人路径规划研究.机械科学与技术, 2003, 4(9):31~34.
[28]杨明,王宏,何克忠.基于激光雷达的移动机器人环境建模与避障.清华大学学报(自然科学版) , 2000, 40(7):112~116.
[29] S.S. Ge, Y. J. Cui. New Potential Functions for Mobile Robot Path Planning. IEEE Trans on Robotics and Automaton, 2000, 16(5):615~620.
[30]王小平,曹立明.遗传算法-理论、应用与软件实现.西安:西安交通大学出版社, 2002, 1~16.
[31]周明,孙树栋,彭炎午.基于遗传模拟退火算法的机器人路径规划.航空学报, 1998, 19(1):118~120.
[32]张乃尧,阎平凡.神经网络与模糊控制.北京:清华大学出版社, 1998,58~62.
[33]王士同.神经模糊系统及其应用.北京:北京航空航天大学出版社, 1998,49~54.
[34]王凌.智能优化算法及其应用.北京:清华大学出版社,2001,39~43.
[35]孙增圻.智能控制理论与技术.北京:清华大学出版社, 1997, 79~82.
[36]王仲民,姚立卿,张寒松.基于神经网络的移动机器人路径规划研究.天津职业技术师范学院学报, 2003, 3(1):10~12.
[37]谢宏斌,刘国栋,李春光.动态环境中基于模糊神经网络的机器人路径规划的一种新方法.江南大学学报, 2003,2(1):20~22.
[38]钟江生.自动导向小车路径规划问题的一种神经网络方法.五邑大学学报, 1999,13(3):15~18.
[39]朱咏杰,王树国,常疆.一种基于神经网络的移动机器人路径规划算法.高技术通讯, 2002, 9:42~45
[40]金海,谢卫. A*树搜索算法代价与误差关系的研究.软件学报, 1995, 6(3):155~158.
[41]唐平,杨宜民.动态二叉树表示环境的A*算法及其在足球机器人路径规划中的实现.中国工程科学,2002, 4(9):50~53.
[42]张纯刚.基于滚动窗口的移动机器人路径规划.系统工程与电子技术, 2002, 24(6):63~69.
[43]蔡自兴,贺汉根,陈虹.未知环境中移动机器人导航控制问题.计算机科学, 2002, 29(10):711~713.
[44] J. J. Leonard and H. F. Durrant-Whyte. Mobile Robot Localization by Tracking Geometric Beacons. IEEE Trans on Robotics and Automation, 1991, 7(3):376~382.
[45]高德平,黄学梅.多传感器数据融合.红外与激光工程, 1999, 28(2):14~17.
[46]张军宇,何克忠.智能机器人THMR-V的组合定位系统.计算机工程与应用, 2001,15:68~71.
[47]王密,郭丙轩,雷霆等.车载GPS导航系统中GPS定位与道路匹配方法研究.武汉测绘科技大学学报, 2000, 25(3):248~256.
[48] G. Foux, M. Heymann, A. Bruckstein. Two-Dimensional Robot Navigation among Unknown Stationary Polygonal Obstacles. IEEE Transactions on Robotics and Automation, 1993, 9(1):96~102.
[49] C. Hofner, G. Schmidt. Path Planning and Guidance Techniques for an Autonomous Mobile Cleaning Robot. Robotics and Autonomous System. 1995, 14:199~212.
[50] G. Schmidt, C. Hofner. An Advanced Planning and Navigation Approach for Autonomous Cleaning Robot Operations. In IEEE/RSJ International Conference on Intelligent Robots and Systems, 1998, 2:1230~1235.
[51] Zingaretti Primo, Carbonate Antonella. Route Following Based on Adaptive Visual Landmark Matching. Robotics and Autonomous Systems 1998, 25(8):213~221.
[52] Y Yagi, Y Nishizawa, M Yachida. Map-Based Navigation for a Mobile Robot with Omnidirectional Image Sensor COPIS. IEEE Trans. Robotics and Automation, 1995, 11(5):104~118.
[53]肖为周,王炜,李修港等.基于GIS的城市公交规划信息系统的应用.中国地理信息系统协会论文集,1999:1001~1005.
[54]向怀坤,柴旭东,廖明军等.基于GPS,GIS与GSM开发车辆监控调度系统的研究.汽车工程, 2002,24(3):45~47.
[55]邹旭东,郑四发,班学钢等.具有交通限制约束的道路网络最优路径算法.公路交通科技, 2002, 11(4):31~35.
[56] R.C. Arkin. Cooperation without Communication: Multi-Agent Schema-Based Robot Navigation. Journal of Robotic Systems, 1992, 9(3):351~364.
[57] R.C. Arkin, T. Balch, E. Nitz. Communication of Behavioral State in Multi-Agent Retrieval Tasks. In Proceedings 1993 IEEE Conference on Robotics and Automation, Atlanta, GA, 1993, 23(2):216~223.
[58] T. Balch and R.C. Arkin. Communication in Reactive Multi-Agent Robotic Systems. Autonomous Robots 1995, 1(1):321~320.
[59]王月海,洪炳熔.机器人部队运动多目标合作追捕算法.西安交通大学学报, 2003, 37(6):573~576.
[60] Haynes Thomas, Sen Sandip. Evolving Behavioral Strategies in Predators and Prey. Lecture notes on Artificial Intelligence, Springer Verlag, Berlin, Spring 1996:1~14.
[2]张海英,刘祚时,林桂娟.群体机器人研究的现状和发展.电子技术应用, 2004, 2:1~3.
[3]王宏,艾海舟.移动机器人体系结构与系统设计.机器人, 1993, 15(1):49~54.
[4]卢韶芳,刘大维.自主式移动机器人导航研究现状及其相关技术.农业机械学报, 2002, 33(2):112-116.
[5]王天然.一种开放式移动机器人体系结构.机器人, 1995. 17(5):193-199.
[6] W Burgard, M Moors, D Fox et al. Collaborative Multi-Robot Exploration. Proceedings of the IEEE International Conference on Robotics and Automation, 2000:476~481.
[7] Y U Cao, A. S. Fukunaga, A. B. Kahng. Cooperative Mobile Robotics: Antecedences and Directions. Autonomous Robots, 1997. 4(1):7~27.
[8] G. Dudek, M. Jenkin, E. E. Milios et al. A Taxonomy for Multi-Agent Robotics. Autonomous Robots, 1996. 3(4):375~397.
[9]李实,徐旭明,叶榛等.国际机器人足球比赛及其相关技术机器人.机器人, 2000,22(5):20~26.
[10]顾国昌,李亚波.基于总体势减小的动态调度技术解决多机器人的路径规划.机器人, 2001, 23(2):172~174.
[11]郑大钟.线性系统理论.北京:清华大学出版社, 1990, 57~59.
[12] PerezT Lozano. Spatial Planning: A Configuration Space Approach, IEEE Trans Computers, 1983, 32(2):108~120.
[13] R. A. Brooks, PerezT Lozano. A Subdivision Algorithm in Configuration Space for Finding Path with Rotation. IEEE Trans System, Man Cybernetics, 1985, 15(2):224~233.
[14]于红斌,李孝安.基于栅格法的机器人快速路径规划.微电子学与计算机, 2005, 6(22):98~100.
[15]李宏超黄亚楼阙嘉岚等.基于四叉树环境模型的轮式移动机器人平滑路径生成方法.机器人, 2001, 23(5):32~36.
[16]邰宜斌.一种机器人路径规划的新方法.上海交通大学报. 1996, 30(4):94~100.
[17]朱嘉钢. A*算法中引入前视机制的探讨.无锡轻工大学学报, 2001, 20(5):531~533.
[18]蒋新松.机器人学导论.辽宁科学技术出版社, 1994:511~516,543~554.
[19] Ames L. Crowly. Navigation for an intelligent mobile robot. IEEE Journal of Robotics and Automation, 1985, 1(1):31~40.
[20]袁曾任,姜焕东.智能移动机器人的一种全局路径规划方法和基于知识的路径控制器.机器人, 1992, 14(2):25~30.
[21]霍迎辉,张连明,杨宜民.移动机器人路径规划的最短切线路径算法.广东自动化与信息工程, 2003, 1(5):45~48.
[22] Franz. Aurenhammer. Voronoi Diagrams-A Survey of Fundamental Geometric Data Structure. ACM Computing Surveys, 1991, 23(1):345~495.
[23]范红.一种基于APF的点式移动机器人全局路径规划方法.科技通报, 2003, 19(4):285~287.
[24]张棋,杨宜民.基于改进人工势场法的足球机器人避碰控制.机器人, 2002 ,24(1):12~15.
[25]王会丽,傅卫平,方宗德等.基于改进的势场函数的移动机器人路径规划.机床与液压, 2002,1(6):67~69.
[26]赵晓东,王树国,严艳军等.障碍环境下空间机器人的路径规划算法及仿真.高技术通讯, 2003,13(6):54~58.
[27]张培艳,吕恬生.基于模拟退火-人工势场法的足球机器人路径规划研究.机械科学与技术, 2003, 4(9):31~34.
[28]杨明,王宏,何克忠.基于激光雷达的移动机器人环境建模与避障.清华大学学报(自然科学版) , 2000, 40(7):112~116.
[29] S.S. Ge, Y. J. Cui. New Potential Functions for Mobile Robot Path Planning. IEEE Trans on Robotics and Automaton, 2000, 16(5):615~620.
[30]王小平,曹立明.遗传算法-理论、应用与软件实现.西安:西安交通大学出版社, 2002, 1~16.
[31]周明,孙树栋,彭炎午.基于遗传模拟退火算法的机器人路径规划.航空学报, 1998, 19(1):118~120.
[32]张乃尧,阎平凡.神经网络与模糊控制.北京:清华大学出版社, 1998,58~62.
[33]王士同.神经模糊系统及其应用.北京:北京航空航天大学出版社, 1998,49~54.
[34]王凌.智能优化算法及其应用.北京:清华大学出版社,2001,39~43.
[35]孙增圻.智能控制理论与技术.北京:清华大学出版社, 1997, 79~82.
[36]王仲民,姚立卿,张寒松.基于神经网络的移动机器人路径规划研究.天津职业技术师范学院学报, 2003, 3(1):10~12.
[37]谢宏斌,刘国栋,李春光.动态环境中基于模糊神经网络的机器人路径规划的一种新方法.江南大学学报, 2003,2(1):20~22.
[38]钟江生.自动导向小车路径规划问题的一种神经网络方法.五邑大学学报, 1999,13(3):15~18.
[39]朱咏杰,王树国,常疆.一种基于神经网络的移动机器人路径规划算法.高技术通讯, 2002, 9:42~45
[40]金海,谢卫. A*树搜索算法代价与误差关系的研究.软件学报, 1995, 6(3):155~158.
[41]唐平,杨宜民.动态二叉树表示环境的A*算法及其在足球机器人路径规划中的实现.中国工程科学,2002, 4(9):50~53.
[42]张纯刚.基于滚动窗口的移动机器人路径规划.系统工程与电子技术, 2002, 24(6):63~69.
[43]蔡自兴,贺汉根,陈虹.未知环境中移动机器人导航控制问题.计算机科学, 2002, 29(10):711~713.
[44] J. J. Leonard and H. F. Durrant-Whyte. Mobile Robot Localization by Tracking Geometric Beacons. IEEE Trans on Robotics and Automation, 1991, 7(3):376~382.
[45]高德平,黄学梅.多传感器数据融合.红外与激光工程, 1999, 28(2):14~17.
[46]张军宇,何克忠.智能机器人THMR-V的组合定位系统.计算机工程与应用, 2001,15:68~71.
[47]王密,郭丙轩,雷霆等.车载GPS导航系统中GPS定位与道路匹配方法研究.武汉测绘科技大学学报, 2000, 25(3):248~256.
[48] G. Foux, M. Heymann, A. Bruckstein. Two-Dimensional Robot Navigation among Unknown Stationary Polygonal Obstacles. IEEE Transactions on Robotics and Automation, 1993, 9(1):96~102.
[49] C. Hofner, G. Schmidt. Path Planning and Guidance Techniques for an Autonomous Mobile Cleaning Robot. Robotics and Autonomous System. 1995, 14:199~212.
[50] G. Schmidt, C. Hofner. An Advanced Planning and Navigation Approach for Autonomous Cleaning Robot Operations. In IEEE/RSJ International Conference on Intelligent Robots and Systems, 1998, 2:1230~1235.
[51] Zingaretti Primo, Carbonate Antonella. Route Following Based on Adaptive Visual Landmark Matching. Robotics and Autonomous Systems 1998, 25(8):213~221.
[52] Y Yagi, Y Nishizawa, M Yachida. Map-Based Navigation for a Mobile Robot with Omnidirectional Image Sensor COPIS. IEEE Trans. Robotics and Automation, 1995, 11(5):104~118.
[53]肖为周,王炜,李修港等.基于GIS的城市公交规划信息系统的应用.中国地理信息系统协会论文集,1999:1001~1005.
[54]向怀坤,柴旭东,廖明军等.基于GPS,GIS与GSM开发车辆监控调度系统的研究.汽车工程, 2002,24(3):45~47.
[55]邹旭东,郑四发,班学钢等.具有交通限制约束的道路网络最优路径算法.公路交通科技, 2002, 11(4):31~35.
[56] R.C. Arkin. Cooperation without Communication: Multi-Agent Schema-Based Robot Navigation. Journal of Robotic Systems, 1992, 9(3):351~364.
[57] R.C. Arkin, T. Balch, E. Nitz. Communication of Behavioral State in Multi-Agent Retrieval Tasks. In Proceedings 1993 IEEE Conference on Robotics and Automation, Atlanta, GA, 1993, 23(2):216~223.
[58] T. Balch and R.C. Arkin. Communication in Reactive Multi-Agent Robotic Systems. Autonomous Robots 1995, 1(1):321~320.
[59]王月海,洪炳熔.机器人部队运动多目标合作追捕算法.西安交通大学学报, 2003, 37(6):573~576.
[60] Haynes Thomas, Sen Sandip. Evolving Behavioral Strategies in Predators and Prey. Lecture notes on Artificial Intelligence, Springer Verlag, Berlin, Spring 1996:1~14.