Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 123
Текст из файла (страница 123)
456 Часть И). Знания и рассуждения постного значения в текущем состоянии. Это означает, что следующее состояние полностью задано текущим состоянием и поэтому нет необходимости использовать дополнительные аксиомы окружения. В аксиоме состояния-преемника для местонахождения агента утверждается, что агент находится в квадрате у после выполнения некоторого действия, либо если это действие было возможным и заключалось в перемещении в квадрат у, либо если агент уже находился в квадрате у и его действие не заключалось в том, чтобы перемешаться куда-то в другое место: Розы(а, я) (Ас(лдепс, у, неып1с(а,ы)) а> а = Со(х, у) ы (АС(Адепе, у, я) л а Ы Со(у, я))) В аксиоме для флюентного предиката но1ддпд утверждается, что агент владеет золотом д после выполнения некоторого действия, если этим действием было схватывание золота д и такое схватывание было возможно или если агент уже владел золотом д и выполненное агентом действие не заключалось в отпускании золота: Розы(а, з) (Но1ддпд(д, Кези1С(а, ы) ) ьь а = ОсаЫд) и (Но1ддпд(д, ы) л а Ф Не1еаые(д) ) ) сй Аксиомы состояния-преемника позволяют решить проблему представительного окружения, поскольку общий размер этих аксиом измеряется величиной в 0(АЕ) литералов: каждый из е результатов каждого из А действий упоминается один и только один раз.
Литералы распределяются по Р разным аксиомам, поэтому аксиомы имеют средний размер АЕ/ Р. Внимательный читатель должен был заметить, что в этих аксиомах участвует флюентное высказывание Ас, касающееся агента, но не золота, поэтому мы все еще не можем доказать, что приведенный выше трехшаговый план позволяет достичь цели — переноса золота в квадрат (1, 1) . Мы должны указать, что Ъ. неявным результатом перемещения агента из квадрата х в квадрат у является то, что переместится также все золото, которое он несет (а также все муравьи, которые заползли в это золото, все пылинки и бактерии на этих муравьях и т.д.). Учет таких неявных результатов связан с решением так называемой 'в.
проблемы распространения последствий (гаппбсагюп ргоЫещ). Более подробно мы рассмотрим эту проблему позже, но для данной конкретной проблемной области ее можно решить, дописав более общую аксиому состояния-преемника для высказывания Ас. В новой аксиоме, которая обобщает предыдущую версию, утверждается, что объект о находится в квадрате у, либо если агент перешел в квадрат у и о — это или агент, или то, что держит агент, либо если объект о уже находился в квадрате у и агент никуда не переходил, притом что о является или агентом, или тем, что держит агент. Рояя(а, я) Ас(о, у, неяп1с(а ы) ) < > (а = до(х, у) л (о = Адепс ы но1ддпд(о, я) ) ) н (Ае(о, у, ы) л (Зяуя ы л а = Со(у, ы) л (о = Адепс н но1ддпд(о, ы) ) ) ) Возникает еще одна формальная сложность: процесс логического вывода, в котором используются эти аксиомы, должен позволять доказывать неравенства.
Про- Глава 10. Представление знаний 457 стейшего рода неравенство задается между константами, например лцепс~а,. Общая семантика логики первого порядка допускает, чтобы разные константы ссылались на один и тот же объект, поэтому база знаний должна включать какую-то аксиому, позволяющую предотвратить такую ситуацию. В Ж аксиоме уникальных имен (ип[г[ие патез ахют) провозглашается неравенство для каждой пары констант в базе знаний. Если же это условие подразумевается в программе автоматического доказательства теорем, а не записывается в базу знаний, то называется предположением об уникальности имен (ип[г)це панаев азьцгпрйоп).
Необходимо также сформулировать условие неравенства между термами действий, например, утверждение о том, что Со( [1,1], [1,2] ) — это действие, отличное отомо( [1, 2], [1, 1] ) или СгаЬ(С,). Прежде всего необходимо указать, что каждый тип действия является различным, т.е., например, что действие Со — это не действие ЫгаЬ. Для каждой пары имен действий А и и необходимо иметь: Затем требуется указать, что два терма действия с одним и тем же именем действия ссылаются на одно и то же действие тогда и только тогда, когда все участвуюшие в них объекты являются одинаковыми: л(хг,...,х ) = л(ю,...,зщ) сФ хг = ю л ...
л х Все эти аксиомы, вместе взятые, называются Ъ. аксиомами уникального действия (ипа]це асбоп ахют). Такая комбинация описания начального состояния, аксиом состояния-преемника, аксиом уникальности имен и аксиом уникального действия является достаточной для доказательства того, что предлагаемый план позволяет достичь цели. Решение проблемы выводимого окружения Аксиомы состояния-преемника позволяют решить проблему представительного окружения, но не проблему выводимого окружения.
Рассмотрим (-шаговый план р, такой, что Я„=дев ц1с (р, я,) . Чтобы определить, какие флюентные высказывания являются истинными в состоянии Я,, необходимо рассмотреть каждую из Р аксиом окружения в каждом из г временных шагов. Поскольку аксиомы имеют средний размер лд7 Р, это соответствует объему работы по логическому выводу, измеряемому величиной 0(лес) . Основной объем этой работы связан с копированием флюентных высказываний в неизменном виде из описания одной ситуации в описание слелуюшей.
Для решения проблемы выводимого окружения можно воспользоваться следующими двумя подходами. Во-первых, можно отбросить ситуационное исчисление и изобрести новую формальную систему для записи аксиом. Указанная задача была решена в таких формальных системах, как исчисление флюентных высказываний (Гшеп( са!сц!ш), Во-вторых, можно изменить механизм логического вывода таким образом, чтобы в нем аксиомы окружения обрабатывались более эффективно. На то, что должна существовать такая возможность, указывает сам факт, что трудоемкость этого простого подхода оценивается величиной 0(АЕ~); но почему она должна зависеть от количества действий А, если точно известно, какое именно действие выполняется в каждом временном шаге? Чтобы определить, как можно улучшить состояние дел, вначале рассмотрим формат аксиом окружения: Часть П!. Знания и рассуждения Рояя(а,я) Рг(леяизс(а,я)) <=т (а = А, и а = А2 ...) гР(я) а (аФА~) А (аФА4) Таким образом, в каждой аксиоме рассматриваются несколько действий, которые могут сделать это флюентное высказывание истинным, и несколько действий, которые могут сделать его ложным.
Мы можем формализовать такие истинностные преобразования, введя предикат РояеЕЕесс (а, Р,), означающий, что в результате действия а флюентное высказывание Е, становится истинным, и предикат ВГЕДЕЕЕЕСС ( а, Рг), ОЗНаЧаЮЩИй, ЧтО ПОСЛЕ ВЫПОЛНЕНИЯ ДЕйСтВИЯ а фЛЮЕНтНОЕ ВЫ- сказывание ег становитсЯ ложным. Это означает, что пРиведеннУю выше системУ аксиом можно переписать следующим образом: Рояя(а, я) Р,(неяснее(а,я)) ~о РояеЕЕесс(а,Р,) ч (Р,(я) А (геяеЕЕесе(а,Р,) РояЕЕЕесе(А1, Р,) РояЕЕЕесс(А, Р,) ГГеоЕЕЕесс(лм Р,) неяЕЕЕесе(А4, Р,) Ответ на вопрос о том, может ли такая операция формирования системы аксиом быть выполнена автоматически, зависит от точного формата аксиом окружения. Для того чтобы обеспечить использование подобных аксиом в эффективной процедуре логического вывода, необходимо провести три описанных ниже преобразования.
1. Проиндексировать преднкаты РояЕЕЕесс и Е(едЕЕЕесе по их первому параметру таким образом, чтобы после получения информации о действии, которое произошло в момент времени с, можно было бы найти его результаты за время 0(1) . 2. Проиндексировать аксиомы таким образом, чтобы после определения того, что е, представляет собой результат какого-то действия, мы могли найти аксиому для е, за время 0(1) . В таком случае не придется даже рассматривать аксиомы, касающиеся тех флюентных высказываний, которые не являются результатом данного действия.
3. Представить каждую ситуацию как предыдушую ситуацию плюс некоторая дельта. Таким образом, если ничего не изменяется от одного шага к другому, то не нужно вообще выполнять никакой работы. При использовании старого подхода требовалось выполнять объем работы 0(Е), вырабатывая утверждение для каждого флюентного высказывания Р, (ееяи2 с (а, я) ) из предыдуших ег ( я) утверждений. Поэтому в каждом временном шаге мы рассматриваем текущее действие, собираем данные о его результатах и обновляем множество истинных флюентных высказываний. Среднее количество таких обновлений в каждом временном шаге соответствует е, поэтому общая сложность измеряется величиной 0(ес) .
В этом и состоит решение проблемы выводимого окружения. Глава 1О. Представление знаний 459 Исчисление времени и событий Ситуационное исчисление вполне себя оправдывает, если существует единственный агент, выполняющий мгновенные, дискретные действия, а если действия имеют продолжительность и могут накладываться друг на друга, то ситуационное исчисление становится довольно громоздким. Поэтому мы будем рассматривать данные темы с помощью альтернативной формальной системы, известной под названием 'в. исчисление событий (ечеп( са!си)цз), которая основана на точках во времени, а не на ситуациях.
(Термины "событие" и "действие" могут использоваться как взаимозаменяемые. Неформально выражаясь, "событие" обозначает более широкий класс действий, включая те, в которых нет явного агента. С описанием такого класса проще справиться с помощью исчисления событий, а не ситуационного исчисления.) В исчислении событий флюентные высказывания становятся истинными или ложными в определенных точках во времени, а не в ситуациях, притом что само исчисление предназначено для того, чтобы с его помощью можно было формировать рассуждения, касающиеся интервалов времени. В аксиоме исчисления событий указано, что флюентное высказывание является истинным в какой-то момент времени, если действие, описываемое этим высказыванием, было инициировано некоторым событием в некоторый момент времени в прошлом и еще не закончено под влиянием какого-либо промежуточного события.
Отношения Тпдетаееа и Тегттпаееа играют примерно такую же роль, как и отношение Неьц1с в ситуационном исчислении; отношение Тптсуасеа (е, Е, с) означает, что возникновение события е во время с вызвало то, что флюентное высказывание Е стало истинным, а отношение Теггатпагеа(ы, Е, С) ОЗНаЧаст, ЧтО ВЫСКаЗЫВаНИЕ Е перестало быть истинным. Мы будем использовать прелнкат наррепя (е, с) для обозначения того, что событие е произошло во время с, и предикат С11ррес)(Е, с, с,) для обозначения того, что высказывание Е перестало быть истинным под влиянием некоторого события, происшедшего в какое-то время между с и с,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
