автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Разработка методов и средств динамического выбора алгоритмов планирования действий интеллектуальных агентов

На правах рукописи

ДОБРЕЦОВ Сергей Вячеславович

РАЗРАБОТКА МЕТОДОВ И СРЕДСТВ ДИНАМИЧЕСКОГО ВЫБОРА АЛГОРИТМОВ ПЛАНИРОВАНИЯ ДЕЙСТВИЙ ИНТЕЛЛЕКТУАЛЬНЫХ

АГЕНТОВ

Специальности:

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

05.13.01 - Системный анализ, управление и обработка информации (информатика)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 2003

Работа выполнена на кафедре «Автоматика и вычислительная техника» в ГОУ ВПО «Санкт-Петербургский государственный политехнический университет».

Научный руководитель: доктор технических наук, профессор

Птицына Лариса Константиновна

Официальные оппоненты: доктор технических наук, профессор

Громов Виктор Никифорович доктор технических наук, профессор Ярошенко Алексей Владимирович

Ведущая организация: Академия гражданской авиации

Защита состоится « \ \ » 2003 г. в « К<о » часов на заседании

диссертационного совета Д 212.229.18 в ГОУ ВПО «Санкт-Петербургский государственный политехнический университет» по адресу: 195251, Санкт-Петербург, ул. Политехническая, 29, корпус № 9, аудитория 325.

С диссертацией можно ознакомиться в фундаментальной библиотеке ГОУ ВПО «Санкт-Петербургский государственный политехнический университет».

Автореферат разослан« <6 » ноября 2003 г

Ученый секретарь диссертационного совета [)пП Шашихин В. Н.

ги—-у

2.ооЗ-А

•7 ?78,

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

Решаемые задачи. Для достижения цели диссертационной работы необходимо решить следующие задачи:

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

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

4. Сформировать критерии оптимальности алгоритма планирования и определить принципы динамического выбора алгоритма эффективного планирования действий интеллектуальных агентов.

5. Разработать методы динамического выбора алгоритмов эффективного планирования действий интеллектуальных агентов.

6. Построить прототип экспертной системы для динамического выбора алгоритмов эффективного планирования действий и подтвердить целесообразность использования предложенного инструментария.

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

Основные методы исследования. Для решения поставленных задач используются методы системного анализа, теории систем искусственного интеллекта, теории вероятности и математической статистики, теории оптимизации и принятия решений.

Научные результаты и их новизна:

1. Проведена формализация процесса нелинейного планирования в системах искусственного интеллекта и доказан общий случай теоремы о систематичности уточнения частичного плана с использованием двусторонней защиты казуальных связей.

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

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

4. Впервые решена задача ргарессионяой оценки значений показателей качества алгоритмов планирования действий интеллектуальных агентов и предложен способ снижения сложности регрессионной модели с сохранением точности результатов за счет введения критерия отбора значимой информации.

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

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

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

и EDS. Материалы диссертационной работы внедрены в учебный процесс кафедры автоматики и вычислительной техники СПбГПУ. Представленные внедрения подтверждены соответствующими актами.

Апробация результатов исследования. Основные результаты представлялись на международных, всероссийских и региональных конференциях, включая Ш международную научно-техническую конференцию "Новые информационные технологии и системы" (Пенза, 10-11 декабря 1998 г.), молодежную научно-техническую конференцию «Наукоемкие технологии и интеллектуальные системы 2001», (Москва, 21-22 марта 2001 г.), VII международную конференцию «Информационные сети, системы и технологии» (Минск, 2-4 октября 2001 г.), научную конференцию студентов и аспирантов «XXX Юбилейная неделя науки СПбГТУ» (Санкт-Петербург, 26 ноября - 1 декабря 2001 г.), V международную конференцию по мягким вычислениям и измерениям (Санкт-Петербург, 25-27 июня 2002 г.), II и Ш Всероссийские научно-технические конференции «Прикладные и теоретические вопросы современных информационных технологий» (Улан-Уде, 18 -22 сентября 2001 г. и 30 июля - 6 августа 2002 г.), Международную конференцию «Информационные технологии в образовании, технике и медицине» (Волгоград, 2426 сентября 2002 г.). По теме диссертационной работы сделано 11 публикаций.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы, включающего 136 наименований, и приложений. Материал работы изложен на 175 страницах машинописного текста, основное содержание - на 144 страницах. Работа содержит 9 рисунков и 18 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

определений интеллектуальных агентов и их основных свойств, таких как автономность, реактивность, целеустремленность и коммуникативность, раскрыта ключевая роль планирования деятельности как неотъемлемого атрибута интеллектуального поведения программных систем.

