Paper Info
Title
Moving Target Search with Subgoal Graphs.
Abstract
Moving Target Search (MTS) is a dynamic path planning problem, where an agent is trying to reach a moving entity with a minimum path cost. Problems of this nature can be found in video games and dynamic robotics, which require fast processing time (real time). In this work, we introduce a new algorithm for this problem - the Moving Target Search with Subgoal Graphs (MTSub). MTSub is based on environment abstraction and uses Subgoal Graphs to speed up searches without giving up cost minimal paths. The algorithm is optimal with respect to the knowledge that the agent has during the search. Experimental results show that MTSub meets the requirement of real time performance (e.g., 5 microseconds per step). Compared to G-FRA*, which is the best known dynamic algorithm so far, MTSub is up to 29 times faster in average time per step, and 186 times faster in maximum time per step. MTSub also compares fairly well against MtsCopa. Although in this case MTSub is up to 3.89 times slower in average response time and up to 6.81 times slower in maximum response time, it performed much better than MtsCopa in the processing phase - up to 220,000 times faster and requiring up to 44 times less space.
Year
Venue
Field
2015
International Conference on Automated Planning and Scheduling
Motion planning,Graph,Mathematical optimization,Moving target search,Computer science,Response time,Artificial intelligence,Dynamic problem,Robotics,Speedup
DocType
ISSN
Citations 
Conference
2334-0835
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Doron Nussbaum18913.49
Alper Yorukcu211.02