搜索和规划之间有什么区别

Question

在人工智能方面,我现在正在阅读规划.但作为人工智能的天真,我无法理解他们坚持"规划和搜索之间的差异".

我有程序编程知识,比如C/C++,我可以根据数据结构进行搜索.

我无法理解他们提供的'人工智能:现代方法 - 斯图尔特罗素'中给出的购买(ISBN0123654789)和拥有(ISBN0123456789)的例子,搜索十位数的ISBN号将需要100亿次操作.

我的问题是如何搜索一本书需要100亿次行动,但计划却没有.

Answer 1

Russell和Norvig并不是说搜索和计划是不同的事情.事实上,在我认为你正在考虑的部分(在蓝色版的第10章中),他们恰恰相反:规划问题可以简化为搜索问题.

但是,表示为搜索的计划可能会有一个巨大的搜索空间.在书的例子中,有10 ^ 10种不同的可能动作,并且使用不知情的搜索技术,计算机不"知道"购买(x)导致具有(x),即使这对于人类来说是微不足道的.因此,即使是单一行动计划的搜索空间也是巨大的.这听起来很愚蠢,但它是无知搜索的定义.

因此,实际工作的规划算法需要一些算法和/或启发式的聪明才能,本章的其余部分将继续描述.在本书示例中,改进的搜索原因从has(x)的目标向后,使用buy(x)vs have(x)连接执行一些一阶逻辑模式列表并导出正确的操作.

作为旁注,我非常喜欢拉塞尔和诺维格的书,以及他们的一般工作.但我发现计划章节有点弱.Lozano-Perez教授和Kaelbling教授在课堂上使用上一版本的在线课程进行了讲义.他们的笔记非常详细,有例子.当我研究这种材料时,我发现它们是一个很好的补充:

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-825-techniques-in-artificial-intelligence-sma-5504-fall-2002/index.htm

Answer 2

我不熟悉您引用的具体示例，但无论如何我都会尝试。

搜索几乎是一个完全通用的结构：存在一个可能性空间，您想定位一个，但您必须通过检查（不一定是正确的）子集来找到它。关于特定搜索问题（即空间是什么，你如何查询它等）和特定搜索算法（最重要的是，你如何组织你在什么空间中查询的空间部分）有各种各样的细节。命令）。几乎任何问题都可以作为搜索问题提出（可能性的空间是什么，以及如何判断哪个是所需的），这就是为什么它在 AI 中占有如此重要的地位。

计划是一种特殊的搜索：它是在动作序列空间（或更一般地说，偏序）中搜索满足某些标准的计划。这并不意味着它必须作为搜索来实现（就像一些可以使用搜索解决的问题可以用其他方式解决一样），但问题可以这样描述。

说根据 ISBN 查找一本书需要 100 亿次操作，这表明检查 ISBN 是其中一个操作（因为有很多可能的 ISBN），但不知何故计划（即找到合适的操作序列）将导致更少的操作（因为那么您就不需要检查所有 ISBN 了吗？）。但如果没有问题的细节，我不能说这种说法有多么合理。