Reaching the Goal in Real-Time Heuristic Search: Scrubbing Behavior is Unavoidable
Full Text: 8941-38731-1-PB.pdf
Real-time agent-centered heuristic search is a well-studied problem where an agent that can only reason locally about the world must travel to a goal location using bounded computation and memory at each step. Many algorithms have been proposed for this problem, and theoretical results have also been derived for the worst-case performance. Assuming sufficiently poor tie-breaking, among other conditions, we derive theoretical best-case bounds for reaching the goal using LRTA*, a canonical example of a real-time agent-centered heuristic search algorithm. We show that the number of steps required to reach the goal can grow asymptotically faster than the state space, resulting in a “scrubbing†when the agent repeatedly visits the same state. This theoretical result, supported by experimental data, encourages recent work in the field that uses novel tie-breaking schemas and/or perform different types of learning.
Citation
N. Sturtevant, V. Bulitko. "Reaching the Goal in Real-Time Heuristic Search: Scrubbing Behavior is Unavoidable". Symposium on Combinatorial Search, (ed: Stefan Edelkamp, Roman Barták), pp 166-174, August 2014.| Keywords: | heuristic search, real-time, learning |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Sturtevant+Bulitko:SoCS14,
author = {Nathan R. Sturtevant and Vadim Bulitko},
title = {Reaching the Goal in Real-Time Heuristic Search: Scrubbing Behavior
is Unavoidable},
Editor = {Stefan Edelkamp, Roman Barták},
Pages = {166-174},
booktitle = {Symposium on Combinatorial Search},
year = 2014,
}Last Updated: July 09, 2020Submitted by Sabina P
