Агенты на основе логических схем
Агент на основе логической схемы представляет собой особую разновидность рефлексных агентов с поддержкой состояния, которые определены в главе 2. В этом агенте результаты восприятия становятся входными данными для последовательной логической схемы — сети из логических элементов, каждый из которых реализует какую-то логическую связку, и регистров, каждый из который хранит истинностное значение одного высказывания. Выходами этой логической схемы являются регистры, соответствующие действиям, например, выход Grab принимает значение true, если агент хочет что-то схватить. Если вход Glitter (блеск) связан непосредственно с выходом Grab, то агент хватает свою цель, где бы он ее не обнаружил (рис. 7.9).
Вычисления значений с помощью логических схем осуществляются по принципу обработки потока данных: на каждом временном интервале устанавливаются значения входных данных и по логической схеме распространяются сигналы. Каждый раз, когда некоторый логический элемент получает на входе все необходимые данные, он вырабатывает на выходе некоторое значение. Этот процесс весьма напоминает процесс прямого логического вывода в таком графе AND—OR.
В предыдущем разделе было указано, что агенты на основе логической схемы позволяют учитывать временнъ/е соотношения намного более успешно, чем пропозициональные агенты на основе логического вывода. Это связано с тем, что значение, хранящееся в каждом регистре, показывает истинностное значение соответствующего пропозиционального символа в текущий момент времени t, поэтому регистр не хранит отдельные копии этого значения для каждого отдельного интервала времени. Например, можно предусмотреть регистр Alive, который должен содержать значение true, если вампус жив, и false, если он мертв. Этот регистр соответствует пропозициональному символу Alive1, поэтому в каждом временном интервале он ссылается на разные высказывания. Внутреннее состояние этого агента (т.е. его память) поддерживается путем обратного подключения выхода некоторого регистра к той же схеме через линию задержки. Это позволяет доставить в схему информацию о состоянии регистра в предыдущем интервале времени. Один из примеров такой конструкции приведен на рис. 7.9. Значение регистра Alive формируется с помощью конъюнкции отрицания восприятия Scream и пропущенного через линию задержки значения самого регистра Alive. Действие, выполняемое этой схемой применительно к регистру Alive, можно представить в форме высказывания как следующую двухстороннюю импликацию:
Это высказывание означает, что вампус в момент времени t жив тогда и только тогда, когда в момент времени t не был слышен его жалобный предсмертный крик (такое состояние нельзя определить по крику в момент времени t-1), и он был жив в момент времени t-1. Предполагается, что при инициализации этой логической схемы значение регистра Alive устанавливается равным true. Поэтому значение регистра Alive остается истинным до тех пор, пока не раздается жалобный крик вампуса, после чего это значение становится ложным и остается таковым. Это — именно то, что требуется.
За местонахождением агента можно следить в основном с использованием такого же способа, с помощью которого мы следим за здоровьем вампуса. Для этого требуется иметь отдельный регистр ьХ/У для каждого значения х и у; его значение должно быть равным true, если агент находится в квадрате [х, у]. Однако логическая схема, которая присваивает значение регистру Lxy, является гораздо более сложной по сравнению с логической схемой для регистра Alive. Например, агент находится в квадрате [1,1] в момент времени t, если он, во-первых, был здесь в момент времени t-1 и либо не двинулся вперед, либо попытался двинуться, но ударился об стену; во-вторых, находился в квадрате [1,2], смотря вниз, и двинулся вперед; в-третьих, находился в квадрате [2,1], смотря влево, и двинулся вперед. Эти три условия можно описать с помощью следующего высказывания:
Схема для регистра Ь1Л показана на рис. 7.10. К каждому регистру местонахождения подключена аналогичная схема. В упр. 7.13, б предлагается спроектировать логическую схему для высказываний, касающихся ориентации.
Логические схемы, показанные на рис. 7.9 и 7.10, постоянно поддерживают правильные истинностные значения для регистров Alive и Lx,y. Однако необычным свойством логических высказываний, соответствующих этим схемам и регистрам, является то, что их правильные истинностные значения всегда можно проверить. С другой стороны, рассмотрим высказывание В4>4 о том, что в квадрате [4,4] чувствуется ветерок. Несмотря на то что истинностное значение этого высказывания остается постоянным, агент не сможет узнать это истинностное значение до тех пор, пока не посетит квадрат [4,4] (или не выведет логическим путем, что рядом с этим квадратом есть яма). Пропозициональная логика и логика первого порядка предназначены для того, чтобы с их помощью можно было автоматически представлять высказывания с истинными, ложными и неизвестными значениями, а логические схемы таким свойством не обладают: регистр для высказывания В4>4 обязан содержать хоть какое-то значение, либо true, либо false, даже несмотря на то, что истинные данные о том, каково его значение, еще не получены. Это означает, что значение в регистре вполне может оказаться неправильным, и это введет агента в заблуждение. Иными словами, в регистре должны быть представлены три возможных состояния (высказывание В4 /4 является заведомо истинным, заведомо ложным или имеющим неизвестное значение), но в нашем распоряжении для этой цели имеется только один бит.
Решение такой проблемы состоит в использовании двух битов вместо одного. Высказывание В4/ 4 будет представлено с помощью двух регистров, которые мы будем называть х(В44) и X(-iB4/4), где К обозначает "known" (известный). (Напомним, что это все еще просто символы со сложными именами, даже несмотря на то, что они выглядят как структурированные выражения!) Если оба регистра, i=C(B4/4) и i=C(-iB4/4), содержат ложное значение, то истинностное значение В4/4 неизвестно. (А если оба они содержат истинное значение, то в базе знаний есть ошибка!) С этого времени, каждый раз, когда в некоторой части логической схемы нужно будет использовать высказывание В4/4, вместо него будет применяться высказывание i=C(B4/4), а когда потребуется использовать -пВ4/4, вместо него будет служить i=C(-iB4/4). Вообще говоря, каждое потенциально неопределенное высказывание можно представить двумя высказываниями с оценкой знаний (knowledge proposition), которые позволяют определить, известно ли о том, что соответствующее высказывание является истинным, или известно, что оно ложно.
Примеры того, как использовать высказывания с оценкой знаний, будут вскоре приведены. Но вначале необходимо провести определенную работу, чтобы найти способ выяснения истинностных значений самих высказываний с оценкой знаний. Обратите внимание на то, что высказывание В4>4 имеет постоянное истинностное значение, а значения высказываний JFC(B4>4) и i=C(-iB4/4) изменяются по мере того, как агент больше узнает об этом мире. Например, высказывание к (В4,4) вначале является ложным, а затем становится истинным, как только появляется возможность определить, что высказывание В4/4 является истинным, т.е. после того, как агент переходит в квадрат [4,4] и обнаруживает ветерок. С тех пор оно продолжает оставаться истинным. Таким образом, справедливо следующее уравнение:
X(B4/4)t <=» Х(В4/4)t_1 v (Lt4/4 л Breeze*-) (7.6)
Аналогичное уравнение может быть составлено для высказывания к (-iB4,4)t. Теперь, после того как агент узнал, в каких квадратах чувствуется ветерок, он может заняться обнаружением ям. В отсутствии ямы в некотором квадрате можно быть уверенным тогда и только тогда, когда в отношении одного из соседних квадратов известно, что в нем не чувствуется ветерок. Например, имеет место следующее уравнение:
K(-.P4,4)t <=> i5C(-.B3l4)t v К(-,В4(3)Ь (7.7)
Задача определения того, что в некотором квадрате есть яма, является более сложной — для этого в одном из соседних квадратов должен чувствоваться ветерок, который нельзя приписать наличию других ям, как показывает следующее уравнение:
К(Рц)* (K(BZiA)t л 2С(-,Р2,4)Ь л -РГ(-,Рз,з)fc)
v (K(Bi3)t л К(-лРл,2)* л Ж-пРз.з)*) (7.8)
Хотя логические схемы для определения наличия или отсутствия ям являются довольно сложными, с?= в них имеется лишь постоянное количество логических элементов в расчете на каждый квадрат. Это свойство является существенным, если мы занимаемся созданием агентов на основе логической схемы, предназначенных для решения задач, масштабы которых могут увеличиваться в разумных пределах. А фактически это — свойство самого мира вампуса; среда называется проявляющей свойство локальности, если истинность каждого интересующего нас высказывания можно определить, рассматривая лишь постоянное количество других высказываний. Обоснованность классификации по признаку локальности очень сильно зависит от того, насколько точно определена "физическая структура" данной среды. Например, область определения задачи игры в минного тральщика (Minesweeper) (упр. 7.11) является нелокальной, поскольку, чтобы узнать, есть ли мина в данном квадрате, может потребоваться проверить квадраты, находящиеся от него на произвольном расстоянии. Поэтому агенты на основе логических схем не всегда практически применимы для нелокальных областей определения.
Осталась еще одна проблема, которую мы до сих пор тщательно обходили, — вопрос об ацикличности. Логическая схема является ацикличной, если каждый путь, соединяющий выход некоторого регистра в обратном направлении с его входом, содержит промежуточный элемент задержки. Мы требуем, чтобы все схемы были ацикличными, поскольку логические схемы, являющиеся цикличными, не работают как физические устройства! Они могут переходить в режим неустойчивых колебаний, что приводит к появлению неопределенных значений. В качестве примера цикличной схемы рассмотрим следующий дополненный вариант уравнения 7.6:
K(B4,4)t <=> i5C(B4,4)t"1 v (1Л,4 л Breeze*-) v K(P3.)t v K(PAi3)t (7.9)
Дополнительные дизъюнкты, K(P3iA)t и K{PAi3)t, позволяют агенту определить, чувствуется ли ветерок, на основании известных данных о наличии ям в соседних квадратах, и, на первый взгляд, в этом нет ничего предосудительного. Но, к сожалению, появление ветерка зависит от наличия ям в соседних квадратах, а наличие ям зависит от того, чувствуется ли ветерок в соседних квадратах, и такая связь устанавливается с помощью уравнений, подобных уравнению 7.8. Поэтому полная логическая схема будет содержать циклы.
Сложность здесь заключается не в том, что дополненное уравнение 7.9 стало неправильным. Скорее всего, проблема состоит в том, что промежуточные зависимости, представленные подобными уравнениями, невозможно разрешить с помощью распространения истинностных значений по соответствующим логическим схемам. Ациклическая версия схемы, составленной с использованием уравнения 7.6, которая определяет наличие ветерка только с помощью прямого наблюдения, является неполной в том смысле, что могут возникать такие ситуации, когда агент на основе логической схемы окажется менее осведомленным, чем агент на основе логического вывода, использующий полную процедуру логического вывода. Например, если чувствуется ветерок в квадрате [1,1], то агент на основе логического вывода может прийти к заключению, что ветерок чувствуется также в квадрате [2,2], а агент на основе ациклической логической схемы, использующий уравнение 7.6, на это не способен. Задача создания полной логической схемы выполнима (в конце концов, логические схемы дают возможность эмулировать любой цифровой компьютер), но такая схема окажется значительно более сложной по сравнению с ациклической логической схемой.