Интеллект, основанный на поведении

Ранние работы в области искусственного интеллекта были направлены на создание программ, имитирующих интеллект. Однако сегодня многие исследователи считают, что человеческий интеллект основан совсем не на выполнении сложных программ. Утверждается, что он базируется на эволюции поведения, гарантирующей выживание, поэтому интеллект лучше имитируется простыми функциями ответа на раздражения, например теми, которые моделируются искусственными нейронами. Эта теория объясняет, почему машины, разработанные на основе архитектуры фон Неймана, превосходят людей в навыках вычислений, но с трудом демонстрируют нечто похожее на здравый смысл. Таким образом, концепция эволюционного поведения обещает многое изменить в исследованиях искусственного интеллекта. Например, поведенческие модели применялись для создания роботов, которые умеют выполнять элементарные задачи благодаря развивающимся поведенческим навыкам, а не просто исполняя сложные программы. Еще один пример — область искусственных нейронных сетей, в которых системы обучаются вести себя определенным образом, а не просто программируются для выполнения заранее заданных вычислений.

Необходимо подчеркнуть, что так же, как из-за значительного количества возможных состояний мы не программировали все вероятные решения головоломки из восьми фишек, проблема размеров удерживает нас от явного представления всего графа состояний. Граф является способом выражения ближайших ходов, но не инструментом, который хотелось бы задать явно и полностью. Однако рассмотрение (и, возможно, расширение) части графа для головоломки из восьми фишек, изображенной на рис. 10.3, может оказаться полезным.

Если рассматривать проблему, с которой сталкивается система управления, в терминах графа состояний, она превращается в поиск последовательности стрелок, которые ведут от начального состояния в целевое. То есть эта последовательность стрелок представляет последовательность порождений, решающих исходную проблему. Таким образом, независимо от приложения, задачу системы управления можно считать задачей поиска пути в графе состояний. Это универсальное представление системы управления — главное, что мы получаем путем анализа проблемы, требующей применения мышления, в терминах продукционной системы. Если задачу можно описать в терминах продукционной системы, то ее решение можно сформулировать в терминах поиска пути.

Чтобы подчеркнуть этот важный вывод, представим, как другие задачи можно формализовать в терминах продукционных систем и, следовательно, в виде систем управления, ищущих пути в графах состояний. Одно из классических прило-

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

Возможно, менее очевидный пример продукционной системы — это проблема логических заключений из данных фактов. Порождения в этом контексте представляют собой логические правила, позволяющие формировать новые утверждения из старых. Например, предложение «Все супергерои благородные» и «Супермен — это супергерой» можно скомбинировать в предложение «Супермен благородный». Аналогично, фразу «Бэтмен и Робин умные» можно преобразовать в «Не Бэтмен или не Робин не умные». Состояния в такой системе включают набор предложений, правдивых в определенных точках процесса дедукции: начальное состояние — это набор основных утверждений (часто называемых аксиомами), из которых делаются выводы, а целевое состояние может быть любым набором утверждений, содержащих предполагаемое заключение.

В качестве примера на рис. 10.4 показана часть графа состояний, по которому можно пройти, чтобы получить утверждение «Сократ смертен» из набора утверждений «Сократ — мужчина», «Все мужчины — люди» и «Все люди смертны». Он демонстрирует нам основу изменчивости знаний: разум переходит из одного состояния в другое, когда процесс мышления генерирует дополнительные утверждения, применяя подходящие порождения.

Деревья поиска

Мы узнали, что работа системы управления включает поиск в графе состояний пути от начального узла к конечному. Простой способ выполнения такого поиска — проследовать по каждой стрелке, ведущей от начального состояния, и для каждого случая записать следующее состояние, затем пройти по стрелкам из этих новых состояний и опять записать результат, и т. д. Поиск цели расползается из начального состояния, как капля чернил в воде. Этот процесс продолжается, пока одно из новых состояний не окажется целевым, то есть пока не будет найдено решение, и системе управления потребуется просто применить порождения, найденные на пути от начального состояния к конечному.

Конечный результат применения такой стратегии — построение дерева, называемого деревом поиска (search tree), которое состоит из части графа состояний, исследованного системой управления. Корневой узел дерева поиска — это начальное состояние, а потомки каждого узла — это состояния, достижимые из родительского после применения одного порождения. Каждая дуга между узлами в дереве поиска обозначает выполнение одного порождения, а каждый путь от корня к листу — путь между соответствующими состояниями в графе состояний.

