An Indexed K-D Tree for Neighborhood Generation in Swarm Robotics Simulation

摘要：

　　In this paper, an indexed K-D tree is proposed to solve the problem of neighborhoods generation in swarm robotic simulation.The problem of neighborhoods generation for both robots and obstacles can be converted as a set of range searches to locate the robots within the sensing areas.The indexed K-D tree provides an indexed structure for a quick search for the robots neighbors in the tree generated by robots positions, which is the most time consuming operation in the process of neighborhood generation.The structure takes full advantage of the fact that the matrix generated by robots neighborhoods is symmetric and avoids duplicated search operations to a large extent.Simulation results demonstrate that the indexed K-D tree is significantly quicker than normal K-D tree and other methods for neighborhood generation when the population is larger than 10.

关键词： Neighborhood generation k-d tree simulation range search indexed k-d tree swarm robotics

作者: Zhongyang Zheng Ying Tan

作者单位: Key Laboratory of Machine Perception and Intelligence(Peking University),Ministry of Education Department of Machine Intelligence,School of Electronics Engineering and Computer Science,Peking Uni

会议类型: 国际会议

会议名称: 4th international Conference,ICSI2013(第4届群体智能国际会议)

会议地点: 哈尔滨

会议语种:英文

页码: 53-62

在线出版日期: 2013-06-12（万方平台首次上网日期，不代表论文的发表时间）