В чем разница между поиском и планированием

Рассел и Норвиг не говорят, что поиск и планирование - разные вещи. Фактически, в разделе, о котором, как мне кажется, вы говорите (в главе 10 Blue Edition), говорится прямо противоположное: проблема планирования может быть сведена к проблеме поиска.

Но план, выраженный как поиск, может иметь чудовищно большое пространство поиска. В примере с книгой существует 10 ^ 10 различных возможных действий, и при использовании неинформированной техники поиска компьютер не "знает", что покупка (x) приводит к получению ( x), хотя для человека это тривиально очевидно. Таким образом, даже простор для поиска разовых планов огромен. Звучит глупо, но это определение неосведомленного поиска.

В результате алгоритмы планирования, которые на самом деле работают, требуют некоторой алгоритмической и / или эвристической смекалки, которые будут описаны в оставшейся части этой главы. В примере с книгой улучшенный поиск направлен в обратном направлении от цели иметь (x), выполняет некоторый листинг схемы логики первого порядка с использованием соединения buy (x) vs have (x) и получает правильное действие.

Кстати, я большой поклонник книги Рассела и Норвига и их работ в целом. Но я обнаружил, что главы по планированию немного слабоваты. Профессора Лозано-Перес и Кельблинг делают свои записи лекций в классе, используя предыдущее издание книги в Интернете. Их записи очень подробны с примерами. Когда я изучал этот материал, я обнаружил, что они являются отличным дополнением:

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

Я не знаком с конкретным примером, который вы цитируете, но я все равно попробую.

Поиск - это почти полностью универсальная конструкция: существует пространство возможностей, и вы хотите найти его, но вы должны найти его, изучив (не обязательно надлежащее) подмножество. Существуют всевозможные подробности относительно конкретной проблемы поиска (например, что такое пространство, как вам разрешено запрашивать его и т. Д.) И конкретного алгоритма поиска (наиболее важно, как вы организуете, какие части пространства вы запрашиваете, в каких приказ). Практически ЛЮБАЯ проблема может быть представлена ​​как проблема поиска (каково пространство возможностей и как определить, какая из них желательна), поэтому она занимает такое видное место в ИИ.

Планирование - это особый вид поиска: это поиск в пространстве последовательностей действий (или, в более общем смысле, частичных заказов) плана, который удовлетворяет некоторым критериям. Это не означает, что он должен быть РЕАЛИЗОВАН как поиск (точно так же, как некоторые проблемы, которые можно решить с помощью поиска, могут быть решены другими способами), но проблему можно описать таким образом.

Утверждение, что поиск книги по ее ISBN потребует 10 миллиардов действий, предполагает, что проверка ISBN является одним из действий (поскольку существует много возможных ISBN), но каким-то образом планирование (то есть поиск подходящей последовательности действий) приведет к меньшему количеству действий (потому что тогда вам не нужно будет проверять все ISBN?). Но без подробностей проблемы я не могу сказать, насколько обоснованно это утверждение.

При планировании можно использовать регрессионный поиск, т.е. начать с состояния цели и сформировать план для достижения исходного состояния.

Для примера с вашей книгой, если вы начнете с ПРЕДПОСЫЛКИ: купить (B), ISBN (B), тогда у вас может быть миллион возможностей, на которые стоит обратить внимание (поскольку существует миллион номеров ISBN), но вы хотите «спланировать» < / i> как можно достичь состояния цели, а не просто "поиск"