На основании рассмотрения двух основных парадигм планирования действий в искусственном интеллекте - планирования в пространстве состояний и планирования в пространстве частичных планов, их общих компонент и взаимосвязей, сформулирована универсальная постановка задачи планирования (I,G\ где I соответствует исходному состоянию системы, a G определяет набор целевых условий. Даны определения решения задачи планирования для обоих представлений и выделены основные свойства алгоритма построения плана действий, включающие корректность, полноту и систематичность, которые обеспечивают гарантированное нахождение всех решений задачи планирования. Проведенный анализ развития систем планирования позволил выявить ограничения концепции классического планирования, а также определить основные перспективные направления развития систем планирования действий, связанные с планированием в условиях неопределенности, информационным, оптимальным, динамическим и адаптивным планированием, планированием во времени (составлением расписаний), а также планированием в условиях действующих ограничений на используемые ресурсы вычислительных машин, комплексов и компьютерных сетей.

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

Во второй главе представлен анализ широкого спектра методов планирования и выделен класс методов нелинейного планирования, позволяющий учитывать специфические условия функционирования интеллектуальных программных агентов. Для описания функциональной среды агента использовано представление на базе языка ADL, в котором состояние среды описывается набором булевских переменных Q, а доступные действия (операторы) тройками <PREC, ADD, DEL>, где PREC является набором высказываний предикатов первого порядка, определяющих условия применения оператора, a ADD и DEL - соответственно множества добавляемых (принимающих значение 1) и удаляемых (принимающих значение 0) в результате выполнения оператора переменных. План решения исходной задачи формируется

путем преобразования частичного плана, формально описываемого с помощью тройки (Г, ST, С'), где Т определяет множеством шагов в плане, ST: Т А -отображение шагов плана на множество операторов, а С - совокупность ограничений, включающая ограничения упорядоченности Со, связывающие ограничения С в, монотонные интервальные ограничения С/ и точечные ограничения СР. Процесс планирования состоит в постепенной детализации исходного частичного плана посредством добавления новых шагов и ограничений с целью сужения множества потенциальных решений. Данный процесс соответствует построению дерева поиска, каждой вершине которого соответствует частичный план и, возможно, одно или несколько его потенциальных решений, на основании которых строится решение исходной задачи планирования.

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

На основании представления алгоритмов, используемых в существующих практических реализациях систем планирования, в виде частного случая обобщенного алгоритма нелинейного планирования проведен их теоретический сравнительный анализ, на основании которого сформировано пространство алгоритмов Q, в результате чего каждый конкретный алгоритм планирования соей может быть представлен в виде тройки (ws, of, m° ), где <os е Sf - {МТС, ARB} -тип конструктора решений и соответствующий ему способ выбора подцели: МТС -выбор подцели на основании модального критерия истинности, ARB - произвольный выбор подцели, <вс е if = {NC, SGL, DBL} - используемая стратегия консервации:

8

NC - консервация не применяется, SGL - консервация с односторонним предохранением казуальных связей, DBL - консервация с двусторонним предохранением казуальных связей, а т° е fl° = {NO, CFT, ORD} - применяемая стратегия оптимизации: N0 - оптимизация не используется, CFT - оптимизация на основе разрешения конфликтов, ORD - оптимизация с дополнительным упорядочиванием шагов плана.

Данный подход позволяет расширить рассматриваемое множество альтернатив за счет синтеза новых алгоритмов из элементов выделенного базиса. С учетом естественных ограничений на совместимость компонент базиса, результирующее множество состоит из шести элементов: <ARB, DBL, CFT>, <ARB, SGL, CFT>, <MTC, DBL, CFT>, <MTC, NC, NO>, <MTC, NC, ORD>, <MTC, SGL, CFT>.

В третьей главе проведен анализ критериев оптимальности алгоритма планирования и представлено обоснование необходимости динамического выбора оптимального алгоритма планирования. Для оценки качества функционирования алгоритмов введена система показателей, состоящая из двух уровней:

1. Универсальные показатели, применимые ко всем алгоритмам планирования и отражающие наиболее важные с практической точки зрения свойства алгоритма: функциональность, качество найденного решения, рациональность использования ресурсов, вычислительная сложность, быстродействие и предсказуемость.

2. Специализированные показатели, применимые для конкретного класса алгоритмов. В случае нелинейных алгоритмов с генерацией частично-упорядоченных планов данная группа включает в себя характеристики дерева поиска (степень ветвления,- глубина поиска, необходимая для нахождения решения задачи; степень избыточности; показатель состоятельных вершин), а также вычислительную стоимость одного вызова и основных шагов алгоритма.

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

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

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

Для интегральной оценки оптимальности алгоритма относительно заданного критерия эффективности на множестве задач планирования использованы следующие выборочные критерии: Ф^са) - доля задач, при решении которых алгоритм со оказался е-оптимальным с заданным пороговым значением; Ф^а) - относительное значение показателя эффективности алгоритма а, усредненное на множестве задач планирования; Фз(со) - абсолютное значение показателя эффективности, усредненное на заданном множестве задач планирования (для случая однокритериального выбора).

Полученные результаты определили основное направление дальнейшего исследования, состоящее в разработке методов выбора локально £-опгимальных

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

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

Для оценки значимости имеющейся информации предложен критерий отбора показателей, используемых для принятия решения, на основе статистического критерия хи-квадрат. Для заданного показателя у(ш) эффективности алгоритма планирования строится множество значимых показателей 1у*-{г е 1А: е^у < а), где 1Л - общее множество информационных показателей, состоящее из характеристик среды функционирования 1е и условий задачи 1П; вычисленный критический уровень значимости для распределения хи-квадрат с соответствующим количеством степеней свободы для показателей г е 1А и показателя у(со), а а - задаваемый уровень значимости. Экспериментально показано, что данный подход позволяет сократить размер информационного множества более чем на 40% с сохранением качества результатов за счет исключения малозначимых показателей. Для проверки предложенного критерия отбора информации проведено сравнение результатов, полученных с использованием множеств 1л и 1у*.

Ввиду отсутствия известных экспертных правил для определения оптимального алгоритма планирования, применен подход, основанный на нахождении регрессионной зависимости Я: Х—*У, где множество X определяет используемую информацию (1а или 1у*\ а У соответствует используемой оценке критерия эффективности. В зависимости от способа оценки значения критерия качества выделены два типа задач: строгая постановка, заключающаяся в

определении непосредственного значения критерия оптимальности, и слабая постановка, состоящая в проверке выполнения условия ¿-оптимальности алгоритма.

Принимая во внимание факт отсутствия специализированных методов, учитывающих специфику планирования действий, для решения задачи использованы проблемно-независимые методы анализа данных. Для каждой тройки, состоящей из алгоритма планирования, типа регрессионной задачи и информационного множества, построен набор регрессионных моделей, включающий линейную регрессионную модель Я^х), квадратичную регрессионная модель Я$(х) и нейросетевую регрессионную модель Я^х) на основе искусственной нейронной сети (ИНС) прямого распространения (персептрон) с одним скрытым слоем. В качестве активационной функции узлов скрытого слоя использовался гиперболический тангенс, в выходном слое для задачи типа 1 применялся нейрон с линейной функцией активации, а для задачи типа 2-е логистической функцией.

Входной набор: /и

Входной набор: 1А

<

\ \

1 2 » 4 & 6 7 в 9 10 11 12

Рис. 1. Зависимость ЕЛУот размера скрытого слоя Л//-

Для построения ИНС применена адаптивная процедура выбора размера скрытого слоя Ля, заключающаяся в обучении набора сетей с разными размерами скрытого слоя и выборе из условия минимизации контрольной ошибки ЕЛУ, вычисляемой на некотором сравнительном множестве задач. Для корректного сравнения нейросетевой и других регрессионных моделей при определения Ин использовалось альтернативное тестовое множество, не совпадающее с обучающим и тестовым наборами задач. Как видно из полученных данных (рис. 1), в обоих случаях следует признать значение Ин=5 наилучшим, причем тот факт, что оптимальное значение не зависит от размера входного множества, может рассматриваться как дополнительное подтверждение корректности процедуры выбора множества 1у.