Дерево поиска, которое будет создано в ходе решения головоломки из восьми фишек из конфигурации, показанной на рис. 10.5, показано на рис. 10.6. Крайняя левая ветвь дерева представляет попытку решить задачу, сперва переместив фишку 6 вверх, центральная ветка обозначает решение, начатое с перемещения фишки 2 вправо, а крайняя правая ветвь представляет перемещение вниз фишки 5. Кроме того, дерево поиска показывает, что если начать с перемещения вверх фишки 6, то единственно возможным порождением на следующем шаге будет перемещение фишки 8 вправо. (В действительности на этом шаге можно передвинуть фишку 6 вниз, но это будет всего лишь откат предыдущего порождения, то есть лишний ход.)

Целевое состояние достигается на последнем уровне дерева поиска (рис. 10.6). Так как это означает, что решение найдено, система управления может прервать процедуру поиска и начать создание последовательности инструкций, которая будет использоваться для решения головоломки во внешней среде. Это представляет собой простой процесс прохождения по дереву поиска вверх от целевого узла и одновременного проталкивания всех встречающихся порождений, представляемых дугами дерева, в стек. Применение такой техники к дереву поиска на рис. 10.6 приведет к формированию стека порождений на рис. 10.7. Система управления теперь может решить головоломку во внешней среде, выполняя инструкции, выталкиваемые из стека.

Можно сделать еще одно наблюдение. Вспомните, что в деревьях, которые мы обсуждали в главе 7, использовалась система указателей, следуя которой, можно было пройти по дереву вниз, от родительских узлов к их потомкам. Однако в случае дерева поиска система управления должна перемещаться от потомков к их родителям, то есть от целевого состояния вверх по дереву к начальному состоянию. Указатели в таких деревьях указывают вверх, а не вниз. То есть в каждом узле-потомке есть указатель на его родителя, но в узлах-родителях нет указателей на их потомков. (В некоторых приложениях используются оба набора указателей, что позволяет перемещаться по дереву в обоих направлениях.)

Эвристика

Для нашего примера с рис. 10.6 мы выбираем начальную конфигурацию, из которой можно получить легко управляемое дерево поиска. Однако дерево поиска, созданное в попытке решить более сложную проблему, может оказаться намного больше. В шахматах существует 20 вариантов первого хода, и в таком случае у корневого узла дерева поиска будет 20 потомков, а не 3, как в случае головоломки из восьми фишек. Кроме того, шахматная партия может состоять из 30 или 35 пар ходов, а не из пяти простых ходов, как в нашем примере. Даже для случая головоломки из восьми фишек дерево поиска может существенно разрастись, если цель невозможно достигнуть быстро. Таким образом, создание полного дерева поиска может стать настолько же непрактичным, как и представление полного графа состояний.

Одна из стратегий разрешения этой проблемы — изменить порядок, согласно которому конструируется дерево поиска. Вместо построения дерева вширь (breadth-first), что означает, что дерево создается слой за слоем, мы можем пройти по самым многообещающим путям в дереве до максимальной глубины и перейти к другим вариантам только в случае, если эти первоначальные предпосылки окажутся ложными. Это называется построением дерева поиска в глубину (depth-first), то есть дерево создается путем построения вертикальных путей, а не горизонтальных слоев.

Метод построения в глубину схож со стратегией, которую мы, люди, применяем для решения головоломки из восьми фишек. Вряд ли мы постараемся выполнить несколько вариантов решения одновременно, как моделирует подход построения в ширину; вместо этого мы выберем способ решения, выглядящий наиболее привлекательно, и постараемся выполнить его до конца. Обратите внимание, что мы говорим «выглядящий привлекательным». Невозможно, находясь в определенной точке решения, абсолютно точно сказать, какой путь будет наилучшим. Мы просто следуем своей интуиции, которая, конечно же, может завести и в тупик. Несмотря на это, использование интуиции дает людям преимущество перед методами решения «в лоб», когда каждому варианту уделяется одинаковое внимание, и поэтому разумно применять интуитивные методы и в автоматических системах управления.

Теперь необходимо найти способ определения, какое из нескольких состояний выглядит наиболее многообещающим. Мы будем применять эвристику (heuristic) — это количественное значение, связанное с каждым состоянием, которое представляет собой попытку измерить «расстояние» от этого состояния до ближайшей цели. В каком-то смысле эвристика — это измерение намеченных затрат. Выбирая между двумя состояниями то, эвристическое значение для которого меньше, мы, вероятно, достигнем цели с меньшими затратами. Таким образом, это состояние отображает направление, в котором нам следует двигаться.

Эвристика должна оцениваться по двум показателям. Во-первых, она должна предъявить разумную оценку количества оставшейся работы, если соответствующее состояние будет достигнуто. Это означает, что должна быть предоставлена понятная информация, позволяющая выбрать один из вариантов, — чем лучше оценка, полученная при эвристическом анализе, тем лучше будут решения, основанные на этой информации. Во-вторых, эвристический анализ должен легко просчитываться, то есть его выполнение должно упростить процесс поиска, а не стать излишней нагрузкой. (Несмотря на то, что фактическое количество перемещений, необходимое для достижения цели из данного состояния, — это очень ценная информация, получение этой информации первым делом включает поиск самого решения.)

