logo标签列表

搜索和规划有什么区别？

artificial-intelligenceplanning
14
在人工智能领域，我现在正在阅读关于规划的内容。但是作为一名对AI不熟悉的人，我无法理解他们坚持“规划和搜索之间的区别”的要点。
我有类似于C / C ++的过程性编程知识，并且可以基于数据结构进行搜索。
而我也无法理解'Stuart Russell'在《人工智能：一种现代方法》中提供的Buy（ISBN0123654789）和Have（ISBN0123456789）的例子，其中他们给出了搜索一个十位数ISBN号需要进行100亿次动作的情况。
我的问题是，如何搜索一本书需要进行100亿次动作，而规划则不需要。
请查看我提供的这个答案。 - nbro
5个回答
15
Russell和Norvig并不是说搜索和规划是不同的事情。实际上，在我认为你谈到的那个部分（在蓝色版本的第10章中），他们说的恰恰相反：一个规划问题可以简化为一个搜索问题。
但是，表示为搜索的计划可能具有巨大的搜索空间。在书中的例子中，有10^10种不同的可能动作，并且使用无信息搜索技术时，计算机“不知道”buy(x)会导致have(x)，即使这对人类来说显然很简单。因此，即使是单个动作计划的搜索空间也非常庞大。听起来很愚蠢，但这就是无信息搜索的定义。
因此，实际上有效的规划算法需要一些算法和/或启发式策略，这是该章节其余部分所描述的。在书中的例子中，改进的搜索从have(x)的目标向后推理，执行一些一阶逻辑模式列表，使用buy(x)与have(x)的联系，并得出正确的动作。
作为一则注记，我非常喜欢Russell和Norvig的书以及他们的工作。但是我发现规划章节有些薄弱。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

6

我不熟悉你提到的具体例子，但我会尽力解释。

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

规划是一种特殊类型的搜索：它是通过行动序列（或更普遍的偏序）空间进行搜索，以满足某些标准的计划。这并不意味着它必须作为搜索实现（就像一些可以使用搜索解决的问题可以用其他方法解决一样），但问题可以这样描述。

说通过ISBN查找书籍需要10亿个操作，这表明检查ISBN是其中之一的操作（因为有那么多可能的ISBN），但是通过规划（即找到适当的行动序列）将导致更少的操作（因为你就不需要检查所有的ISBN了？）。但是，没有问题的详细信息，我无法确定这种说法是否合理。

ISBN的例子被误用了。Russell和Norvig使用它来解释正向搜索和反向搜索之间的区别。 - decadenza
3
规划可以利用“回归搜索”，即从目标状态开始，“制定计划”以达到初始状态。
例如，对于您的图书示例，如果您以前提条件：购买（B），ISBN（B）开始，则可能有数百万种可能要找出（因为有数百万个ISBN号码），但是“您想要‘规划’如何达到目标状态而不仅仅是‘搜索’”
规划可提供达到目标状态所需的操作序列。搜索不涉及“操作”。
来源：Udacity AI 课程和 AIMA: Russel, Norvig
双向搜索的概念会发生什么变化？ 它允许我们同时进行正向和反向搜索。谈论第一段。 - Oluwayetty
1
在搜索和规划之间的主要区别是状态的表示方式。在搜索中，状态被表示为单个实体（可能是相当复杂的对象，但其内部结构不会被搜索算法使用）。而在规划中，状态具有结构化表示（属性的集合），这些表示将被规划算法使用。
0

简而言之，它们的区别在于：

  • 搜索是并行进行的，是一项声名狼藉的操作

  • 状态的表示：

    • 搜索状态被表示为单个实体，其内部结构未被使用
    • 规划状态具有结构化表示，由规划算法使用

  • 规划可以利用回归搜索

    • 即从目标开始，并从初始状态形成计划
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接