Содержание к диссертации
Введение
1. Агентный подход к решению задач 6
1.1 Анализ понятия «агент» 6
1.2 Виды агентных архитектур 17
1.2.1 Делиберативная архитектура 18
1.2.2 Реактивная архитектура 28
1.2.3 Гибридная архитектура 34
1.3 Стратегии функционирования мультиагентных систем 51
1.4 Агентный подход к анализу изображений 56
1.5 Выводы к главе 1 61
2. Агент системы анализа изображений 62
2.1 Понятие агента и его среды 62
2.2 Задачи агента и его функциональная модель 68
2.3 Структура агента 74
2.4 Обобщённый алгоритм работы агента 83
2.5 Работа агента в активизированном режиме 86
2.6 Функционирование агента при нисходящем анализе 91
2.7 Функционирование агента при восходящем анализе 99
2.8 Выводы к главе 2 104
3. Экпериментальные исследования 105
3.1. Цели и задачи экспериментального исследования 105
3.2. Описание программно - аппаратной системы для проведения эксперимента 107
3.3. Описание экспериментального исследования 114
3.4 Выводы к главе 3 129
Заключение 130
Список литературы
- Делиберативная архитектура
- Стратегии функционирования мультиагентных систем
- Задачи агента и его функциональная модель
- Описание программно - аппаратной системы для проведения эксперимента
Введение к работе
Актуальность темы. Автоматическая обработка визуальной информации является важным направлением в области искусственного интеллекта, и ей в последние годы уделяется все возрастающее внимание. Интенсивное освоение космического пространства повышает актуальность задач распознавания и оценки состояния земной поверхности по сигналам, получаемым с различных спутников-наблюдателей. К таким задачам можно отнести: анализ техногенного загрязнения окружающей среды, анализ экологических проблем, мониторинг использования природных ресурсов и контроль выполнения международных соглашений. Задачи распознавания изображений возникают и в смежных прикладных областях: компьютерное зрение, автоматический контроль безопасности дорожного движения, медицинская диагностика, томография и ряд других. Хорошо известно, что решение таких задач связано с обработкой большого объёма информации сложной структуры, которую трудно интерпретировать.
В настоящее время одним из наиболее перспективных подходов к решению сложных задач (которыми, бесспорно, являются и задачи анализа изображений), в области искусственного интеллекта является мультиагентный подход. Сущность мультиагентного подхода к решению задач состоит в том, чтобы редуцировать исходную сложную задачу до некоторой упорядоченной совокупности более простых задач, совокупное решение которых приведет и к решению исходной сложной задачи. Ответственность за решение каждой такой «простой» задачи возлагается на некоторую относительно «простую» решающую систему, называемую агентом (более простую по сравнению с решающей системой, способной решить исходную сложную задачу самостоятельно). Это позволяет снизить трудоёмкость разработки и модификации решающей системы, необходимой для решения исходной сложной задачи, за счёт того, что она представляется совокупностью относительно простых и однотипных решающих систем. Кроме того, во многих случаях использование мультиагентного подхода позволяет решать задачи более
сложные, чем те, которые могут быть решены при помощи классических экспертных систем, например, задачи, обладающие неопределенностью по статической структуре оригинала. Однако, единого мнения относительно интерпретации понятия «агент», являющегося базовым для реализации данного подхода, на текущий момент ещё не сформировано. Нет указания на полный перечень процессов, поддержку которых должны обеспечивать агенты, входящие в состав мультиагентной системы анализа изображений. Не указывается сложность задач, на решение которых должны быть ориентированы отдельные агенты. Невыясненными остаются вопросы относительно структуры таких агентов и состава их внешней среды.
В связи с этим, и в виду актуальности задачи распознавания изображений в целом, разработка агента системы анализа изображений носит актуальный характер.
Цель работы. Целью работы является разработка моделей агента и исследование его свойств, применительно к задаче анализа сложных изображений.
Поставленная цель достигается решением следующих задач:
Исследование проблемы анализа изображений.
Анализ существующих наработок в теории агента.
Определение понятия «агент», применительно к задаче анализа изображений.
Описание состава среды агента мультиагентной системы анализа изображений (МСАИ).
Выявление видов задач, возникающих перед агентом в такой среде.
Разработка функциональной модели агента МСАИ.
Разработка структурной модели агента системы анализа изображений.
Разработка алгоритма взаимодействия агента с его средой.
Методы исследований. При решении поставленных задач использовались методы: теории распознавания образов, теории классификации, теории решения задач, теории алгоритмов, теории экспертных систем, теории искусственного
интеллекта, дискретной математики, а также использовались существующие наработки в теории агента. Проверка теоретических выводов и количественные оценки получены методом имитационного моделирования на ЭВМ. Научная новизна работы:
Разработан состав среды (окружения) агента МСАИ, что позволяет выявить все виды задач, возникающие перед данным агентом в процессе его функционирования в этой среде.
Разработана функциональная модель агента, позволяющая описать работу агента, входящего в состав мультиагентной системы анализа изображений (МСАИ).
Разработана структурная модель агента МСАИ, являющаяся развитием гибридных архитектур, обеспечивающая агенту МСАИ способность решать задачи, возникающие перед ним в его среде.
Разработан алгоритм взаимодействия агента с его средой, позволяющий агенту, в составе МСАИ, решать задачи анализа сложных изображений.
Практическая ценность диссертационной работы заключается в разработке программно-методического комплекса, реализующего функции агента МСАИ для задачи анализа изображений и позволяющего во взаимодействии с пользователем эмулировать работу коллектива агентов.
Использование результатов диссертации. Основные результаты работы были внедрены в Институте леса им. В.Н. Сукачёва СО РАН.
Личный вклад автора. Выносимые на защиту основные результаты получены автором лично. В работах, опубликованных лично и в соавторстве, автором предложены методические основы, проведены аналитические выкладки и получены расчётные значения.
Апробация работы. Материалы диссертационной работы докладывались и обсуждались: на семинаре кафедры «Системы искусственного интеллекта» Красноярского государственного технического университета (2005г.); на семинаре кафедры «Информатики и вычислительной техники» Сибирского Аэрокосмического Университета (2005г); на Всероссийской научно-
методической конференции «Повышение качества непрерывного, профессионального образования» в г. Красноярске (2005г.); на семинаре лаборатории мониторинга леса в Институте леса им. В.Н. Сукачёва СО РАН (2005г.).
Публикации. По материалам диссертации опубликовано 7 печатных работ.
Структура и объём работы. Диссертация состоит из введения, трёх глав и заключения. Всего 140 страниц. Библиография содержит 105 наименований.
В первой главе актуализируются задачи решаемые в данной диссертационной работе. Для этого проводится анализ современного состояния проблемы. Рассматриваются существующие мнения относительно понятия «агент». Проводится сравнительный анализ существующих в настоящее время агентных архитектур и стратегий функционирования мультиагентных систем. Рассматривается пригодность мультиагентного подхода для решения задач по анализу сложных изображений. Во второй главе работы вводится понятие агента для мультиагентной системы анализа изображений и описывается состав среды такого агента. Затем, исходя из состава среды агента, описываются задачи возникающие перед разрабатываемым агентом в такой среде и предлагается функциональная модель позволяющая полностью описать функционирование всякого агента мультиагентной системы анализа изображений. Предлагается структурная модель агента МСАИ, обеспечивающая ему возможность решения всех задач, которые могут возникнуть перед ним в процессе его функционирования в среде. Делаются выводы о принадлежности разработанного агента к классу гибридных агентных архитектур. Далее описывается разработанный алгоритм взаимодействия типового агента МСАИ с его средой. В третьей главе описывается начальные условия и ход экспериментального исследования. На примере работы сформированных в ходе эксперимента агентов уровня примитивов показана работоспособность разработанного алгоритма взаимодействия агента МСАИ с его средой. В заключении сформулированы основные научные и практические результаты полученные в данной работе.
Делиберативная архитектура
Делиберативная (совещательная) архитектура представляет собой классический подход к построению агентов. Его суть состоит в том, чтобы рассматривать агенты как системы, основанные на знаниях. Эта парадигма известна как символический искусственный интеллект. Основой символической парадигмы, в сфере искусственного интеллекта, является гипотеза физической символической системы, сформулированной Ньюэллом и Саймоном [35]. Физическая символическая система определена как: Физически реализованный набор физических сущностей (символов), который может быть скомбинирован в виде структур, которые способны управлять (осуществлять) процессами на символах согласно инструкциям, являющимся набором символических кодов. Далее гипотеза о физических символических системах утверждает, что такая система способна осуществлять общее интеллектуальное поведение.
Одна из первых систем, в которой использовались методы автоматического планирования последовательности действий агента, выполнение которых приводит к некоторой желаемой цели - STRIPS [18,37,60,77]. Эта система действовала на основе символического описания мира и состояния желаемой цели, а также описания множества операций, характеризуемых пред и постусловиями. Система находила последовательность своих действий, которая вела к цели, на основе простого анализа средств и целей, который по существу связывал постусловия операций с желаемой целью. Символическое описание STRIPS (модели предметной области) — пространство состояний. Характерными чертами планировщика STRIPS являются: представление состояний пространства состояний через формулы логики первого порядка, использование правил вывода, анализ конечных значений и проверка предусловий операторов (действий) и целевой формулы. Система также была снабжена механизмом обучения через обобщение найденных планов и их хранение. До сих пор отдельные компоненты системы (например, способ описания предметной области) активно используются.
Алгоритм планирования STRIPS очень прост и хорошо работает для задач умеренной сложности, когда среда агента статична и хотя бы частично формализована.
Другой пример агента (HOMER) [18,60,63] позволяет продемонстрировать лингвистические способности автономного агента, способного планировать свои действия и реализовывать их. HOMER моделирует подлодку, которая существует в двухмерном море, о котором она имеет только частичные знания. Агент получает инструкции от пользователя на ограниченном английском языке со словарем из 800 слов, инструкции могут содержать среднестатистические временные ссылки. HOMER по полученным инструкциям составляет и реализует соответствующий план своих действий. Агент имеет ограниченную память и использует ее для подготовки сообщения о реализации своего плана. Действия агента строго соответствуют разработанному им плану, который в свою очередь полностью предопределён инструкциями пользователя и априорными знаниями агента о среде.
Впоследствии были приложены значительные усилия к созданию более эффективных методов. Для более сложных задач даже при статичности среды агента целесообразнее искать не просто цепочку действий агента, а выстраивать иерархию подцелей, различая их тем самым по важности. Подзадачи, решаемой агентом исходной задачи, как правило взаимозависимы, что вызывает необходимость чередовать определённым образом действия агента, направленные на достижение разных подцелей. В результате появились, по крайней мере, два основных метода: иерархическое и нелинейное планирование. Однако в середине 80-х стало ясно, что даже эти методы будут недостаточны для динамических сред.
Стратегии функционирования мультиагентных систем
В настоящее время принято выделять три подхода к решению задач: централизованный, распределённый и смешанный. Все эти подходы используются при построении мультиагентных систем искусственного интеллекта. Каждый из указанных подходов имеет свою область применения. Они не являются конкурирующими подходами к решению сложных задач [51,64]. Предметом исследования мультиагентных систем независимо от используемого подхода к решению задач является организационная структура, образуемая в результате организационно-управленческого взаимодействия членов некоторого сообщества при решении им исходной задачи.
Централизованный подход [10,37,51,71,72], прежде всего, характеризуется наличием в составе системы модуля, исполняющего роль центрального координатора действий этой системы. При данном подходе планы индивидуальных агентов создаются раздельно, а затем отправляются в «центральный координатор», анализируются им, идентифицируются потенциальные взаимодействия, которые могут привести к конфликтам, и группируются в последовательность опасных ситуаций. Затем, координатор вставляет коммуникационные команды в индивидуальные планы, что позволяет агентам синхронизировать свою работу. То есть, каждый агент рассылает координатору сообщения о планируемых действиях. Координатор строит план, который определяет для каждого агента его действия, включая действия ухода от коллизий (рис. 1.7 «Централизованная мультиагентная система»).
Таким образом, основная нагрузка по построению плана решения задачи, стоящей перед системой, возлагается на центральный координатор. Кроме того, наличие центрального координатора действий системы обуславливает некоторое превалирование в них процесса планирования, по сравнению с другими процессами. Другой особенностью централизованного подхода является то, что дерево целей для той или иной глобальной задачи должно быть задано координатору априори. Отдельные агенты лишь реализуют достижение необходимых локальных целей. Тем самым централизованный подход оказывается пригодным для решения только таких задач, для которых отсутствует неопределенность по статической структуре. То есть, системы с централизованной архитектурой по функциональным возможностям схожи с классическими экспертными системами, со всеми присущими им достоинствами и недостатками.
Концепция распределённых систем (децентрализованного управления) в общих чертах представляет собой следующее [10,15,26,33,37,71,72]. В некоторой среде функционирует некоторая достаточная с точки зрения решаемых задач совокупность независимых решающих систем (агентов). В этой же среде заданы некоторые правила (ограничения) поведения агентов и задана некоторая глобальная цель. Каждый из агентов, удовлетворяя ограничениям среды, преследуя свою локальную цель и согласуя свои действия с другими агентами коллектива - участвует в процессе достижении коллективом некоторой глобальной цели. Если глобальную цель преследует необходимый и достаточный коллектив агентов, то она, безусловно, будет достигнута (она может быть представлена как состоящая из частных целей агентов коллектива). Глобальная цель состоит из частных целей в том смысле, что достижение каждым из агентов своей частной цели приводит к достижению глобальной цели коллективом агентов. Первоначально, в ответ на формулировку конкретной глобальной цели откликаются (готовы с ней работать) несколько агентов, но с учётом действующих в среде ограничений остаётся один агент. Роль оставшегося агента — упростить исходную цель: представить её совокупностью подцелей. Формулировка подцелей приводит к новому конкурсу среди агентов. Этот процесс продолжается до тех пор, пока не будут сформулированы подцели (подзадачи), решение которых становится доступным для соответствующих агентов коллектива.
Таким образом, основным признаком задач, на решение которых ориентированы системы с децентрализованной координацией агентов, является невозможность априори редуцировать решаемые системой задачи. Результатом достижения коллективом агентов конкретной глобальной цели являются её редукция на подцели, определение конкретного коллектива агентов, обеспечивающего достижение конкретной глобальной цели, структура связей между агентами, формируемая на период решения конкретной исходной задачи, и собственно решение исходной задачи (рис. 1.8 «Распределённая мультиагентная система»).
Задачи агента и его функциональная модель
Задачи агента - это обязательства, которые берёт на себя агент по поручению другого агента или пользователя. Как следует из предыдущего параграфа такими обязательством для описываемого агента являются простые задачи, а решение всякой простой задачи может быть представлено как совокупность актов классификации. Существует два способа постановки задачи классификации [22]:
1) В признаковом пространстве задано N классов своими эталонами Хср и всякий объект относится к тому классу, для которого minj (XCRJ - Xj). Таким образом, всё пространство свойств разбивается на N кластеров. В такой случае, любой исследуемый объект всегда может быть отнесён к одному из известных классов (рис. 2.2). Данный способ классификации основан на концепции «всезнайства» субъекта исследующего объект.
2) Задан некоторый критерий компактности є, задано признаковое пространство и совокупность классов своими представителями. Всякий объект будет отнесён к некоторому классу Cj, если расстояние до представителя этого класса, от рассматриваемого объекта, удовлетворяет критерию компактности данного класса (рис. 2.3) Xcpj xi є . Здесь исследуемый объект будет отнесён к некоторому известному классу только в том случае, если он будет иметь с эталоном этого класса «достаточно» много общего, т.е. будет удовлетворять критерию компактности данного класса.
Если же объект не будет отнесён ни к одному известному классу, он будет классифицирован как «неизвестный» или как фон. Необходимой предпосылкой решения указанных задач классификации является требование не пересекаемости подмножеств множества объектов в пространстве свойств. Данный способ классификации учитывает неполноту знаний агента, устраняя проблему «всезнайства» предыдущего. Это позволяет агенту выявить необходимость и инициировать процесс обучения, то есть изменения и пополнения своей системы знаний о предметной области.
Поскольку разрабатываемый в данной работе агент основан на концепции конечности его знаний, следует выбор второго способа постановки задачи классификации для разрабатываемого агента. Модель опознаваемого объекта представляет собой для агента вектор признаков х s и их значений.
Итак, задачей агента является задача классификации данных поступающих к агенту от его среды, и эта задача является простой. При этом данные, поступающие от среды к агенту МСАИ, принципиально разделяются на два потока. На поток данных о целях (нисходящий анализ) и поток данных об анализируемом элементе среды агента (восходящий анализ). Таким образом, всякий агент системы анализа изображений должен быть способен участвовать в двух процессах: поиск, управляемый целями (операция ограничения, многоэтапное исполнение которой должно привести к системе простых целей агентов) и поиск, управляемый данными (операция обобщения, многоэтапное исполнение которой должно привести к решению исходной задачи поставленной перед МСАИ в целом). В первом случае осуществляется поиск свойств, различающих классифицируемые объекты, а во втором случае - поиск общих свойств, классифицируемых объектов. Тогда функционально агент может быть описан в виде пары обобщённых продукций Поста (2.2): индексы f или 1 обозначают направление поиска; I — уникальный идентификатор агента; S - обобщённая модель знаний агента. Данная модель задана агенту в виде вектора признаков. Р - условие применимости агента. Представляет собой требования соответствия обобщённой модели знаний агента описываемой вектором признаков S - модели конкретной ситуации, предлагаемой для классификации агенту в данный момент (описываемой некоторым вектором признаков Sj). Если предъявленная агенту ситуация не соответствует модели знаний агента - такая ситуация считается неадекватной данному агенту.
А - посылка правила. Описывает область определения признакового пространства состояний агента. Если предъявленная агенту ситуация означивается вне этой области, это служит сигналом к обучению агента.
В — заключение правила. Если в результате произведённой классификации предъявленная агенту ситуация была им опознана как принадлежащая некоторому априори известному агенту классу состояний - заключения правила принимает значение «истина». В противном случае, если предложенная ситуация была отнесена к фону, заключение правила принимает значение «ложно», что так же служит сигналом к обучению агента.
Описание программно - аппаратной системы для проведения эксперимента
Целью проводимых экспериментальных исследований является проверка работоспособности разработанного алгоритма взаимодействия агента с его средой и программно-методического комплекса, реализующего функции необходимые для решения основной агентной задачи. Для этого были поставлены следующие задачи:
Рассмотреть процесс формирования признаковых пространств агента (пространства целей и обобщения) и их структурирования, т.е. процесс формирования БЗ агента.
Рассмотреть процесс формирования коллектива агентов, на примере создания совокупности агентов уровня примитивов, соответствующей текущей цели пользователя. Определить зависимость коллектива горизонтально взаимодействующих агентов от неоднородности анализируемых данных и заданной точности анализа. Предполагается, что в начальный момент коллектив агентов представлен только корневым агентом. Получив от пользователя описание текущей цели, корневой агент инициирует диалог с пользователем, конечным результатом которого будет являться заданная пользователем выборка на поле анализируемого изображения, элементы которой соответствуют текущей цели пользователя. В данном эксперименте корневой агент не создавался, но его функционирование в плане взаимодействия с нижележащими агентами моделировалось. Соответственно в эксперименте не рассматривается и задача коммуникации корневого агента и конечного пользователя мультиагентной система анализа изображений. В качестве исходных данных для эксперимента был взять космофотоснимок «Landsat ТМ» лесов приполярного Урала, (рис. 3.1). Каждая точка такого снимка описывается её значением по каждому спектральному каналу использующимся при съёмке. Начальное множество признаков описывающих точки данного изображения, приведено в таблице 3.1.
Экспериментальные исследования проводились на установке, созданной на базе IBM-совместимой ПЭВМ. Программный комплекс, реализующий функции разработанного агента, был создан с использованием языка программирования Java, в среде разработки NetBeans. Данный комплекс представляет собой систему директивного типа. Обобщённая структура разработанного комплекса представлена на рисунке 3.2. Рассмотрим компоненты входящие в структуру комплекса:
Пользовательский интерфейс - предназначен для ввода пользователем, с клавиатуры либо посредством манипулятора типа «мышь», управляющих команд и отображения полученных результатов на экран монитора. Интерфейс пользователя организован в виде рабочей формы, поля которой заполняются пользователем (рис. 3.3).
Пользователь заполняет необходимые пути, указывающие места хранения на жёстком диске текстовых файлов содержащих информацию о текущей задаче агента. Так же заполняется поле идентификатора текущего агента. Идентификатор представляет собой буквенно-числовую комбинацию. Буква обозначает уровень агента в иерархии коллектива (Р, W, S, К, Т), а последующее число - уникальный идентификатор агента на данном уровне.
По нажатию кнопки «получить список агентов» пользователь может просмотреть идентификаторы всех уже существующих агентов МСАИ, хранящихся в рабочем каталоге системы.
По нажатию кнопки «загрузить агент» происходит считывание БЗ текущего агента из текстового файла, хранящегося на жёстком диске, в оперативную память ЭВМ. Опознавание необходимого файла осуществляется по заданному идентификатору агента. Если же БЗ текущего агента пуста, то в рабочем каталоге создается подкаталог вида «/рабочий каталог/уровень агента/идентификатор агента/», который будет являться рабочим каталогом для текущего агента.
По нажатию кнопки «расчёт признаков» пользователю предоставляется выбор из списка признаков методы расчёта которых известны системе (содержатся в ОАР МСАИ). Пользователь может выбрать признаки, расчёт которых необходимо произвести. Кроме того от пользователя требуется указать путь, по которому будет сохранён результат расчёта. После чего системой осуществляется вычисление указанных пользователем признаков, для изображения, путь к которому указан в поле ввода «путь к изображению».
По нажатию кнопки «декорреляция» осуществляется декорреляция признаков методом главных компонент, для изображения, путь к которому указан в строке ввода - «путь к изображению».