Численное моделирование проводилось с использованием пакета Matlab версии 6.0 и библиотек Regressional Toolbox и Netlab, предоставляющих набор статистических процедур и средств симуляции ИНС соответственно. В целях нормализации к исходным данным была применена препроцессинговая процедура, состоящая в нахождении относительных значений используемых показателей качества функционирования и масштабировании включенных в регрессионную модель показателей в промежутке [0,1]. Для оценки качества рассмотренных моделей использованы средняя и максимальная величины ошибки регрессионной функции па тестовом множестве для задачи типа 1 и отношение числа правильно решенных задач к общему количеству задач в тестовом множестве для задачи типа 2.

На основании анализа рассмотренных моделей сделан вывод о применимости рассмотренного подхода для априорной оценки значений критериев эффективности алгоритма планирования, при этом уровень точности результатов, полученных при использовании моделей Rs(x) и R^x), является достаточно близким и заметно превосходит аналогичные показатели линейной модели Ri(x). Ввиду ограниченной точности оценок, предпочтительной является слабая постановка регрессионной задачи, проверяющая лишь выполняемость условия 8-оптимальности без непосредственной оценки значения рассматриваемого критерия. Экспериментальные данные также подтверждают адекватность выбора множества 1у* на основе предложенного статистического критерия.

Полученные регрессионные оценки использованы для построения точечных стратегий вида a*=S(x), где <а* ей- алгоритм планирования, а х содержит известную информацию о среде функционирования агента и условиях задачи. Решающее правило для задачи типа 1 определяется как:

ta* = arg min R" (JF),

где через R"'(W) обозначена реализация одной из рассмотренных регрессионных моделей для алгоритма со, а ^соответствует вектору значений показателей, входящих в 1Л или в 1у*.

В силу определения, в случае задачи типа 2 (без дискретизации выхода) применяется обратное решающее правило:

»♦ = argmaxÄ,'(»r).

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

Таблица 1

Оценка эффективности априорного динамического выбора оптимального алгоритма на основе регрессионных моделей

Тип задачи Входной набор Регрессионная модель Ф,(ю) Ф2(а>) Ф3(ю)

1 1у* 0.72 2.604 60.44

1 1у* Ш 0.54 1.673 19.50

1 1у* Лф) 0.58 1.647 20.75

1 1а 0.78 2.762 62.61

1 1а 0.36 1.987 20.07

1 1А Яу(х) 0.62 1.715 19.81

2 1у* ад 0.86 2.552 60.22

2 1у* ад 0.54 1.209 11.92

2 IV* ад; 0.74 1.278 12.90

2 1а ад; 0.84 2.615 61.02

2 1а ад; 0.44 1.296 13.52

2 1а ад; 0.68 1.231 12.19

Экспериментальные данные показали, что для наиболее перспективных реализаций данного метода, основанных на использовании моделей Я^х) и Кц(х) и задачи типа 2, эффективность построенного таким образом мета алгоритма планирования оказывается в пределах 20-30% от теоретически достижимого для заданного множества алгоритмов уровня. При этом предложенный метод динамического выбора оптимального алгоритма планирования более чем на 40% превосходит показатели известных альтернативных подходов, основанных как на использовании фиксированного алгоритма, так и на статистических методах выбора (табл. 2). В то же время установлено, что линейная регрессионная модель и

регрессионные оценки для задачи типа 1 не позволяют получить удовлетворительного качества результатов.

Таблица 2

Эффективность выбора алгоритма на основе статистических критериев

Критерий выбора Оптимальный алгоритм Ф1(а>) Ф2(са) ФзМ

тах Ф,(т) <MTC.NC.NO> 0.78 1.708 18.81

тт 02(0)) <MTC.SGL.CFT> 0.30 1.631 15.81

тт Фз(т) <MTC.SGL.CFT> 0.30 1.631 15.81

В пятой главе рассмотрены вопросы, определяющие практическое

использование разработанного подхода к выбору оптимального алгоритма планирования. Наиболее перспективными областями применения априорного выбора алгоритма являются:

- системы планирования в динамической среде: множества переменных, описывающих среду, и действий, модифицирующих значения переменных, меняются от задачи к задаче. Типичными представителями данного класса являются узкоспециализированные программные агенты, ориентированные на решение специфических задач в сложных средах;

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

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

15

осуществляется по протоколу HTTP 1.0 с использованием интегрированного WWW-сервера.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Предложена двухуровневая система показателей производительности алгоритма, на основе которой проведен сравнительный анализ функционирования

рассматриваемых алгоритмов нелинейного планирования с учетом их специфических особенностей.

4. С использованием аппарата теории исследования операций определены подходы к построению статистических критериев оптимальности алгоритмов планирования и принципы динамического выбора алгоритма планирования на основе введенной системы показателей эффективности.

5. На основе статистических и нейросетевых подходов разработаны методы априорного динамического выбора оптимального алгоритма построения плана действий на основании анализа доступной информации о предметной области и условиях задачи планирования до фактического ее решения.

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

Список опубликованных работ по теме диссертации

1. Добрецов C.B., Шестаков С.М. Планирование действий в искусственном интеллекте // Демиург (Вестник Академии Технического Творчества), № 1/1998. -СПб, 1998 - С. 32-46.

2. Добрецов C.B., Шестаков С.М. Повышение производительности интеллектуальных информационных агентов в гетерогенных средах И Материалы Ш международной научно-технической конференции «Новые информационные технологии и системы» - Пенза: ПГТУ, 1998. - С. 33.

3. Добрецов C.B., Шестаков С.М. Особенности организации систем сбора и обработки информации в гетерогенных сетях // Вычислительные, измерительные и управляющие системы. Труды СПбГТУ № 479 - СПб: СПбГТУ, 1999. - С. 32-35.

4. Добрецов C.B., Птицына J1.K. Перспективные направления исследований в области планирования действий интеллектуальных агентов // XXIX неделя науки СПбГТУ. Материалы межвузовской научной конференции (факультет

