Efficient Incremental Search for Moving Target Search
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 615-619.
Abstract
Incremental search algorithms reuse information from previous searches to speed up the current search and are thus often able to find shortest paths for series of similar search problems faster than by solving each search problem independently from scratch. However, they do poorly on moving target search problems, where both the start and goal cells change over time. In this paper, we thus develop Fringe-Retrieving A* (FRA*), an incremental version of A* that repeatedly finds shortest paths for moving target search in known gridworlds. We demonstrate experimentally that it runs up to one order of magnitude faster than a variety of state-of-the-art incremental search algorithms applied to moving target search in known gridworlds.Xiaoxun Sun, William Yeoh, Sven Koenig
@inproceedings{ijcai2009p108,
title = {Efficient Incremental Search for Moving Target Search},
author = {Sun, Xiaoxun and Yeoh, William and Koenig, Sven},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {615--619},
year = {2009},
url = {https://ijcai.org/proceedings/2009/108},
}
TY - CPAPER TI - Efficient Incremental Search for Moving Target Search AU - Sun, Xiaoxun AU - Yeoh, William AU - Koenig, Sven T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 615 EP - 619 UR - https://ijcai.org/proceedings/2009/108 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
