摘要翻译：
实时启发式搜索算法适用于需要在恒定时间内做出决策的位置智能体。自从近20年前Korf的原始工作以来，已经提出了无数的扩展建议。最有趣的扩展之一是回溯的思想，其中代理决定返回到以前访问的状态，而不是贪婪地向前移动。经验表明，这一想法对各种业绩计量有重大影响。这些研究是在使用回溯的特定实时搜索算法的特定经验测试床上进行的。因此，观察到的趋势在多大程度上具有总体上的回溯特征尚不清楚。本文首次从理论上研究了实时启发式搜索中的回溯问题。特别地，在一个调节回溯量的参数中，我们给出了求解代价指数和线性的上界。这些结果适用于广泛的实时启发式搜索算法，其中包括许多现有的算法作为一个小的子类。
---
英文标题：
《On Backtracking in Real-time Heuristic Search》
---
作者：
Valeriy K. Bulitko and Vadim Bulitko
---
最新提交年份：
2009
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  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.
---
PDF链接：
https://arxiv.org/pdf/0912.3228