технической кибернетики и институт интеллектуальных систем). Часть V - СПб: СПбГТУ, 2000-С. 38-39.

5. Добрецов C.B. Анализ критериев оптимальности алгоритмов планирования действий интеллектуальных агентов // Сборник докладов III научно-технической конференции «Наукоемкие технологии и интеллектуальные системы 2001». - М.: МГТУ им. Н.Э.Баумана, 2001. - С. 287-290.

6. Добрецов C.B. Автоматизация выбора оптимального алгоритма планирования действий интеллектуальных агентов // Сборник докладов межвузовской научно-технической конференции «Управляющие и вычислительные системы. Новые технологии». - Вологда: ВГТУ, 2001 - С. 78-79.

7. Добрецов C.B. Использование алгоритмов планирования при реализации интеллектуальных агентов // Сборник докладов П всероссийской научно-технической конференции «Прикладные и теоретические вопросы современных информационных технологий». Часть I - Улан-Удэ: ВСГТУ, 2001. - С. 130-135.

8. Добрецов C.B. Сравнительный анализ нелинейных алгоритмов планирования действий интеллектуальных агентов // Труды VII международной конференции «Информационные сети, системы и технологии». Том 2. / Под ред. А.Н. Морозевича, A.M. Зеневич - Мн.: БГЭУ, 2001. - С. 109-114

9. Добрецов C.B., Птицына JI.K. Сравнительный анализ нелинейных процедур планирования действий интеллектуальных агентов // Научная конференция студентов и аспирантов «XXX Юбилейная неделя науки СПбГТУ». Материалы межвузовской научной конференции (факультет технической кибернетики). Часть VII. -СПб: СПбГТУ, 2002. - С. 34-35.

10. Добрецов C.B. Априорный выбор оптимального алгоритма планирования алгоритма решения задачи планирования действий // Сборник докладов III Всероссийской научно-технической конференции «Прикладные и теоретические вопросы современных информационных технологий». Часть I - Улан-Удэ: ВСГТУ, 2002.-С. 143-148.

11. Добрецов С.В Экспертная система выбора оптимального алгоритма планирования действий интеллектуального агента // Сборник докладов международной конференции «Информационные технологии в образовании, технике и медицине». Часть П -Волгоград: ВГТУ, 2002. - С. 75-78.

Лицензия ЛР №020593 от 07.08.97.

Подписано в печать 06.//. Объем в п.л. /,0 Тираж /00. Заказ

Отпечатано с готового оригинал-макета, предоставленного автором, в типографии Издательства СПбГПУ 195251, Санкт-Петербург, Политехническая ул., 29.

Отпечатано на ризографе ЯН-2000 ЕР Поставщик оборудования — фирма "Р-ПРИНТ" Телефон: (812) 110-65-09 Факс: (812) 315-23-04

17 ?7&

»17978

ВВЕДЕНИЕ.

1. ВЫБОР ПРИНЦИПОВ ОРГАНИЗАЦИИ ЭКСПЕРТНЫХ СИСТЕМ ДЛЯ ОПТИМИЗАЦИИ ПЛАНИРОВАНИЯ ДЕЙСТВИЙ ИНТЕЛЛЕКТУАЛЬНЫХ АГЕНТОВ.

1.1. Назначение и функции интеллектуальных агентов.

1.2. Описание знаний интеллектуальных агентов.

1.3. Задача планирования действий интеллектуального агента.

1.3.1. Среда функционирования интеллектуальных агентов и ее основные характеристики.

1.3.2. Постановка задачи планирования интеллектуальных агентов.

1.3.3. История исследований и текущее состояние.

1.4. Анализ перспектив развития и выбор принципов организации экспертных систем для оптимизации планирования действий интеллектуальных агентов

1.4. L Особенности разработки и применения экспертных систем.

1.4.2. Использование искусственных нейронных сетей в экспертных системах

1.5. Постановка задачи диссертационной работы.

2. ФОРМИРОВАНИЕ КЛАССА ПЕРСПЕКТИВНЫХ СТРАТЕГИЙ fr ПЛАНИРОВАНИЯ ДЕЙСТВИЙ ИНТЕЛЛЕКТУАЛЬНЫХ АГЕНТОВ.

2.1. Представление алгоритмов нелинейного планирования в пространстве состояний.

2.2. Обобщенный алгоритм нелинейного планирования в пространстве состояний.

2.2.1. Конструктор решений.

2.2.2. Уточнение частичного плана.

2.2.3. Проверка состоятельности модифицированного плана.

2.2.4. Оптимизация уточненного плана.

2.3. Анализ особенностей реализаций нелинейных систем планирования и их представление через обобщенный алгоритм планирования.

2.3.1. Алгоритм NONLIN.

2.3.2. Алгоритм TWEAK.

2.3.3. Алгоритм SNLP.

2.3.4. Алгоритм XJA.

2.3.5. Формирование базиса класса нелинейных систем планирования.

2.4. Выводы.

3. АНАЛИЗ КРИТЕРИЕВ ОПТИМИЗАЦИИ ПЛАНИРОВАНИЯ ДЕЙСТВИЙ.

3.1. Анализ известных подходов к оптимизации планирования действий

3.2. Анализ показателей производительности алгоритмов планирования

3.2.1. Универсальные показатели производительности.

3.2.2. Оценка специфических особенностей алгоритмов планирования.

3.3. Параметризация предметной области.

3.4. Характеристики задачи планирования.

3.5. Экспериментальный анализ производительности сравниваемых алгоритмов.

5Г' 3.6. Выбор алгоритма планирования с позиций теории исследования операций.

3.7. Формирование критериев эффективности алгоритма.

3.8. Концепция системы выбора оптимального алгоритма.

3.9. Выводы.

4. АПРИОРНЫЙ ВЫБОР ОПТИМАЛЬНОГО АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ ПЛАНИРОВАНИЯ.

4.1. Анализ задачи априорного выбора.

4.2. Критерий отбора доступной информации.

4.3. Оценка значения критерия эффективности.

4.4. Построение канонических регрессионных моделей.

4.5. Применение средств анализа данных на основе искусственных нейронных сетей.

4.6. Использование регрессионных моделей для выбора оптимального алгоритма.

