"ЖУРНАЛ РАДИОЭЛЕКТРОНИКИ" N 10, 2003 |
Об одном подходе к логическому программированию интеллектуальных агентов для поиска и распознавания информации в Интернет
А. А. Морозов; e-mail: morozov@mail.cplire.ruИнститут радиотехники и электроники РАНРабота поддержана РФФИ (гранты NN 00-01-0560 и 03-01-00256)
Получена 19 ноября 2003 г.
В статье рассмотрена проблема разработки интеллектуальных агентов для поиска и распознавания информации в Интернет. Изложен оригинальный подход к объектно-ориентированному логическому программированию агентов Интернет. Рассмотрена проблема обеспечения корректности логического вывода в условиях постоянного изменения информации в Интернет. Описан оригинальный математический аппарат для формализации модифицируемых рассуждений в Интернет. Рассмотрена модель параллельных вычислений, разработанная для логического программирования агентов Интернет. Рассмотрены средства логического программирования агентов Интернет на основе разработанного математического аппарата. СодержаниеВведение * 1. Постановка задачи и основная идея её решения * 2. Объектно-ориентированное логическое программирование интеллектуальных агентов * 2.1. Классы, миры и наследование * 2.2. Повторное доказательство логических акторов * 2.3. Доказательство логического актора в динамической среде Интернет * 2.4. Пример реализации логического агента Интернет * 3. Построение многоагентных логических систем * 3.1. Основные элементы модели параллельных асинхронных вычислений * 3.1.1. Процессы * 3.1.2. Сообщения * 3.1.3. Резиденты * 3.1.4. Пример графического описания агента * 3.2. Декларативная семантика многоагентных систем * 3.3. Принципы построения логических систем взаимодействующих агентов * 3.4. Визуальное программирование агентов Интернет * 4. Сравнение с другими подходами к декларативному программированию агентов Интернет * 4.1. Декларативная семантика агентов Интернет * 4.2. Визуальное программирование агентов Интернет с помощью функциональных диаграмм * 4.3. Параллельное программирование агентов * 4.4. Модифицируемые рассуждения в многоагентных системах * 4.5. Опережающие вычисления в многоагентных системах * Заключение * Список литературы * Приложение 1. Пример построения теоретико-модельной семантики параллельной программы * Приложение 2. Пример агента Интернет * Морозов Алексей Александрович * ВведениеВсё большему числу людей приходится регулярно осуществлять поиск и распознавание информации в Интернет. В зависимости от потребностей конкретного человека это занимает больше или меньше рабочего времени и требует тех или иных средств автоматизации поиска. Для многих людей поиск информации в Интернет пока что является редкой или разовой операцией, в том смысле, что человека либо совсем не интересует, либо интересует лишь от случая к случаю, как изменялась в дальнейшем информация по интересовавшей его теме. Такой "разовый" поиск в Сети автоматизируют общедоступные поисковые системы, основанные на лингвистических методах и поиске ключевых слов. Можно сказать, что задачи разового поиска и распознавания в Интернет поддаются решению с помощью классических методов распознавания [1] (в первую очередь, методов структурного распознавания), разработанных для других применений. Вместе с тем, по мере увеличения зависимости человека от информации, поступающей из Сети (её достоверности, своевременности, полноты и т.п.) поиск и распознавание информации в Интернет превращается из разовой операции в долговременный или даже постоянно протекающий процесс. Для автоматизации долговременного и постоянного поиска в Сети необходимо использовать специализированные прикладные программы ("интеллектуальные агенты Интернет"), которые отслеживают изменения информации, относящейся к области интересов конкретного пользователя. Агентами Интернет называют программы, автоматизирующие поиск, распознавание, извлечение и анализ информации во всемирной Сети, ориентированные на нужды конкретного пользователя (или группы пользователей). Агенты отличаются от используемых в настоящее время универсальных поисковых систем Интернет тем что:
В настоящее время не существует общепринятого определения агентов. Однако агентами принято называть программы, демонстрирующие свойства автономности, реактивности (реагирующие на внешние стимулы), проактивности (выполняющие действия по собственной инициативе), и (в случае многоагентных систем) обладающие социальным поведением [8,9]. Логическое программирование агентов Интернет является одним из наиболее интересных направлений в области поиска и распознавания информации в Сети, активно развиваемым в течение последнего десятилетия. Перспективность этого подхода была продемонстрирована в ряде исследовательских и коммерческих проектов (см. обзоры [12,14,40]). Показано, что логические языки, вследствие своих высоких выразительных и дедуктивных возможностей, являются удобным средством анализа сложных гипертекстовых структур Сети. Можно выделить следующие достоинства логического подхода к программированию агентов Интернет:
Однако главным достоинством логического программирования является то, что в рамках этого подхода существуют средства оценки математической строгости методов обработки информации, а именно теоретико-модельная семантика программ, а также понятия корректности и полноты логических программ. В последнее десятилетие было разработано большое количество методов и средств логического программирования агентов Интернет, основанных на различных модификациях и расширениях языка Пролог, а также неклассических логиках (линейной, модальной и др.) [8,10,12,40]. Тем не менее, до сих пор не был создан математический аппарат, который обеспечивал бы свойства корректности и полноты логических программ (агентов), работающих в динамическом внешнем окружении (т.е. в условиях постоянного изменения и пополнения информации в Интернет). Для решения этой проблемы мы разработали математический аппарат логического программирования агентов Интернет [40-44,46,47,49]. Созданный математический аппарат включает:
В рамках разработанной модели интеллектуальных агентов, агент Интернет (а также набор взаимодействующих агентов Интернет) описывается с помощью логической программы, исполняемой под управлением специальной стратегии, реализующей модифицируемые рассуждения с помощью так называемых повторных доказательств подцелей. В настоящей статье рассмотрены методы и средства объектно-ориентированного логического программирования интеллектуальных агентов, базирующиеся на разработанных нами аппарате модифицируемых рассуждений в динамической среде Интернет и объектно-ориентированном логическом языке Акторный Пролог. В разделе 1 рассмотрена проблема обеспечения корректности логического вывода в условиях постоянного изменения информации, описан оригинальный аппарат для формализации модифицируемых рассуждений в Интернет. В разделе 2 рассмотрены средства объектно-ориентированного логического программирования агентов Интернет. В разделе 3 рассмотрены средства логического программирования многоагентных (параллельных) систем поиска и распознавания. В разделе 4 рассмотренный подход сравнивается с другими подходами к логическому программированию агентов Интернет. 1. Постановка задачи и основная идея её решенияРассмотрим упрощённую модель логического интеллектуального агента, осуществляющего поиск и распознавание информации в Интернет. Рис. 1: Упрощённая модель интеллектуального агента Интернет.Предположим, что рассматриваемый агент - это некоторая логическая программа, обрабатывающая информацию из Сети и выдающая отчёты о собранных данных (рис. 1). В контексте такой модели агента необходимо обратить внимание на следующие ключевые вопросы:
Очевидно, что если агент работает с некоторыми заранее определёнными ресурсами или служит лишь для разовых операций поиска, в случае изменения данных в Сети для получения нового отчёта достаточно просто заново исполнить логическую программу. Однако если агент должен работать в течение длительных промежутков времени, сопоставимых со скоростью обновления данных в Сети, использование стандартного Пролога является математически некорректным, так как стандартная стратегия исполнения Пролога не обеспечивает корректность и полноту логического вывода в условиях изменения исходных данных. Названная проблема имеет и чисто практическую сторону. Перезапуск логической программы, исполнявшейся в течение длительного промежутка времени и самостоятельно осуществлявшей отбор необходимых ресурсов, будет означать бесполезное расходование вычислительных ресурсов и потерю собранной информации. Более того, повторное исполнение логической программы может оказаться вообще невозможным, так как часть необходимых ресурсов в данный момент может оказаться недоступным, что случается в Сети довольно часто. Таким образом, логическое программирование интеллектуальных агентов должно базироваться на некотором аппарате логического вывода, позволяющем вносить коррективы в исходные данные и выведенные на их основе высказывания, но при этом сохраняющем все остальные результаты. То есть, необходимо использовать некоторый аппарат модифицируемых рассуждений. Целью настоящей работы является создание такого аппарата, поддерживающего модифицируемые рассуждения в динамической среде Интернет. Разработанный нами аппарат является альтернативой немонотонным логическим системам. Его идею можно проиллюстрировать с помощью канонического примера про страуса Тити [2]. Запишем канонический пример двумя разными способами. Первый способ основан на использовании логической программы с оператором not, который является некоторой приближённой реализацией немонотонной логики.
При отсутствии в базе данных факта страус("Тити") доказательство утверждения not страус("Тити") завершится успехом, и Пролог выдаст Ответ = "да" - Тити может летать. Однако после добавления факта страус("Тити") это отрицание станет невыводимым, и Пролог ответит, что Тити летать не может. Второй способ основан на использовании разработанного нами аппарата логических акторов [34-36,38,39,49]. Логическими акторами мы называем подцели логической программы, которые могут доказываться повторно без отката логической программы. В дальнейшем мы будем обозначать логические акторы с помощью префикса @.
Эта программа делает то же самое, но принцип её работы иной. Отличие заключается в том, что модификации подлежит не текст программы, а текст запроса (текст целевого утверждения). Новая информация поступает не в виде логических высказываний, а в виде термов - новых значений переменных в целевом утверждении. Вот как это работает. В ходе исполнения логической программы актор @ проверка_отряда будет доказан как обычная подцель; Пролог выдаст результат Ответ = "да" и, кроме того, означит переменную Отряд = "обычный". В дальнейшем, если выяснится, что Тити - страус, эта информация должна быть передана в программу с помощью операции разрушающего присваивания Отряд := "страусы" Разрушающее присваивание, конечно, нарушит корректность логического вывода. Однако, после изменения значения переменной Отряд, механизм логических акторов автоматически восстановит корректность логического вывода путём повторного доказательства отдельной подцели - логического актора @ проверка_отряда. На этот раз в базе данных будет выбран факт проверка_отряда("страусы","нет"), и программа выдаст новый результат Ответ = "нет". Второй способ формализации обладает следующими достоинствами:
Реализация механизма логических акторов требует создания соответствующей стратегии логического вывода, поддерживающей повторное доказательство подцелей программы. В [38] доказано, что существуют такие стратегии, обладающие свойствами полноты (при условии отсутствия зацикливаний) и корректности. На основе разработанного подхода мы создали объектно-ориентированный логический язык Акторный Пролог [34,36,38,39,49]. В следующем разделе будут рассмотрены основные принципы логического программирования на Акторном Прологе, а также пример логического агента Интернет. 2. Объектно-ориентированное логическое программирование интеллектуальных агентовАкторный Пролог - это спроектированный и реализованный нами объектно-ориентированный логический язык. Исследовательской целью разработки этого языка является обобщение объектно-ориентированного подхода (ООП) в программировании, анализе и проектировании информационных систем на основе "чистых" логических средств, обеспечивающих строгую декларативную (теоретико-модельную) семантику объектно-ориентированных программ. Проблема соотношения логического и объектно-ориентированного программирования имеет давнюю историю и обширную библиографию (см., например, обзоры [6,7,11]). Исследуя эту область, мы пришли к выводу, что интуитивное программистское понятие "объект" не имеет однозначного соответствия в логике. При попытке перенести его в логическое программирование, оно распадается, по крайней мере, на три аспекта, каждый со своими выразительными возможностями, теоретическими проблемами и средствами реализации:
В разработанном нами языке Акторный Пролог выразительные возможности всех трёх аспектов ООП получили логическую интерпретацию в виде логических понятий и синтаксических средств. Для этих целей в Акторном Прологе используются:
Разработанные синтаксические средства являются видоизменёнными формулами логики предикатов первого порядка. Они являются логическими аналогами некоторых средств императивного программирования - классов, акторов, недоопределённых множеств, оператора разрушающего присваивания и др., но, в отличие от них, поддерживают строгую декларативную семантику программ. В этом разделе мы рассмотрим два основных средства Акторного Пролога - классы и логические акторы. Описание недоопределённых множеств можно найти в [34,39,49] или в определении языка [36]. 2.1. Классы, миры и наследованиеВ Акторном Прологе для управления топологией пространства поиска используется механизм классов. По аналогии с классами в императивном ООП, в Акторном Прологе введены синтаксические конструкции для структурирования текста программы - классы. Классом в языке называется набор логических предложений (фактов, правил). Так же как в императивном программировании, каждому классу соответствует уникальное имя, и все классы являются элементами некоторой иерархии наследования. Понятию "экземпляр класса" императивного программирования в Акторном Прологе также соответствует аналог. Экземплярами классов ("мирами") в Акторном Прологе называются конкретные применения классов. При этом, в Акторном Прологе отсутствует императивный оператор new (такой как, например, в C++). Экземпляры классов в Акторном Прологе создаются неявно, в результате конструктивного доказательства специальных формул, называемых конструкторами. Экземпляры классов служат составными частями пространства поиска во время исполнения программы. Экземпляр класса включает:
Механизм наследования в Акторном Прологе является аналогом подобных механизмов в императивных объектно-ориентированных языках, однако, он обеспечивает несколько иную операционную семантику: иерархия наследования определяет правила поиска предложений программы. Например, если в качестве пространства поиска для доказательства некоторого предиката p служит экземпляр класса A, то поиск соответствующего предложения с заголовком p будет осуществляться по очереди среди предложений класса A, затем среди предложений непосредственного предка класса A, и так далее, пока не будет найдено подходящее предложение, или пока не закончится иерархия наследования. Таким образом, в Акторном Прологе не происходит перекрытие предложений, определённых в суперклассах, хотя его можно смоделировать, используя нелогический оператор отсечения '!'. Кроме того, в Акторном Прологе не используется множественное наследование. У класса может быть лишь один непосредственный предок, так как иначе было бы непонятно, в каком порядке следует просматривать предложения родительских классов в ходе логического вывода. Слот - это переменная, доступная во всех предложениях экземпляра класса. Имена слотов называются атрибутами классов. Атрибуты необходимо объявлять во всех классах, в которых используются соответствующие слоты. В объявлении атрибутов могут быть заданы инициализаторы - термы языка, конструкторы или другие атрибуты, определяющие значения слотов. Пример определения класса:
Класс 'ADDER', изображающий полный двоичный сумматор, является непосредственным потомком класса 'DEVICE'. Атрибуты a, b и c1 обозначают слагаемые сумматора и входной бит переноса, sum и c2 - сумму и выходной бит переноса. Доказательство конструктора (конструктора экземпляра некоторого класса C) включает следующие стадии:
Доказательство конструктора считается успешным в том и только в том случае, если доказательство предиката goal во всех этих мирах закончилось успехом. Важное замечание: в последних версиях Акторного Пролога каждый автоматический вызов предиката goal сопровождается объявлением нового актора, то есть, при вызове предиката goal неявно используется префикс @. В приведённом выше примере конструктор ('ADDER', a= 1, b= 1, sum= Result) создаст новый экземпляр класса 'ADDER' и присвоит значение переменной Result=0. В Акторном Прологе в любой подцели предложения может быть явным образом указан мир, в котором должно быть выполнено доказательство соответствующего предиката. Для обозначения таких вызовов используется синтаксическая конструкция target ? p(A,B,C,...) - "исполнить процедуру p в мире target". В последних версиях Акторного Пролога мы ввели также синтаксические средства для объявления параллельных процессов. Эту возможность языка мы рассмотрим далее, в разделе, посвящённом программированию многоагентных логических систем поиска и распознавания. В [38] доказана теорема, устанавливающая математическую корректность механизма классов, рассмотренного выше. Теорема 2.1.1. Существуют глобальные синтаксические преобразования, сохраняющие операционную семантику программ, с помощью которых любая программа на Акторном Прологе без акторов, параллельных процессов и нелогических встроенных предикатов может быть преобразована в программу на чистом Прологе (или в формулу хорновского подмножества логики предикатов первого порядка). Таким образом, классы, миры, недоопределённые множества и другие синтаксические средства Акторного Пролога, отражающие структурный и информационный аспекты ООП, имеют стандартную теоретико-модельную семантику. 2.2. Повторное доказательство логических акторовИдея повторного доказательства подцелей и реализующая её стратегия логического вывода ("акторный механизм") являются наиболее интересными и важными элементами Акторного Пролога. Рис. 2: Взаимодействующие логические акторы.В Акторном Прологе логическая программа рассматривается как теорема, разделённая на логические акторы. Логические акторы - это повторно доказываемые подцели A1,...,AN (рис. 2), взаимодействующие через общие переменные V1,...,VM. Доказательство этой теоремы осуществляется в некотором объектно-ориентированном пространстве поиска, состоящем из отдельных миров W1,...,WK. Например, прямоугольник A4 на рисунке обозначает актор, подцели которого исполняются в мирах W2 и W3. Акторный механизм представляет собой расширение стандартной стратегии управления - в его основу положен стандартный "поиск слева направо в глубину с возвратом". Дополнительными возможностями акторного механизма являются повторное доказательство акторов и разрушающее присваивание значений общих переменных. Повторное доказательство акторов служит для обеспечения корректности и полноты логического вывода при изменении значений общих переменных с помощью разрушающего присваивания. Взаимодействие между акторами реализуется с помощью операции "корректного разрушающего присваивания", изменяющей значения общих переменных программы. В ходе этой операции осуществляется необходимое изменение значений общих переменных, а затем вызывается повторное доказательство акторов, зависящих от старых значений общих переменных. Если повторное доказательство всех этих акторов завершается успехом, исполнение операции также заканчивается успехом, в противном случае в логической программе происходит стандартный откат. Заметим, что, в общем случае, повторное доказательство любого актора может "затронуть" некоторые другие акторы и вызвать лавинообразный процесс устранения противоречий, возникших в системе. Подобное согласование логических акторов с помощью разрушающего присваивания осуществляется автоматически в момент успешного завершения доказательства каждого актора. Кроме того, оно может быть вызвано "вручную" с помощью специального встроенного предиката :=. Встроенный предикат := осуществляет разрушающее присваивание, изменяя значения общих переменных. Декларативная семантика этого предиката точно такая же, как у обычного равенства (унификации) = в чистом Прологе, однако операционная семантика этого предиката определяется акторным механизмом языка. Заметим, что повторное доказательство акторов не имеет никакого отношения к идее так называемого "интеллектуального отката". Отмена прежних результатов перед повторным доказательством актора не является разновидностью отката, потому что старые результаты доказательства не выбрасываются из стека (в отличие от операции отката). Таким образом, отменённые результаты доказательства могут стать снова "действующими", если в программе на Акторном Прологе произойдёт стандартный откат. Именно по этой причине идею повторных доказательств иногда называют "анти-бэктрэкингом". Необходимо отметить также, что в языке запрещено повторное доказательство тех акторов, доказательство которых в данный момент ещё не окончено. Это правило предотвращает рекурсивную отмену результатов доказательства акторов, которая могла бы привести к зацикливанию программы. Термин "актор" мы позаимствовали из акторной модели вычислений Хьюитта [3], однако механизм повторного доказательства подцелей реализует иной принцип взаимодействия между акторами. Вот основные отличия разработанной модели вычислений:
Детальное описание акторного механизма можно найти в определении Акторного Пролога [36]. Определение абстрактной машины последовательного Акторного Пролога приведено в [38]. Определение декларативной семантики программ на Акторном Прологе без параллельных процессов основано на теореме 2.1.1: Определение 2.2.1. Декларативной (теоретико-модельной) семантикой программы на Акторном Прологе без параллельных процессов и нелогических встроенных предикатов является декларативная семантика программы на чистом Прологе, соответствующей в смысле теоремы 2.1.1 исходной программе, после удаления всех префиксов @. В [38] доказаны следующие теоремы о корректности и полноте акторного механизма относительно декларативной семантики 2.2.1: Теорема 2.2.2. (о корректности акторного механизма) Стратегия управления Акторного Пролога с проверкой вхождения, без параллельных процессов и без нелогических встроенных предикатов является корректной. Теорема 2.2.3. (о полноте пространства поиска) Любая программа на Акторном Прологе без параллельных процессов и нелогических встроенных предикатов найдёт все существующие решения, если во время её исполнения не возникнут бесконечные вычисления. Программы на Акторном Прологе, использующие параллельные процессы, также имеют теоретико-модельную семантику специального вида, которая будет рассмотрена в разделе о многоагентных логических системах. Можно сказать, что все три аспекта ООП, рассмотренные выше, (структурный, динамический и информационный) реализованы в Акторном Прологе с помощью чистых логических средств, поддерживающих теоретико-модельную семантику программ. Акторный Пролог без нелогических встроенных предикатов является чистым логическим объектно-ориентированным языком, поддерживающим модифицируемые рассуждения. 2.3. Доказательство логического актора в динамической среде ИнтернетРассмотрим отдельный логический актор, в ходе исполнения которого используется информация, доступная в Интернет. Исполнение каждого отдельно взятого актора осуществляется под управлением стандартной стратегии Пролога ("поиск слева направо в глубину с возвратом"), которую можно изобразить графически в виде обхода соответствующего И-ИЛИ дерева программы (рис. 3). В ходе доказательства логический актор обращается к ресурсам Интернет R1-Rx. Предположим, что доказательство этой подцели закончилось успехом, а именно, в ходе логического вывода была успешно пройдена ветвь A-B-C. Это означает, что построенное доказательство зависит от ресурсов Интернет R2, R3, R5, использованных при прохождении ветви A-B-C, и не зависит от других ресурсов Интернет, к которым программа, возможно, обращалась при прохождении иных ветвей И-ИЛИ дерева. Следовательно, повторное доказательство рассматриваемого актора необходимо произвести (только) при изменении какого-либо из ресурсов R2, R3, R5, а все остальные ресурсы можно не учитывать. Рис. 3. И-ИЛИ дерево логического актора, доказываемого в Интернет.Предположим теперь, что доказательство актора завершилось неудачей. В этом случае значительно труднее определить, какие из использованных ресурсов Интернет оказали решающее влияние на результат доказательства, потому что при прохождении различных ветвей ИЛИ дерева использовались разные ресурсы, и, кроме того, сочетание данных из различных ресурсов Интернет могло повлиять на негативный результат при прохождении отдельных ветвей ИЛИ дерева. В общем случае, каждый из ресурсов Интернет R1-Rx мог повлиять на (неудачный) исход логического вывода. Таким образом, для осуществления корректного управления повторными доказательствами, в ходе доказательства логического актора необходимо запоминать:
Если текущая ветвь ИЛИ дерева приведёт к успеху, список ресурсов (1) можно забыть, а вот состояние ресурсов из списка (2) в дальнейшем необходимо отслеживать, чтобы при изменении любого из этих ресурсов осуществить повторное доказательство актора. В случае неудачи доказательства актора, для корректного управления повторным доказательством актора достаточно (хотя не всегда необходимо) отслеживать состояние всех ресурсов из списка (1). 2.4. Пример реализации логического агента ИнтернетПрограмма на Акторном Прологе создаёт множество логических акторов, связанных общими переменными друг с другом и с внешними информационными ресурсами. В случае изменения какого-либо из ресурсов Интернет, повторное доказательство всей логической программы не требуется, будут затронуты лишь некоторые акторы. Рассмотрим простой пример логического агента Интернет, решающего следующую задачу. Существует большое число международных и государственных организаций, разрабатывающих стандарты в области информационных технологий. На сайтах этих организаций регулярно публикуются предварительные варианты стандартов и другие электронные документы. Целью рассматриваемого ниже агента является регулярная проверка сайтов трёх конкретных организаций и уведомление пользователя об их изменении.
Целевое утверждение (1) программы указывает, что исполнение программы начинается с построения экземпляра класса 'Example2'. Класс 'Example2' (2-16) является прямым потомком предопределённого класса 'Report', реализующего управление текстовыми окнами. Экземпляр класса 'Example2' обладает тремя слотами node1, node2 и node3, содержащими экземпляры класса 'ResourceChecker'. Каждому экземпляру класса 'ResourceChecker' передаются три аргумента - название некоторой организации, её адрес в Интернет и ссылка на сам экземпляр класса 'Example2' (с помощью предопределённого слота self). Класс 'ResourceChecker' (17-36) является потомком предопределённого класса 'Receptor', реализующего взаимодействие программы с Интернет. Режим работы экземпляра класса 'Receptor' задаётся с помощью следующих слотов. Аргумент revision_period (21) задаёт повторную проверку ресурса Интернет, расположенного по адресу location, через каждые 3 дня. Аргумент max_waiting_time (22) означает, что если во время обращения к ресурсу ответ не придёт в течение 12 секунд, будет считаться, что обращение к ресурсу закончилось ошибкой. В каждом экземпляре класса 'ResourceChecker' создаётся актор goal (24). Он выполняет следующие действия: предикат get_parameters (25) возвращает параметры заданного ресурса Интернет, а предикат write_parameters (26) выводит на экран соответствующее сообщение. Принцип работы программы заключается в следующем: создаются три экземпляра класса 'ResourceChecker' и три соответствующих им актора goal. Каждый из акторов является логическим утверждением о некотором ресурсе Интернет. Это утверждение можно прочитать декларативно следующим образом: "Информация о текущем состоянии ресурса location выведена на экран". В терминах логического программирования можно сказать, что исполнение программы есть доказательство конъюнкции этих логических утверждений. При этом принципиальное отличие программы на Акторном Прологе от программы на стандартном Прологе состоит в том, что через некоторое время, когда состояние ресурсов Интернет изменится, логическая истинность утверждений программы на "обычном" Прологе будет нарушена. Однако, в отличие от стандартного Пролога, Акторный Пролог автоматически выявит произошедшее изменение ресурса (в приведённом примере - не позже чем через 3 дня) и восстановит корректность доказательства, повторно доказав те (и только те) акторы, ресурсы которых подверглись изменению. Таким образом, в отличие от стандартного Пролога, Акторный Пролог обеспечивает математическую строгость логического вывода в условиях изменения исходных данных. 3. Построение многоагентных логических системАгенты Интернет удобно конструировать из отдельных блоков - более мелких агентов (параллельных процессов), отвечающих за определённые частные задачи. Формулировка задачи в терминах взаимодействующих асинхронных процессов существенно упрощает создание и последующую модификацию агентов. Для программирования многоагентных логических систем мы разработали логическую объектно-ориентированную модель асинхронных вычислений и реализовали её в Акторном Прологе. В этом разделе будут рассмотрены основные идеи, лежащие в основе этой модели, а также принципы построения многоагентных логических систем на Акторном Прологе. 3.1. Основные элементы модели параллельных асинхронных вычисленийРазработанный нами принцип взаимодействия параллельных процессов является обобщением метода опережающих вычислений, применяемого в области искусственного интеллекта, а также для аппаратной реализации вычислительных устройств. Идея опережающих вычислений состоит в том, что некоторые ветви алгоритма могут быть исполнены заранее, ещё до того, как станет известно, понадобятся ли вычисленные данные для дальнейшего исполнения программы. Использование этой идеи совместно с математическим аппаратом логического программирования позволило нам избавиться от необходимости приостанавливать параллельные процессы для синхронизации. Вместо приостановки процессов мы используем модификацию логического вывода, в результате чего общая схема взаимодействия параллельных процессов выглядит следующим образом. Каждый процесс осуществляет вычисления с данными, доступными ему в настоящий момент. Если некоторые данные ещё не получены, процесс осуществляет вычисления с неполными данными. Как будет показано далее, разработанная стратегия исполнения логических программ является корректной относительно их декларативной семантики, поэтому любые результаты, полученные в ходе вычислений с неполными данными, будут корректными относительно декларативной семантики программы. Вычисление с неполными входными данными можно рассматривать как некоторую форму вычисления значений по умолчанию. В дальнейшем, при получении процессом новых или изменённых входных данных, осуществляется модификация проведённых вычислений и корректировка полученных ранее результатов. Модификация логического вывода в нашей модели вычислений основана на принципе повторного доказательства подцелей. Разработанная модель реализована в параллельной версии объектно-ориентированного логического языка Акторный Пролог, поэтому для упрощения изложения в этой статье мы будем использовать понятия и синтаксические обозначения этого языка. 3.1.1. ПроцессыПроцессом в параллельном Акторном Прологе называется экземпляр класса, предложения которого исполняются параллельно по отношению к предложениям других процессов. В Акторном Прологе процессы обозначаются с помощью двойных круглых скобок, в которые заключается конструктор экземпляра класса: (('ClassName', attribute1=Value1,..., attributeN=ValueN)) Передача информации между процессами в нашей модели осуществляется с помощью следующих механизмов:
Таким образом, процессы могут взаимодействовать через общие переменные, а также с помощью вызовов предикатов. Вот почему, в отличие от классической объектно-ориентированной модели вычислений, где используется только один вид сообщений, в нашей модели вычислений различаются два вида сообщений - "прямые" и "потоковые" сообщения. В результате обработки процессом полученного сообщения, его состояние изменяется. Период исполнения процесса, соответствующий обработке сообщения, называется "фазой" исполнения процесса. На каждой фазе исполнения процесса доказательство соответствующих ему подцелей доказательства (логических акторов) приводится в соответствие с информацией, поступившей извне. В зависимости от результатов повторного доказательства акторов, процесс переводится в одно из трёх состояний (см. рис. 4):
Примечание. В определении Акторного Пролога [36] дополнительно рассматривается ещё одно, вспомогательное, состояние, возникающее в ходе построения процесса. Рис. 4. Состояния процесса.Процесс, находящийся в состоянии "неиспользуемый", не осуществляет никаких операций, а все присланные ему сообщения накапливаются в буфере. С помощью неиспользуемых процессов агент изменяет свою структуру в ходе исполнения. 3.1.2. СообщенияОтличие между потоковыми и прямыми сообщениями состоит в следующем:
Перед отправлением прямых и потоковых сообщений все несвязанные переменные в составе соответствующих вызовов предикатов и термов заменяются специальной константой #. Это делается для того, чтобы предотвратить связывание переменных, принадлежащих различным процессам. Это преобразование не нарушает корректность логической программы относительно её декларативной семантики. Потоковые сообщения в Акторном Прологе обрабатываются следующим образом. При изменении значения общей переменной V, связывающей принимающий процесс P с другими процессами, в процессе P осуществляется разрушающее присваивание V := NewValue. Результатом этой операции становится повторное доказательство некоторых акторов процесса P. На рисунке 5 приведены графические символы, которые мы используем для обозначения потоковых сообщений. Рис. 5. Потоковые сообщения.Общие переменные, связывающие процессы, называются "портами". В нашей модели вычислений введены специальные средства для управления передачей потоковых сообщений. Процесс может объявить некоторое значение общей переменной "защищённым". В этом случае другим процессам будет запрещено присваивать этой переменной обычные ("незащищённые") значения. Защищённое значение общей переменной может быть заменено только другим защищённым значением. В Акторном Прологе для объявления защищённых значений общих переменных введено специальное ключевое слово protecting. Это ключевое слово задаётся в составе определений слотов экземпляров классов, а также в аргументах конструкторов процессов: (('ClassName',..., protecting: attributeN=ValueN,...)) Заметим, что в случае перехода процесса в состояние "неудачный" или "неиспользуемый", переданные им потоковые сообщения (в том числе защищённые) отменяются. Для этого через все порты процесса посылаются специальные "пустые" значения, которые в дальнейшем другие процессы могут заменить любыми защищёнными или незащищёнными значениями. Другое ключевое слово, suspending, используется для объявления так называемых "отключающих" портов. (('ClassName',..., suspending: attributeN=ValueN,...)) Отключающие порты служат для автоматического перевода процессов в состояние "неиспользуемый" и автоматического возвращения их из этого состояния. При получении через отключающий порт специальной константы # или "пустого" значения, процесс автоматически переводится в состояние "неиспользуемый". Когда значения всех отключающих портов процесса станут не равными # и "пустым" значениям, он автоматически вернётся в предыдущее состояние. Используя отключающие порты, можно создавать рекурсивные определения процессов, то есть, определения классов, рекурсивно включающие в себя конструкторы экземпляров того же класса. В общем случае, попытка создать экземпляр такого класса приведёт к построению бесконечно большого числа процессов и переполнению памяти компьютера. Однако использование отключающих портов позволяет осуществлять построение новых процессов постепенно, по мере поступления информации на отключающие порты соответствующих конструкторов. Таким образом, Акторный Пролог позволяет описывать системы из неограниченного числа процессов и создавать новые процессы по мере необходимости. Порты, которые не являются ни защищающими, ни отключающими, называются "простыми". На рисунке 6 приведены графические обозначения, которые мы используем для различных портов процессов. Рис. 6. Порты процессов.Прямые сообщения в нашей модели вычислений являются асинхронными, так же как и потоковые. В ходе исполнения предложений процесса, он может вызвать предикат в составе другого процесса (то есть, послать прямое сообщение) с помощью специальных операций отправления прямых сообщений: Target << predicate(A,B,...,C) Target <- predicate(A,B,...,C) Исполнение такой операции всегда заканчивается успехом и не влияет на дальнейшее исполнение посылающего процесса. Отправление прямых сообщений откладывается до окончания текущей фазы исполнения процесса и производится в том и только в том случае, если эта фаза завершится успехом. Кроме того, операции отправления прямых сообщений отменяются при откате логической программы. Инфикс << обозначает так называемые "информационные" прямые сообщения, а <- "переключающие" прямые сообщения. Эти разновидности прямых сообщений отличаются тем что:
На рисунке 7 приведены графические обозначения, которые мы используем для различных видов прямых сообщений. Рис. 7. Прямые сообщения.Заметим, что правила обработки потоковых сообщений соответствуют правилам обработки переключающих прямых сообщений, рассмотренным выше. Таким образом, потоковые сообщения можно назвать переключающими потоковыми сообщениями. 3.1.3. Резиденты"Резидентом" в нашей модели вычислений называется некоторая активная сущность, наблюдающая за состоянием заданного ("целевого") процесса и посылающая собранную информацию своему владельцу. Владельцем резидента является некоторый процесс. В Акторном Прологе резиденты определяются с помощью специальных формул вида slot = target_world ?? function(A,B,...,C) Такая формула может быть задана в качестве аргумента конструктора экземпляра класса или в качестве определения слота в составе класса. В общем случае, каждому резиденту программы соответствуют:
Резидент автоматически исполняет заданную функцию в пространстве поиска, соответствующем целевому процессу. Резидент создаёт список всех вычисленных значений функции, затем упорядочивает этот список и удаляет повторные элементы. После этого резидент посылает список значений функции своему владельцу в виде защищённого потокового сообщения. Резидент постоянно наблюдает за состоянием заданного целевого процесса. После каждого изменения состояния целевого процесса, резидент повторно осуществляет построение и передачу списка значений функции. Кроме того, резидент может получать информацию от своего владельца в виде потоковых сообщений, приходящих через аргументы соответствующей атомарной формулы. При получении новых значений аргументов, резидент также осуществляет повторное исполнение заданной функции и отправление собранной информации. Рис. 8. Резидент.На рисунке 8 приведено графическое обозначение резидентов, которое мы используем в нашей модели вычислений. 3.1.4. Пример графического описания агентаРассмотрим пример графического описания агента Интернет, собирающего данные с помощью поисковых машин Google и Rambler. На рисунке 9 изображена функциональная диаграмма, использующая рассмотренные выше обозначения. Рис. 9. Графическое описание агента Интернет.Процесс 1 осуществляет взаимодействие с пользователем. Он принимает список ключевых слов и посылает процессам 2 и 3 переключающее прямое сообщение, запускающее процесс поиска. Процессы 2 и 3 взаимодействуют с соответствующими поисковыми машинами и накапливают полученные адреса в локальных базах данных. Собранные адреса с помощью резидентов собираются в списки и в виде потоковых сообщений передаются в процесс 4. Процесс 4 объединяет списки адресов и передаёт их в процесс 5, который осуществляет дополнительную фильтрацию полученных ссылок. Необходимый метод проверки Веб страниц реализован в процессе 6. Обратите внимание, что процесс 6 передаёт в процесс 5 самого себя с помощью потокового сообщения, чтобы процесс 5 использовал его в качестве инструмента фильтрации. Список проверенных адресов передаётся в процесс 7, который показывает найденные адреса в диалоговом окне и позволяет пользователю просмотреть найденные ресурсы с помощью стандартного Веб браузера. В следующем разделе будет введена декларативная семантика рассмотренных элементов модели параллельных вычислений. 3.2. Декларативная семантика многоагентных системТеоретико-модельная семантика логических программ является важным инструментом оценки математической строгости реализуемых алгоритмов. С помощью теоретико-модельной семантики можно оценить:
Важным достоинством нашей модели вычислений является то, что она обеспечивает существование классической (то есть, основанной на логике предикатов первого порядка) теоретико-модельной семантики параллельных программ. Определение 3.2.1. Будем говорить, что логическая программа достигла успешного конечного состояния, если:
Определение 3.2.2. Результатом, вычисленным программой, мы будем называть значения общих переменных, связывающих процессы программы, достигшей успешного конечного состояния. Определение теоретико-модельной семантики будет дано следующим образом. Ниже будет определена схема преобразований произвольной параллельной логической программы P в последовательную программу P', для которой гарантировано существование классической теоретико-модельной семантики. Декларативная семантика программы P', будет принята в качестве семантики исходной программы P. Для построения искомой программы P' выполним следующие преобразования:
Примечание. В Акторном Прологе оператор == соответствует обычному равенству (унификации) = стандартного Пролога. Вспомогательный предикат ground_term является недетерминированным; он сопоставляет аргумент со всеми элементами эрбрановского универсума. Этот предикат необходим, чтобы гарантировать корректность использования оператора not в данной точке вычислений. В общем случае, этот предикат выдаёт бесконечное количество ответов, поэтому данное преобразование может привести к зацикливанию в случае использования стандартной стратегии исполнения программы. Однако в данный момент для нас имеет значение только наличие декларативной семантики программы.
Операция построения списка решений, возвращаемых функцией function(A,B,...,C), будет реализована по следующей схеме:
Вспомогательный предикат is_element проверяет, содержится ли значение Result в списке. Вспомогательный предикат sort упорядочивает элементы списка и удаляет из него повторяющиеся элементы. Для сортировки элементов списка будем использовать лексикографическое упорядочение. Вспомогательный предикат ground_term гарантирует корректность использования оператора not. В результате проведённых преобразований мы получим последовательную программу P' на чистом Прологе, расширенном оператором not. В языке Акторный Пролог оператор not не применяется (синтаксис языка не предусматривает использование этого оператора в тексте программ). Следовательно, в программе P' оператор not может использоваться только для моделирования рассмотренных выше специальных конструкций языка. Следовательно, P' является стратифицируемой, и значит, обладает классической теоретико-модельной семантикой. Определение 3.2.3. Теоретико-модельной семантикой параллельной программы P называется теоретико-модельная семантика последовательной программы P', построенной согласно правилам (1)-(7). В приложении 1 приведён подробный пример преобразования параллельной логической программы. Теорема 3.2.4. Параллельная логическая программа является корректной относительно своей теоретико-модельной семантики. Набросок доказательства. Рассматривая И-дерево программы P в ходе преобразований (1)-(7), можно убедиться, что оно может только сокращаться (конкретно, на шаге 1). Таким образом, И-дерево программы P' будет покрывать никак не меньше решений, по сравнению с программой P. То есть, программа P не может вычислить решения, не покрываемые программой P' (и, следовательно, некорректные относительно теоретико-модельной семантики). Конечно, в общем случае, параллельная программа P не обладает полнотой относительно своей теоретико-модельной семантики. Для обеспечения свойства полноты на синтаксис программы необходимо наложить ограничения. Теорема 3.2.5. Параллельная программа P является полной относительно своей теоретико-модельной семантики, если:
Набросок доказательства. Существует пять возможных причин неполноты параллельной программы относительно декларативной семантики. Первая причина - неполнота вычислений, осуществляемых внутри какого-либо процесса. Для устранения этой причины введены условия (1) и (3). Второй возможной причиной является невозможность передачи отката между процессами. Условия (5) и (6) гарантируют, что, если процесс вычислил и передал некоторое решение в другой процесс, другого решения не существует. Следовательно, в откате нет необходимости, так как он всё равно не помог бы найти другие решения. Третья возможная причина неполноты - замена несвязанных переменных константой #, осуществляемая при передаче информации между процессами. Эту причину устраняет условие (8). Четвёртая причина, это бесконечные вычисления, которые могут возникнуть в ходе исполнения программы. Такие зацикливания программы предотвращают условия (3), (4) и (7). Пятая возможная причина - наличие нескольких успешных конечных состояний у программы. Конкретно, у программы может оказаться несколько конечных состояний, если (a) в ней используются прямые сообщения, порядок обработки которых является, в общем случае, непредсказуемым; (b) между процессами осуществляется циклическая передача данных, и невозможно предсказать заранее, в каком порядке будут исполнены процессы, связанные общими переменными. Для предотвращения этих случаев введены, соответственно, условия (2) и (7). Следовательно, при выполнении перечисленных условий (1)-(8), программа будет полной относительно теоретико-модельной семантики. Таким образом, параллельные программы в нашей модели вычислений имеют не только операционную, но также теоретико-модельную семантику. Гарантируется корректность и, при определённых условиях, полнота программ относительно теоретико-модельной семантики. Это означает, в частности, что логический язык пригоден для написания параллельных программ, осуществляющих исчерпывающий перебор. Это позволяет сделать вывод, что разработанная модель параллельных вычислений и основанный на ней параллельный объектно-ориентированный логический язык математически строго реализуют принципы логического программирования. 3.3. Принципы построения логических систем взаимодействующих агентовРазработанная логическая объектно-ориентированная модель вычислений формирует определённый стиль программирования и принципы проектирования прикладных систем:
Логическая объектно-ориентированная модель асинхронных вычислений, в частности, хорошо сочетается с идеями визуального программирования средствами функциональных диаграмм и диаграмм потоков данных. 3.4. Визуальное программирование агентов ИнтернетМы разработали экспериментальные средства визуального логического программирования агентов Интернет. В их основе лежит использование SADT-диаграмм [5,37,38,49]. SADT-диаграммы являются разновидностью функциональных диаграмм и широко используются для анализа и проектирования сложных систем [5]. Система визуального программирования реализует следующую схему разработки интеллектуальных агентов:
|
Эксперименты с визуальным программированием показали, что SADT-диаграммы удобно использовать не только как визуальный язык программирования, но и просто в качестве графического интерфейса с пользователем. В настоящее время система визуального программирования автоматически создаёт визуальный интерфейс логической программы на основе исходной SADT-диаграммы (см. пример пользовательского интерфейса на рис. 11). |
Отдельные блоки визуального пользовательского интерфейса на основе SADT-диаграмм реализуются с помощью параллельных процессов Акторного Пролога. Как правило, каждый элементарный блок диаграммы имеет собственное диалоговое окно, открывающееся при нажатии на этот блок мышкой. Цвет блока автоматически изменяется в зависимости от состояния соответствующего ему процесса. Пользователь может взаимодействовать с блоками диаграммы в любом удобном для него порядке, в том числе повторно изменяя любые введённые ранее параметры. В новых версиях Акторного Пролога мы ввели так называемые "пакеты" и др. синтаксические средства, необходимые для реализации компонентно-ориентированного визуального программирования. В настоящее время реализован действующий прототип системы логического программирования интеллектуальных агентов Интернет на основе разработанного математического аппарата и языка Акторный Пролог. Использование средств визуального объектно-ориентированного логического программирования существенно упрощает создание, а также последующую поддержку и модификацию агентов Интернет. 4. Сравнение с другими подходами к декларативному программированию агентов ИнтернетРазработанный метод программирования агентов Интернет и модель параллельных вычислений воплощают несколько идей, каждая из которых требует отдельного рассмотрения и сопоставления с предложенными ранее подходами. 4.1. Декларативная семантика агентов ИнтернетХьюитт одним из первых отметил математическую некорректность использования стандартного Пролога для программирования распределённых информационных систем [4]. К сожалению, выявленная теоретическая проблема не была своевременно решена и до сих пор не учитывается многими исследователями. Некоторые перспективные подходы к изучению декларативной семантики распределённых систем были разработаны в области логического программирования взаимодействующих агентов. Ковальски и Сэдри [15] предложили расширение Пролога для программирования систем взаимодействующих агентов. Используя логические правила с параметром "время" и специальную процедуру доказательства, они разработали средства логического описания агентов с памятью, реагирующих на внешние события. В отличие от нашей модели вычислений, авторы рассматривают только взаимодействие с помощью логических высказываний, описывающих наблюдения агентов. В рамках указанного подхода рассматривается декларативная семантика отдельно взятых агентов, но при этом не обеспечивается декларативная семантика всей системы в целом. Костантини [16] предложила перспективный подход, позволяющий исследовать декларативную семантику системы взаимодействующих агентов в целом. В своей работе она использовала специальные синтаксические соглашения и механизм взаимодействия агентов, похожий на механизм информационных прямых сообщений в нашей модели асинхронных вычислений. 4.2. Визуальное программирование агентов Интернет с помощью функциональных диаграммИдея визуального программирования агентов Интернет с помощью функциональных диаграмм ранее была успешно реализована Москони и Порта. Разработанная ими система VIPERS [22] построена на основе специальной разновидности диаграмм потоков данных. По сравнению с нашей системой визуального программирования агентов, система VIPERS обладает более проработанным графическим интерфейсом, однако реализация блоков диаграмм осуществляется на императивном языке. Таким образом, система VIPERS не поддерживает декларативную семантику агентов Интернет и не решает вопросы математической строгости процедур поиска и распознавания информации в динамической среде Интернет. 4.3. Параллельное программирование агентовЦелесообразность использования потокового параллелизма для разработки языков программирования агентов Интернет была продемонстрирована также в проектах WebL Кистлэра и Мэйрэйса [23] (на основе комбинаторов Кадэли и Дэйвиза [24]), Webstream Хонга и Кларка [25], WebScript Занга и Кэшев [26], схемах получения информации Баиша и Кноблока [27]. Перечисленные языки программирования являются императивными и, таким образом, обладают тем же недостатком, что и упомянутая ранее система VIPERS. В области логического программирования Интернет также были разработаны модели параллельных вычислений, основанные на различных принципах взаимодействия агентов. Разработанные ранее логические языки программирования агентов Интернет, такие как concurrent LogicWeb Дэйвисона и Лока [13], W-ACE Понтэли и Гупты [17], Jinni Поля Таро [19], OZ [18], созданный под руководством Герта Смолки, DLP Илиёнса и Де Винка [21], ObjVProlog-D Мэйлэнфэнта, Лэйпэлма, Воче [29] и др. [12], обеспечивают существование декларативной семантики агентов, однако не поддерживают модификацию логического вывода в динамическом внешнем окружении и, следовательно, также не обеспечивают математическую строгость агентов Интернет. Дэйвисон и Лок [13] предложили модель параллельных вычислений, основанную на описании взаимодействующих процессов с помощью рекурсивных предложений (средствами параллельного логического языка Парлог). Отличительной особенностью разработанной модели являются гибкие средства обработки аварийных ситуаций, характерных для работы в Интернет. На основе разработанной модели авторы реализовали средства параллельного программирования в своей системе логического программирования Интернет LogicWeb [14]. Понтэли и Гупта [17] разработали систему логического программирования W-ACE, также основанную на описании процессов с помощью рекурсивных предложений. В языке W-ACE введены средства структурирования пространства поиска на основе модальных операторов. В отличие от проектов [13,17], в Акторном Прологе не используется описание процессов с помощью рекурсивных предложений, так как это, по нашему мнению, усложнило бы решение проблемы корректности логического вывода в условиях модификации исходной информации. Таро [20] разработал оригинальную модель параллельных вычислений на основе "флюентов" - интерпретаторов Пролога, передающих друг другу потоки найденных решений. Этот подход близок к механизму "асинхронного рандеву", предложенному ранее Илиёнсом и Де Винком [21]. В нашей модели параллельных вычислений аналогичные возможности обеспечиваются с помощью резидентов. При этом, в отличие от работ [20,21], мы обеспечиваем строгую теоретико-модельную семантику взаимодействующих процессов. Практически всеми авторами в рассматриваемой области исследований признаётся необходимость сочетания логического подхода с идеями ООП. В нашей модели вычислений и логическом языке Акторный Пролог принципы ООП реализованы последовательно и целенаправленно. Следствием этого является концептуальная близость и естественное сочетание разработанного подхода с идеями визуального и компонентно-ориентированного программирования. 4.4. Модифицируемые рассуждения в многоагентных системахВ качестве перспективного подхода к логическому программированию агентов в динамическом внешнем окружении принято рассматривать использование неклассических (и, в особенности, немонотонных) логических систем [2,10,30,31]. Мы пошли по принципиально иному пути, строго придерживаясь формализма классической логики первого порядка. В нашей модели вычислений модификация рассуждений, необходимая для корректной логической интерпретации изменений, происходящих во внешнем мире, осуществляется с помощью специальной стратегии исполнения логических программ, основанной на принципе повторных доказательств. Это позволило нам математически строго интерпретировать динамический характер среды Интернет, не теряя при этом выразительные и дедуктивные возможности классической логики предикатов первого порядка. Заметим, что разработанный нами подход свободен от недостатков немонотонных логических систем, таких как необщезначимость (в классическом смысле) выводимых формул, зависимость результата от порядка применения правил вывода и повышенная вероятность зацикливания логических программ. 4.5. Опережающие вычисления в многоагентных системахОдним из наиболее интересных направлений в программировании агентов являются опережающие вычисления. Используя этот принцип для управления процессом получения данных из Интернет, Баиш и Кноблок [27] получили значительное увеличение скорости работы агентов Интернет. Эта же идея на более высоком уровне абстракции исследована в работах Иноу, Кавагучи, Ханеда [32], а также Сэйто и Ямамото [33]. Необходимо отметить также, что идея опережающих вычислений используется в языке OZ [18] вместо отката. Наша модель также может рассматриваться как реализация идеи опережающих вычислений, поскольку в Акторном Прологе не используется синхронизация параллельных процессов. Это означает, что в нашей модели вычислений параллельные процессы никогда не ждут получения данных из других процессов, и все вычисления, осуществляемые программой, фактически, являются опережающими. Таким образом, наша модель вычислений является математической основой для реализации опережающих вычислений в многоагентных системах. ЗаключениеРазработан математический аппарат логического программирования интеллектуальных агентов, осуществляющих поиск и распознавание информации в сложно структурированной, динамической среде Интернет. В основу разработанного математического аппарата положен принцип повторного доказательства подцелей, позволяющий модифицировать логические рассуждения во время и после окончания исполнения логической программы, приводя их в соответствие с новой информацией, поступающей извне. На основе разработанного аппарата модифицируемых рассуждений создан параллельный объектно-ориентированный логический язык Акторный Пролог, обеспечивающий корректность логических программ (интеллектуальных агентов), функционирующих в условиях постоянного изменения и пополнения информации. Разработанные средства позволяют создавать персональные системы (агенты) сбора и анализа информации в Интернет. Использование объектно-ориентированного логического подхода существенно упрощает создание, а также последующую поддержку и модификацию агентов Интернет. Разработанный подход поддерживает визуальное и компонентно-ориентированное программирование агентов Интернет. Я благодарен д.ф.-м.н. Юрию Владимировичу Обухову за помощь и поддержку в осуществлении проекта, акад. Юрию Ивановичу Журавлёву и проф. Владимиру Анатольевичу Захарову, которые принимали участие в обсуждении проблемы описания декларативной семантики многоагентных систем, а также к.ф.-м.н. Сергею Валерьевичу Ремизову, программное обеспечение которого помогло нам при отладке прототипа Акторного Пролога. |
Список литературы
|
Приложение 1. Пример построения теоретико-модельной семантики параллельной логической программыВ этом приложении подробно рассмотрен пример преобразований параллельной логической программы для построения её теоретико-модельной семантики. Преобразование осуществляется по шагам, в соответствии с определением 3.2.3:
Построенная последовательная программа удовлетворяет условиям теоремы 3.2.4, но не удовлетворяет условиям теоремы 3.2.5. Следовательно, гарантируется корректность исследуемой параллельной программы относительно её теоретико-модельной семантики, но при этом не гарантируется её полнота. Приложение 2. Пример агента ИнтернетЗдесь можно увидеть полный листинг агента Интернет, приведённого в качестве примера в разделе 3.4. Визуальное программирование агентов Интернет. Первую половину листинга (51% текста) занимает код, созданный автоматически для описания связей между блоками визуальной программы. Вторая половина листинга (49% текста) включает содержимое отдельных блоков, взятое из повторно используемых пакетов. В тексте программы условно указаны наименования и локальные адреса пакетов, содержимое которых было использовано при создании агента. |