摘要翻译:
最近,一些研究人员发现,基于成本的A*满意搜索经常会遇到问题。虽然有人提出了一些“工作方法”来改善这一问题,但没有任何一致的努力来确定其根源。在本文中,我们认为其根源可以追溯到行动成本的巨大差异,这是在大多数规划领域中观察到的。我们表明,这种成本差异误导了a*搜索,这不是微不足道的细节或偶然现象,而是“基于成本的评价函数+系统搜索+组合图”概念的系统性弱点。我们证明了基于大小的评价函数的满意搜索在很大程度上不受这个问题的影响。
---
英文标题:
《Cost Based Satisficing Search Considered Harmful》
---
作者:
William Cushing and J. Benton and Subbarao Kambhampati
---
最新提交年份:
2011
---
分类信息:
一级分类: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中的材料。
--
---
英文摘要:
Recently, several researchers have found that cost-based satisficing search with A* often runs into problems. Although some "work arounds" have been proposed to ameliorate the problem, there has not been any concerted effort to pinpoint its origin. In this paper, we argue that the origins can be traced back to the wide variance in action costs that is observed in most planning domains. We show that such cost variance misleads A* search, and that this is no trifling detail or accidental phenomenon, but a systemic weakness of the very concept of "cost-based evaluation functions + systematic search + combinatorial graphs". We show that satisficing search with sized-based evaluation functions is largely immune to this problem.
---
PDF链接:
https://arxiv.org/pdf/1103.3687