4.7. Выводы.

5. ЭКСПЕРТНАЯ СИСТЕМА ВЫБОРА ОПТИМАЛЬНОГО АЛГОРИТМА ПЛАНИРОВАНИЯ И ЕЕ ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ.

5.1. Примененимость выбора оптимального алгоритма в прикладных системах.

5.2. Анализ требований к системе выбора оптимального алгоритма планирования.

5.3. Особенности практической реализации.

5.4. Использование системы выбора алгоритма планирования для управления комплексной вычислительной средой.

5.4.1. Задача управления комплексной вы числительной средой.

5.4.2. Моделирование предметной области.

5.4.3. Архитектура системы управления вычислительной средой.

5.4.4. Оценка эффективности.

5.5. Выводы.

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

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

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

Несмотря на значительный прогресс, достигнутый в области систем и алгоритмов планирования, текущее состояние характеризуется двумя особенностями:

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

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

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

Анализ известных научных работ по тематике планирования позволяет выделить ряд областей, непосредственно влияющих на эффективность применения систем планирования при разработке интеллектуальных агентов, которым не было уделено должного внимания:

- методы анализа и сравнения производительности алгоритмов планирования;

- исследование зависимости производительности алгоритма планирования от типа предметной области и задачи планирования;

- оптимизация процесса планирования.

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

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

2. Построить унифицированное формализованное представление процесса построения плана действий и определить множество альтернатив, состоящее из потенциально оптимальных алгоритмов планирования.

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

4. Сформировать критерии оптимальности алгоритма планирования и определить принципы динамического выбора алгоритма эффективного планирования действий интеллектуальных агентов.

5. Разработать методы динамического выбора алгоритмов эффективного планирования действий интеллектуальных агентов.

6. Построить прототип экспертной системы для динамического выбора алгоритмов эффективного планирования действий и подтвердить целесообразность использования предложенного инструментария.

Научная новизна диссертационной работы заключается в следующем:

1. Проведена формализация процесса нелинейного планирования в системах искусственного интеллекта и доказан общий случай теоремы о систематичности уточнения частичного плана с использованием двусторонней защиты казуальных связей.

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

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

4. Впервые решена задача регрессионной оценки значений показателей качества алгоритмов планирования действий интеллектуальных агентов и предложен способ снижения сложности регрессионной модели с сохранением точности результатов за счет введения критерия отбора значимой информации.

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

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

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

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

Основные результаты диссертационной работы представлены в [9-19].

Заключение

В диссертационной работе представлены результаты теоретического и экспериментального исследования, на основе которых решена задача создания аппарата качественного и количественного анализа алгоритмов и систем планирования действий интеллектуальных агентов, позволяющего проводить сравнение и априорный выбор оптимального алгоритма планирования. Практическое значение данной задачи определяется ее ключевой ролью в повышении производительности агентов за счет оптимизации работы и расширения функциональности одной из основных подсистем агента, отличающих ИА от других программных продуктов - подсистемы планирования деятельности. Основные результаты работы заключаются в следующем:

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

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

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

4. С использованием аппарата теории исследования операций определены подходы к построению статистических критериев оптимальности алгоритмов планирования и принципы динамического выбора алгоритма планирования на основе введенной системы показателей эффективности.

5. На основе статистических и нейросетевых подходов разработаны методы априорного динамического выбора оптимального алгоритма построения плана действий на основании анализа доступной информации о предметной области и условиях задачи планирования до фактического ее решения.

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

1. Аналитические технологии для прогнозирования и анализа данных. Учебное пособие, Нейропроект НИИЯФ МГУ, 1999 http://www.neuroproject.ru/oglavl.htm (15 авг. 2003)

2. Боровков А. А. Математическая статистика. Оценка параметров. Проверка гипотез. М., Наука, 1984. - 472 с

3. Винер Н. Кибернетика, или Управление и связь в животном и машине Пер с англ., 2 изд. М.: Наука, 1983. - 344 с.

4. Галушкин А.И. Применение нейрокомпьютеров в энергетических системах // Научный Центр Нейрокомрьютеров, М., 1996 http://www.uran.donetsk.Ua/~masters/2002/kita/serdyuk/diss/lib/2/index2.htm (15 авг. 2003)

5. Галушкин А.И. Современные направления развития нейрокомпьютерных технологий в России // Открытые системы, №4, 1997 http://www.osp.ru/os/1997/04/25.htm (15 авг. 2003)

6. Герасимов Ю.Ю. Теория принятия решений. Учебный курс, Петрозаводский ГУ, 1998 http://www.karelia.ru/psu/Faculties/Forest/ courses/decision/decisa.htm (15 авг. 2003)

7. Горбань А.Н, Дунин-Барковский В.Л., Кирдин А.Н. и др. Нейроинформатика Новосибирск: Наука. Сиб. предприятие РАН, 1998. -296 с.

8. Горбань А.Н. Обобщенная аппроксимационная теорема и вычислительные возможности нейронных сетей // Сибирский журнал вычислительной математики. 1998. - Т. 1. - N 1. - С. 12-24

9. Добрецов С. В., Шестаков С.М. Планирование действий в искусственном интеллекте // Демиург (Вестник Академии Технического Творчества), № 1/1998,- СПб, 1998-С. 32-46.

10. Добрецов С. В., Шестаков С.М. Особенности организации систем сбора и обработки информации в гетерогенных сетях // Вычислительные, измерительные и управляющие системы. Труды СПбГТУ № 479 — СПб: СПбГТУ, 1999. С. 32-35.

11. Добрецов С.В Экспертная система выбора оптимального алгоритма планирования действий интеллектуального агента // Сборник докладовмеждународной конференции "Информационные технологии в образовании, технике и медицине". -Волгоград: ВГТУ, 2002. С. 75-78

12. Ежов А, Чечеткин В. Нейронные сети в медицине // Открытые системы, №4, 1997 -http://www.osp.ru/os/1997/04/34.htm (15 авг. 2003)

13. Ежов А., Шумский С. Нейрокомпьютинг и его применение в экономике и финансах -М.: МИФИ, 1998. 222 с.

14. Искусственный интеллект. Кн. 2. Модели и методы / Под ред. Д.А.Поспелова М: Радио и связь, 1990 - 304 с.

