Waypoint Graph Based Fast Pathfinding in Dynamic Environment. (31st August 2015)

• Record Type: Journal Article
• Authors: Zhu, Weiping; Jia, Daoyuan; Wan, Hongyu; Yang, Tuo; Hu, Cheng; Qin, Kechen; Cui, Xiaohui
• Is Part Of: International journal of distributed sensor networks. Volume 11:Number 8(2015)
• Publication Date: 2015-08-31
• Subjects: Sensor networks -- Periodicals; Intelligent agents (Computer software) -- Periodicals; Multisensor data fusion -- Periodicals; 681.2
• DOI: 10.1155/2015/238727
• Languages: English
• ISSNs: 1550-1329

Abstract

Pathfinding is a fundamental task in many applications including robotics, computer games, and vehicle navigation. Waypoint graph is often used for pathfinding due to its advantage in specifying the space and obstacles in a region. Currently the waypoint graph based pathfinding suffers from large computation overhead and hence long latency in dynamic environment, where the location of obstacles may change. In this paper, we propose a fast approach for waypoint graph based pathfinding in such scenario. We eliminate unnecessary waypoints and edges to make the graph sparse. And then we design a prediction-based local method to handle the dynamic change in the environment. Extensive simulation has been done and the results show that the proposed approach outperforms existing approaches.