Системы на предикатах

Системы на предикатах были исторически первыми интеллектуальными системами на логике. В них принятие решений производится на основе логического вывода с использованием языка исчисления предикатов первого порядка, рассмотренного в параграфе 2.3. Системы представляли собой логические программы, включающие предикатные базы знаний и машину вывода, которые могли быть реализованы, например, на языке Prolog, кратко описанном в параграфе 3.1. Программы включали обязательный интерпретатор этого языка, который по существу являлся машиной вывода, реализующей в процессе решения задач правила резолюции и унификации при формировании ответов на запросы.

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

Система должна управлять действами робота, который убирает пыль в комнате. Робот оснащен сенсором, который определяет, есть ли там какая-либо пыль, и пылесосом, который может быть использован для уборки пыли. Робот все время имеет четкую ориентацию (одну из обозначенных как north («север»), south («юг»), west («запад»), east («восток»)). В дополнение к способности убирать пыль робот может перемещаться вперед на один шаг или поворачиваться на 90°. Он перемещается по комнате, которая условно разделена сеткой на несколько ячеек одинакового размера (соответствующего единице перемещения робота).

С целью упрощения предположим, что комната имеет сетку 3×3 и робот (Р-У) стартует на квадрате сетки (0, 0) в направлении на «север» (рис. 6.1). Робот может получить сигнал наличия пыли Dirt (означающий, что где-то есть пыль) или Null (означающий, что нет никакой специальной информации). Он может выполнять любое одно из доступных действий: forward («вперед»), suck («убрать пыль»), turn («поворот»). Цель робота — пересекая комнату, постоянно искать пыль и удалять ее.

Рис. 6.1. Среда робота-уборщика.

На начальном этапе введем три простых предиката:

Гп (х, у) ;робот находится на (х, у)

Dirt (x, у) ;есть пыль на (х, у)

Facing (d) щаправление робота d.

Далее определим функцию next. Эта функция должна реагировать на сигналы очувствления, полученные от сенсоров (Dirt или Null), и вырабатывать новую базу данных, которая включает эту информацию. Она также должна удалять старую или неуместную информацию и определять новое положение и направление агента. Поэтому лучше определять функцию next по частям.

Сначала напишем old (N), чтобы определить «старую» информацию в базе данных, которую при обновлении можно удалить:

Далее необходимо определить функцию new, которая выдаст набор новых предикатов, которые надо добавить к базе данных. Эта функция должна генерировать предикаты: 1п (…), описывающий новую позицию агента, Facing (…), описывающий ориентацию агента, и Dirt (…), если пыль была обнаружена на новой позиции. Имея функции old и new, функцию next можно записать как.

Теперь можно перейти к новым правилам, которые определяют поведение робота. Дедуктивные правила имеют вид.

где (р и ф являются предикатами с некоторым произвольным списком констант и переменных. Идея заключается в том, что если ф соответствует базе данных агента, тогда Ф может быть решена для любых переменных, входящих в предикат ф.

Первое правило относится к основному действию очистки: оно имеет приоритет над всеми другими поведениями агента (такими как навигация).

Следовательно, если робот находится на позиции (х, у) и он видит пыль, тогда назначенным действием будет suck. В противном случае основным действием будет forward или turn. Подсоединим основной алгоритм навигации таким образом, что робот всегда будет двигаться от (0, 0) к (0, 1), к (0, 2) и потом к (1, 2), (1, 1) и т. д. Как только робот доходит до (2, 2), он переходит снова к (0, 0). Правила, относящиеся к перемещению вплоть до (0, 2), могут быть такие:

1п (0, 0) л Facing (north) л —iZ)wt (0, 0) —> Do{forward)

In (0, 1) л Fadngfnorth) л -Dirt (0, 1) —" Do (forward)

In (0, 2) л Facing (north) л -Dirt (0, 2) —> Do (tum)

//?((), 2) л Facing (east) —> Do (forward)

Заметим, что в каждом правиле необходимо явно проверять, не выполняется ли предшествующая часть первого правила. Это делается для того, чтобы быть уверенным, что всегда назначается только одно действие через предикат Do (…). Похожие правила могут быть выведены для случая, когда робот достигает (2, 2) и когда один раз переходит от (2, 2) к (0, 0). Эти правила совместно с функцией next обеспечивают требуемое поведение робота.

Рассмотрим вопрос о практичности такого подхода к построению агентов, основанных на логике. Предположим, что построен набор правил для робота р такой, что для любой базы данных Д, если возможно доказать Do (a), то тогда а является оптимальным действием, т. е. наилучшим действием, которое может быть выполнено при состоянии среды, описанным в базе Д. При запуске агента в момент t_{ робот вырабатывает некоторую базу данных и начинает применять свои правила р, для того чтобы найти действие, которое следует выполнить. Через некоторое время в момент t₂ ему удается вывести Д_t<_^_p Do (a) для некоторого действия а е А, и поэтому а является оптимальным действием, которое робот может выполнить в момент t₂. Но если состояние среды изменилось между t_t и t₂, то нет никакой гарантии того, что а все еще оптимально, особенно если прошло много времени между и t₂. Только если t₂ — t_{ бесконечно мало, т. е. принятие решения происходит практически мгновенно, то можно не обращать внимания на эту проблему. На практике принятие решения систем, основанных на логике, не будет мгновенным.

Принято считать, что логическая система на предикатах обладает свойством вычислительной рациональности, если ее блок принятия решения предлагает действие, которое было оптимально на момент начала процесса принятия решения. Ясно, что вычислительная рациональность неприемлема в среде, которая меняется быстрее, чем робот может принять решение [8]. Это — проблема чисто принятого здесь логического подхода. Уходя от языков, представляющих жесткую логику и состоящих из законченных наборов дедуктивных правил, можно построить системы, которые обладают приемлемыми характеристиками. Но в этом случае теряется преимущество логического подхода: простая и элегантная семантика.

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

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