15. Каннади Д. Нейросетевые технологии в диагностике аномальной сетевой активности // Пер. с англ. М.: НИП «Информзащита», 1999. -http://vlasov.iu4.bmstu.ru/primer/ssl/ssll.htm (15 авг. 2003)

16. Катулев А.Н., Северцев H.A. Исследование операций: принципы принятия решений и обеспечение безопасности М.: Физ.-мат. лит., 2000. — 320 с.

17. Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. Курс лекций. М.: МЦМНО, 1998. - http://qc.ipt.ac.ru/russian/kitaev.zip (15 авг. 2003)

18. Клышинский Э. С. Некоторые аспекты построения агентных систем // МГИЭМ, 1999-http://www.sdteam.com/articles/agent.html (15 авг. 2003)

19. Логический подход к искусственному интеллекту: От модальной логики к логике баз данных / Тейз А., Грибомон П., Юлен Г. и др. М.:Мир, 1998.494 с.

20. Минский М., ПайпертС. Персептроны. М.: Мир, 1971.-240 с.31.0суга С. Обработка знаний М.:Мир, 1989. - 293 с.

21. Попов Э. В. Экспертные системы реального времени // Открытые системы, №2, 1995 -http://www.osp.ru/os/1995/02/66.htm (15 авг. 2003)

22. Розенблатт Ф. Принципы нейродинамики. Персептрон и теория механизмов мозга. М.: Мир, 1965. - 480 с.

23. Статистические и динамические экспертные системы :Учеб. пособие для вузов/ Попов Э.В.,Фоминых И.Б.,Кисель Е.Б.,Шапот М.Д. М. :Финансы и статистика, 1996. - 319 с.

24. Универсальная энциклопедия Кирилла и Мефодия М.: Кирилл и Мефодий, 1999. - http://mega.km.ru (15 авг. 2003)

25. Уоссерман Ф. Нейрокомпьютерная техника: Теория и практика. -М: Мир, 1992.-240 с.

26. Уэно X., Исидзука М. Представление и использование знаний М.:Мир, 1989.-220 с.

27. Фишберн П. Теория полезности для принятия решений. М.: Наука, 1978.-352 с.

28. Шестаков С. М. Разработка и исследование интеллектуальных агентов для работы с информационными источниками в гетерогенных сетях: Диссертация на соискание ученой степени кандидата технических наук. -СПб, 2000-184 с.

29. AIPS98 Planning Competition Results // Proceedings of the Forth International Conference AIPS'98 Carnegi-Mellon University (PA), 1998. - http://www-2.cs.cmu.edu/~aips98 (15 авг. 2003)

30. Agent Technology: Foundations, Applications, and Markets / Jennings N. R., Wooldridge M. J. (Eds.) Berlin: Springer-Verlag, 1998. - 325 p.

31. Agre, P. E., Chapman, D. Pengi: An Implementation of a Theory of Activity // Proceedings of the 6th National Conference on Artificial Intelligence. — Morgan Kaufmann, 1987. pp. 268-272

32. Akaike, H. Fitting Autoregressive Models for Prediction // Annals of the Institute of Statistical Mathematics, 1969, Vol 21. pp. 243-247.

33. Alterman R. Issues in adaptive planning. University of California, Berkeley (CA), 1986.-39 p.

34. Appleby S. ,Steward S. Mobile Software Agents for Control in Telecommunications Networks // ВТ Technological Journal 12 (2), 1994. -pp.104-113

35. Bacchus F. AIPS-2000 Planning Competition. U. of Toronto, Canada, 2000. -http://www.cs.toronto.edu/aips2000 (15 авг. 2003)

36. Blum A., Furst M. Fast planning through planning graph analysis // Artificial Intelligence, Vol. 90, 1997 pp. 281-300

37. Boger, Z., and Guterman, H. Knowledge extraction from artificial neural network models // Proceedings of the 1997 IEEE Conference on Systems, Man, and Cybernetics. Orlando (FL), 1997. - pp. 3030-3035

38. Bratman, M.E. Intentions, Plans, and Practical Reason Cambridge (MA): Harvard University Press, 1987 - 140 p.

39. Bylander T. A Linear Programming Heuristic for Optimal Planning // Proceedings of 14th AAAI/9th IAAI Conference. AAAI Press / The MIT Press, 1997.-pp. 694-699.

40. Carpenter 0., Grossberg S. A massively parallel architecture for a self-organizing neural pattern recognition machine // Computing Vision, Graphics and Image Processing, Vol 37, 1987. pp. 54-115.

41. Chapman D. Planning for conjunctive goals // Artificial intelligence, Vol. 32, 1987.-pp. 333-337.

42. Chavez A., Maes P. Kasbah: An Agent Marketplace for Buying and Selling Goods // Proceedings the First International Conference on the Practical Application of Intelligent Agents and Multi-Agent Technology (PAAM'96) -London, UK, 1996. pp. 75-90

43. Chiariglione L. FIPA A general overview // 1996 -http://agdec2.technion.ac.il/~granot/telerobotics/ilpa.htm (15 aBr. 2003)

44. Cohen, P.R., Levesque H.J. Intention is choice with commitment // Artificial Intelligence, Vol. 42, 1990-pp. 213-261

45. Davies, N. J., Weeks, R. Jasper: Communicating Information Agents // Proceedings of the 4th International Conference on the World Wide Web -Boston (MA), 1995 http://www.w3.org/Conferences/WWW4/Papers/ 180 (15 aBr. 2003)

46. Doyle P., Planning. AI Qual Summary: Stanford University, 1997 http://www-cs-students.stanford.edu/~pdoyle/quail/notes/pdoyle/planning.html (15 aBr. 2003)

47. Enbutsu I., Baba K., Hara K. Fuzzy rule extraction from a multilayered neural network// Proceedings of IJCNN Seattle (WA), 1991. - pp. 461-465

48. Etzioni O., Hanks S., Weld D., Draper D., Lesh N. and Williamson M. An approach to planning with incomplete information // In Proceedings of the

49. Third International Conference on Principles of Knowledge Representation and Reasoning, KR-92 Cambridge (MA), 1992. - pp. 115-125

50. Ferber J. Simulating with Reactive Agents / In Stender, J., Hillebrand, E. (Eds.), Many Agent Simulation and Artificial Life. Amsterdam: IOS Press, 1994-pp. 8-28