Простой эвристический анализ для головоломки из восьми фишек заключается в оценке «расстояния» до цели путем подсчета фишек, находящихся не на своем месте, — мы предполагаем, что состояние, когда четыре фишки занимают чужие места, находится дальше от цели (и поэтому менее привлекательно), чем состояние, когда только две фишки расположены неверно. Но такой анализ не учитывает, насколько далеко от своих мест находятся фишки. Если две фишки расположены далеко от своих позиций, для перемещения их по головоломке может потребоваться множество порождений.

Более точное значение получается при эвристическом анализе, когда измеряется расстояние от текущего положения каждой фишки до конечного, и эти значения складываются для получения единственной величины. Фишка, находящаяся рядом со своим конечным положением, даст расстояние, равное единице, тогда как фишка, угол которой соприкасается с квадратом, где она должна в итоге оказаться, связывается с расстоянием, равным двум (так как ее необходимо переместить на одно положение по вертикали и на одно по горизонтали). Такие вычисления проводятся легко и дают грубую оценку количества перемещений, необходимых для перевода головоломки из текущего состояния в конечное. Например, эвристическое значение для конфигурации на рис. 10.8 равно семи (так как фишки 2, 5 и 8 находятся на расстоянии, равном единице, от конечных позиций, а фишки 3 и 6 — на расстоянии, равном двум). Действительно, для решения головоломки из данного положения необходимо семь перемещений.

Теперь, когда мы нашли подходящий вариант эвристического анализа для головоломки, необходимо внедрить его в процесс принятия решений. Вспомните, что человек в такой ситуации обычно выбирает решение, выглядящее наиболее близким к цели. Таким образом, наша процедура поиска должна вычислить эвристическое значение для каждого листового узла дерева и произвести поиск, начиная с листа с наименьшим значением. Эта стратегия представлена на листинге 10.1, где показан алгоритм проектирования дерева поиска и применения полученного решения.

Листинг 10.1. Алгоритм системы управления с использование эвристики

Сделать начальный узел графа состояний корней дерева поиска и записать его эвристическое

значение. while (целевой узел не достигнут) do

[Из всех листовых узлов выбрать самый левый листовой узел с наименьшим эвристическим

значением. К этому узлу присоединить в качестве потомков все узлы, достижимые путем выполнения одного

порождения. Записать эвристические значения для каждого из этих новых узлов, соседствующих с узлом

в дереве поиска ] Пройти по дереву поиска от целевого узла к корню, проталкивая порождения, связанные с каждой

пройденной дугой, в стек. Решить исходную проблему, последовательно выталкивая из стека и выполняя порождения.

Теперь применим этот алгоритм к головоломке из восьми фишек, начиная с конфигурации на рис. 10.5. Сначала объявляем исходное состояние корневым узлом и записываем его эвристическое значение, равное пяти. Затем, выполнив первый проход структуры while, добавляем три узла, к которым можно перейти из начального состояния (рис. 10.9). Обратите внимание, что для каждого листового узла мы записали эвристические значения в круглые скобки.

Целевой узел не достигнут, поэтому мы еще раз проходим структуру while, на этот раз для самого левого узла («самый левый листовой узел с наименьшим эвристическим значением»). После этого дерево поиска переходит в состояние, показанное на рис. 10.10.

Теперь эвристическое значение самого левого листа равно пяти, указывая, что эта ветвь, возможно, не является наилучшим путем решения. Алгоритм понимает это, поэтому при следующем проходе обрабатывается самый правый узел (который теперь является «самым левым листовым узлом с наименьшим эвристическим значением»). Дерево поиска переходит в состояние на рис. 10.11.

Теперь кажется, что алгоритм идет по верному пути. Так как эвристическое значение для последнего узла равно трем, структура while указывает нам следовать по этому пути, и алгоритм поиска достигает цели, формируя дерево поиска, показанное на рис. 10.12. Сравнивая его с деревом, изображенным на рис. 10.6, мы видим, что даже с неверным шагом в самом начале выполнения алгоритма использование эвристической информации существенно уменьшило размер дерева поиска и сделало процесс поиска гораздо эффективнее.

После достижения целевого состояния выполнение структуры while прекращается, и мы переходим к прохождению дерева от целевого узла к корню, одновременно проталкивая соответствующие порождения в стек. Полученный стек был уже показан ранее на рис. 10.7. Наконец, необходимо выполнить порождения по мере выталкивания их из стека. Теперь мы увидим, как машина опустит манипулятор и начнет передвигать фишки.