搜索和规划有什么区别



在人工智能方面,我现在正在阅读有关规划的文章。但作为一个对人工智能的天真者,我无法理解他们坚持"计划和搜索之间的区别"的观点。

我有C/C++等过程编程知识,可以根据数据结构进行搜索。

而且我无法理解买入(ISBN0123654789)和 在"人工智能:现代"中给出(ISBN0123456789) 方法 - 斯图尔特·罗素",他们在其中给出,搜索十位数的 ISBN 数字将采取100亿次行动。

我的问题是,搜索一本书需要100亿次行动,但计划不需要。

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

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

因此,实际有效的规划算法需要一些算法和/或启发式的聪明,本章的其余部分将继续描述。 在本书示例中,改进的搜索原因从have(x)的目标向后,使用buy(x)与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

我不

熟悉你引用的具体例子,但我还是会尝试。

搜索几乎是一个完全通用的结构:有一个可能性的空间,你想找到一个,但你必须通过检查一个(不一定正确的)子集来找到它。 关于特定的搜索问题(即空间是什么,如何允许查询它等)和特定的搜索算法(最重要的是,如何以什么顺序组织空间的哪些部分),有各种各样的细节。 几乎任何问题都可以被提出为搜索问题(可能性的空间是多少,你如何判断哪个是理想的),这就是为什么它在人工智能中占有如此突出的地位。

计划

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

说通过 ISBN 查找一本书需要 100 亿次操作表明检查 ISBN 是其中一项行动(因为有很多可能的 ISBN),但不知何故计划(即找到适当的操作顺序)将导致更少的操作(因为您不需要检查所有 ISBN?)。 但是,如果没有问题的细节,我不能说这种说法有多合理。

计划可以利用回归搜索,即从目标状态开始,形成达到初始状态的计划。

以你的书为例,如果你从PRECONDITION:buy(B),ISBN(B)开始,那么你可能有一百万个可能性去寻找(因为有一百万个ISBN数字),但你想"计划"如何达到目标状态,而不仅仅是"搜索"。

计划为您提供达到目标状态所需的操作顺序。搜索与"操作"无关

资料来源:Udacity AI课程和AIMA:Russel,Norvig

搜索和规划之间的主要区别在于国家在搜索中,状态表示为单个实体(这可能是相当复杂对象,但其内部结构不被搜索算法使用)在规划中,各州具有结构化表示(属性集合)由计划算法使用

为了简短起见,区别在于:

  • 搜索是并行完成的,并且是一项非常不知名的操作

  • 各州代表:

    • 搜索状态表示为不使用其内部结构的单个实体
    • 计划
    • 状态具有计划算法使用的结构化表示形式
  • 规划可以利用回归搜索

    • 即从目标开始,从初始状态形成计划

最新更新