51. Feigelbaum E., Feldman J. (Eds.). Computers and Thought. New York: McGraw-Hill, 1963.-535 p.

52. Feigelbaum E. A Personal View of Expert Systems / Report No. KNL92-41 -Stanford University, CA, USA, 1992.- 21 p.

53. Fikes, R. E., Nilsson, N. J. STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving // Artificial Intelligence, Vol. 2, 1971. -pp. 189-208

54. Foner L. A Multi-Agent Referral System for MatchMaking // Proceedings the First International Conference on the Practical Application of Intelligent Agents and Multi-Agent Technology (PAAM '96) London, UK, 1996. - pp. 245-262

55. Genesereth M., Ketchpel S. Software Agents // Communications of the ACM, 37(7), 1994.-pp. 48-53.

56. Currie K., Tate A. O-PLAN: The Open Planning Architecture // Artifical Intelligence, Vol. 51(1), 1991. pp. 49-86

57. Hanks S., Williamson M. Optimal Planning with a Goal-Directed Utility Model// Proceedings of the 2nd AIPS Conference, 1994 pp. 176-181

58. Hanks S., Weld D.S. A Domain-Independent Algorithm for Plan Adaptation // JAIR Vol. 2, 1995.-pp. 319-360

59. Hayes-Roth, B. An Architecture for Adpative Intelligent Systems // Artificial Intelligence, Vol. 72 (1-2), 1995. pp.329-365.

60. Heckerman D., A tutotial on learning Bayesian networks / Technical report TR-95-06. -Redmond (WA): Microsoft Research, 1995. 57 p.

61. Hoist A., The Use of a Bayesian Neural Network Model for Classification Tasks: Dissertation. Stockholm, Sweden: Royal Institute of Technology, 1997.-172 p.

62. Hopfíeld J.J. Neural Networks and Physical systems with emergent collective computational abilities // Proceedings of the National Academy of Sciences of the USA, Vol. 79, 1982. -pp.2554-2558

63. Huhns M.N., Singh M.P. Ksiezyk T. Global information management via local autonomous agents / In: Huhns M.N., Singh M.P (Eds.), Readings in Agents. — San Francisco (CA): Morgan Kaufmann Publishers Ca, 1998. pp. 36-45

64. Hurvich C.M., Tsai C.L. Regression and time-series model selection in small samples // Biometrika, 1989. pp. 297-307

65. Hyotyniemi H. Multivariate Regression Techniques and Tools: Report 125. -Helsinki University of Technology, Espoo, Finland, 2001.-215 p.

66. Jennings N. R., Wittig T. ARCHON: Theory and Practice /In: Avouris N. M., Gasser L. (Eds.), Distributed Artificial Intelligence: Theory and Praxis-Kluwer Academic Press, 1992. pp. 179-195

67. Jordan M. I. Why the logistic function? A tutorial discussion on probabilities and neural networks: MIT Computational Cognitive Science Report 9503. — MIT, 1995.- 13 p.

68. Kaebling, L. P., Rosenschein, S. J. Action and Planning in Embedded Agents / In: Maes P. (Ed.), Designing Autonomous Agents: Theory and Practice from Biology to Engineering and Back. Cambridge (MA): The MIT press, 1990. — pp. 35-48

69. Kambhampati S. Multi-Contributor Causal Structures for Planning: A Formalization and Evaluation // Artificial Intelligence, Vol. 69, 1994. pp. 235-278.

70. Kambhampati S., Knoblock C., Yang Q. Planning as Refinement Search: A Unified framework for evaluating design tradeoffs in partial order planning // Artificial Intelligence. Special issue on Planning and Scheduling. Vol. 76. No. 1-2, 1995.-pp. 167-238.

71. Kautz H., Selman B. Unifying SAT-based and graph-based planning // Proceedings of the 16th International Joint Conference on Artificial Intelligence, IJCAI99. Stockholm, Sweden, 1999. - pp. 318-325

72. Kohonen, T. Self-Organization and Associative Memory. Berlin: SpringerVerlag, 1989.-312 p.

73. Kosko B. Bi-directional associative memories // IEEE Transactions on Systems, Man and Cybernetics 18(1), 1987. -pp.49-60

74. Kozierok R., Maes P. A Learning Interface Agent for Scheduling Meetings // Proceedings of the ACM-SIGCHI International Workshop on Intelligent User Interfaces. Orlando (FL), 1993. - pp. 81-93

75. Kushmerick N., Hanks S., Weld D. S. An algorithm for probabilistic planning// Artificial Intelligence. Special issue on Planning and Scheduling. Vol. 76. No. 1-2, 1995.-pp. 239-286

76. Lambrecht E., Kambhampati S., Optimizing Recursive Information Gathering Plans // Proceedings of the 16th International Joint Conference on Artificial Intelligence. Stockholm, Sweden. 1999. - pp. 1204-1211

77. Lange D. B. Mitsuru, O. Programming and Deploying Java(TM) Mobile Agents with Aglets(TM). Addison-Wesley, 1998. -225 p.

78. Liatsos V, Richards B. Least Commitment An Optimal Planning Strategy // 16th Workshop of the UK Planning and Scheduling SIG, 1997. - http://www-icparc.doc.ic.ac.uk/parcPlan/sig97 (15 feb. 2002)

79. Lippman R.P. An introduction to computing with neural nets // IEEE ASSP Magazine. Apr. 1987. pp. 4-22

80. Lovasz L. Computational Complexity: Lecture Notes. Eotvos University, Budapest, Hungary, 1995. - 168 p.

81. Maes P. Artificial Intelligence meets Entertainment: Lifelike Autonomous Agents//Communications of the ACM, Vol.38 (11), 1995.-pp.108-114.

82. McAllister D, Rosenblitt D. Systematic Nonlinear Planning // Proceedings of 9th AAAI Conference. Anaheim (CA), 1991. - pp. 634-639

83. McMillan C., Mozer M. C., Smolensky P. Learning explicit rules in a neural network // Proceedings of the International Joint Conference on Neural Networks IJCNN'91. Seattle (WA), 1991. - pp. 83-88.

