A practical pursuit-evasion algorithm: Detection and tracking

This paper presents a practical algorithm for evader detection and tracking using one or more pursuers. The solution employs two advanced data structures. The first one is the Rapidly-Exploring Random Tree (RRT). It is constructed randomly but evenly distributed to generate a roadmap that captures the connectivity of the free space. The second data structure is the k-dimensional tree (Kd-Tree). Upon completion of the RRTs construction, their vertices are inserted in a Kd-Tree. At the tracking phase, the Kd-Tree will be queried repeatedly for retrieving the set of potential locations to be used by each pursuer in order to monitor or track an evader. Thus, the usage of the Kd-Trce will reduce the querying cost, during tracking, to a logarithmic time. A lazy collision detection strategy is used to resolve collisions with obstacles at runtime. As a result unnecessary checks are eliminated and hence improving the system performance. Simulation results show the validity of the proposed algorithm.