Generalized Fringe-Retrieving A*: faster moving target search on state lattices

Abstract

Moving target search is important for robotics applications where unmanned ground vehicles (UGVs) have to follow other friendly or hostile UGVs. Artificial intelligence re-searchers have recently used incremental search to speed up the computation of a simple strategy for the hunter. The fastest incremental search algorithm, Fringe-Retrieving A*, solves moving target search problems only on two-dimensional grids, which are rather unrealistic models for robotics applications. We therefore generalize it to General-ized Fringe-Retrieving A*, which solves moving target search problems on arbitrary graphs, including the state lattices used for UGV navigation.