84. Minsky M. A Framework for Representing Knowledge // In: Winston P. H. (ed.), The Psychology of Computer Vision. New York: McGraw-Hill, 1975-pp. 211-277

85. Minton S., Bresina J. , Drummond M. Commitment Strategies in Planning: A Comparative Analysis // Proceedings of the Twelfth International Joint Conference on Artificial Intelligence. Sydney, Australia, 1991. - pp. 259-267

86. Minton S., Drummond M., Bresina J., Philips A. Total order vs. Partial Order Planning: Factors Influencing Performance // Proceedings of the KR-92 Conference. Cambridge (MA), 1992. - pp. 83-92

87. Moody J. E., Darken C. Fast learning in networks of locally-tuned processing units // Neural Computation 1, 1989. pp. 281-294

88. Muller J. P., Pischel, M. Modelling interacting agents in dynamic environments I I Proceedings of the Eleventh European Conference on Artificial Intelligence (ECAI-94). Amsterdam, The Netherlands, 1994. - pp. 709-713

89. Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence/ G. Weiss (Ed.) Cambridge, MA: MIT Press, 1999. - 619 p.

90. Nabney I.T. NETLAB: Algorithms for Pattern Recognition. New York: Springer Verlag, 2001 - 420 pp.

91. Newell A., Simon H. A. GPS, a program that simulates human thought / In Feigenbaum E. A., Feldman J. (Eds.), Computers and Thought. New York: McGraw-Hill, 1963. - pp. 279 - 293

92. Nwana, H. S. Simulating a Children's Playground in ABLE: Working Report. Department of Computer Science, Keele University, UK, 1993. -http://www.keele.ac.uk/depts/cs (12 Oct. 1999)

93. Nwana H. Software Agents: An Overview // Knowledge Engineering Review Journal, Vol. 11, No 3, 1996. pp. 1-40

94. Papazoglou M. P., Laufman S. C., Sellis, T. K. An Organizational Framework for Cooperating Intelligent Information Systems // Intelligent and Cooperative Information Systems 1(1), 1992.-pp. 169-202.

95. Pednault E. P. D. ADL: Exploring the middle ground between STRIPS and the Situation Calculus // Proceedings of the 1st International Conference on Principles of Knowledge Representation and Reasoning. Toronto, Canada, 1989.-pp. 324-332

96. Penberthy J. S., Weld D. S. UCPOP: A Sound, Complete, Partial Order Planner for ADL // Proceedings of the Third International Conference on Principles of Knowl. Repr. and Reasoning. Cambridge (MA), 1992. - pp. 103-114

97. Plu M. Software Agents in Telecommunications Network Environments II UNICOM Seminar on Intelligent Agents and their Business Applications. -London, UK, 1995. pp. 225-243

98. Quillian M. R. Semantic Memory / In. Minsky M. (ed.), Semantic Information Processing. Cambridge (MA): The MIT Press, 1968. - pp. 227270

99. Rao A.A. and Georgeff M.P. Modeling rational agents within a BDI-architecture // Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning. -San Mateo (CA), 1991. pp. 473-484

100. Sacerdoti E. Planning in a Hierarchy of Abstraction Spaces // Artificial Intelligence, Vol 5(2), 1974. pp. 115-135

101. Safra S., Tennenholtz M. On Planning while Learning // Journal of Artificial Intelligence Research, Vol. 2, 1994. pp. 111-129.

102. Sarle W. S. Donoho-Johnstone Benchmarks: Neural Net Results/ SAS Institute Inc, 1999. ftp://ftp.sas.com/pub/neural/dojo/dojo.html (20 Mar 2002)

103. Schwarz G. Estimating the Dimension of a Model // Annals of Statistics, Vol. 6, 1978-pp.461-464

104. Shahmehri N., Lambrix P. Notes on Intelligent Software Agents: Course notes. LinkOping university, Sweden, 1998. - http://www.ida.liu.se/ labs/iislab/courses/Agents/paper (4 Mar. 1999)

105. Sheth B., Maes P. Evolving Agents for Personalised Information Filtering // Proceeding of the Ninth Conference on AI for Applications. IEEE Computer Society Press, 1993. - pp.345-352,

106. Shoham, Y. Agent Oriented Programming // Journal of Artificial Intelligence, 1993. Vol. 60(1). pp. 51-92

107. Slaney J., Thiebaux S. Linear-Time Near-Optimal Planning in the Blocks World // Proceedings of 13th AAAI Conference. AAAI Press/The MIT Press, 1996. - pp. 1208-1214.

108. Smith D., Peot M. Postponing Threats in Partial-Order Planning // Proceedings of the 11th AAAI Conference. AAAI Press, 1993. - pp. 500-506

109. Sussman G. J. The Virtuous Nature of Bugs / In: Allen J., Hendler J, Tate A. (Eds.), Readings in Planning,. San Franciso (CA): Morgan Kaufmann Publishers, 1990. - pp 111-117

110. Swingler, K. Applying Neural Networks: A Practical Guide. — London: Academic Press, 1996. 303 p.

111. Sycara K., Zeng D. Coordination of Multiple Intelligent Software Agents // International Journal of Cooperative Information Systems, Vol. 5 (2-3) 1996.-pp. 181-212

112. Tate A. Interplan: A plan generation system which can deal with interactions between goals: Memo MIP-R-109. Machine Intelligence Research Unit, Univ. of Edinburgh, UK, 1974.

113. Tate A. Generating Project Networks // Proceedings of the Fifth International Joint Conference on Artificial Intelligence. Boston (MA), 1977.- pp. 888-893

114. Warren D. Warplan: A system for generating plans: Technical Report 76. Computational Logic Dept., School of AI, Univ. of Edinburgh, UK, 1974.

115. Weld D. S. An Introduction to Least Commitment Planning // AI Magazine, 15(4), 1994.-pp. 27-64

116. Weld D. Recent Advances in AI Planning // AI Magazine, Vol 20(2), 1999.-pp. 93-123.

117. White, J. E. Mobile Agents Make a Network an Open Platform for Third-Party Developers // IEEE Computer, 27(11), 1994. pp. 89-90

118. Wooldridge M., Jennings N.R. Intelligent Agents: Theory and Practice // The Knowledge Engineering Review, Vol. 10. No. 2., 1995. pp. 115-152.