Computer Science – Artificial Intelligence
Scientific paper
2009-12-16
Computer Science
Artificial Intelligence
Scientific paper
Real-time heuristic search algorithms are suitable for situated agents that need to make their decisions in constant time. Since the original work by Korf nearly two decades ago, numerous extensions have been suggested. One of the most intriguing extensions is the idea of backtracking wherein the agent decides to return to a previously visited state as opposed to moving forward greedily. This idea has been empirically shown to have a significant impact on various performance measures. The studies have been carried out in particular empirical testbeds with specific real-time search algorithms that use backtracking. Consequently, the extent to which the trends observed are characteristic of backtracking in general is unclear. In this paper, we present the first entirely theoretical study of backtracking in real-time heuristic search. In particular, we present upper bounds on the solution cost exponential and linear in a parameter regulating the amount of backtracking. The results hold for a wide class of real-time heuristic search algorithms that includes many existing algorithms as a small subclass.
Bulitko Vadim
Bulitko Valeriy K.
No associations
LandOfFree
On Backtracking in Real-time Heuristic Search does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Backtracking in Real-time Heuristic Search, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Backtracking in Real-time Heuristic Search will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-49801