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

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

Латынцев Андрей Александрович

АГЕНТ СИСТЕМЫ АНАЛИЗА СЛОЖНЫХ ИЗОБРАЖЕНИЙ

05.13.17 — Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата технических наук

Красноярск - 2005

Работа выполнена в Красноярском государственном техническом университете

Научный руководитель:' к.т.н., профессор Цибульский Г.М.

Официальные оппоненты: д.т.н., профессор Л.Ф. Ноженкова к.т.н., доцент Г.С. Кирякова

Ведущая организация: Институт леса им. В.Н. Сукачёва СО РАН.

Защита состоится «12» апреля 2005г. в 14 часов в аудитории Г-417 на заседании диссертационного совета К 212.098.02 при Красноярском государственном техническом университете по адресу:

С диссертацией можно ознакомится в библиотеке Красноярского государственного технического университета.

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

Автореферат разослан « 12 » ндрга 2005 г.

Учёный секретарь диссертационного совета

660074, Красноярск, ул. Киренского, 26

К 212.098.02

Кузьменко Н.Г.

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

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

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

Для достижения сформулированной щели были поставлены следующие задачи:

1. Определить понятие «агент», применительно к задаче анализа изображений.

2. Определить состав среды агента.

3. Определить круг задач, возникающих перед сформулированным агентом.

4. Разработать структурную и функциональную модели агента.

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

На защиту выносятся;

1. Определение понятия «агент» системы анализа изображений

2. Состав среды агента.

3. Задачи агента.

4. Структура агента.

5. Функциональная структура агента.

6. Алгоритм взаимодействия агента со средой. Научная новизна;

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

2. Описаны все задачи агента и определена необходимая для их решения структура агента.

3. Определена функциональная модель агента, позволяющая формализовать рассматриваемого агента.

4. Разработан алгоритм взаимодействия агента с его средой, реализующий решение агентной задачи.

носит актуальный характер.

РОС. Н<Чи'-0ИДЛ!,(14Я биг.»; нот '„хл з

СПетербург

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

Использование результатов диссертации. Основные результаты работы были внедрены в Институте леса им. В.Н. Сукачёва СО РАН.

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

Апробация работы. Материалы диссертационной работы докладывались и обсуждались: на семинаре кафедры «Системы искусственного интеллекта» Красноярского государственного технического университета (2005г.); на семинаре кафедры «Информатики и вычислительной техники» Сибирского Аэрокосмического Университета (2005г); на Всероссийской научно-методической конференции «Повышение качества непрерывного, профессионального образования» в г. Красноярске (2005г.); на семинаре лаборатории мониторинга леса в Институте леса им. В.Н. Сукачёва СО РАН (2005г.).

Публикации. По материалам диссертации опубликовано 4 печатные работы. Структура и объём работы. Диссертация состоит из введения, трёх глав, заключения и приложения. Всего 138 страниц машинописного текста и приложения. Библиография содержит 101 наименование.

СОДЕРЖАНИЕ РАБОТЫ Первая глава диссертации содержит краткий обзор существующих подходов к понятию «задача». В настоящей диссертационной работе под понятием «задача» будет пониматься следующее: 3 = <К,К1,КТ>,

где,

К - модель предметной области, которая содержит необходимые для решения задачи знания об исследуемом объекте, и знания о способе решения задачи;

Ка - актуальная модель исследуемого объекта (исходное знание); Кт - требуемая модель исследуемого объекта.

Задача - это ситуация, в которой для некоторой области действительности (предмета задачи) заданы модели существующего и требуемого состояний исследуемого объекта. Решением задачи называется процесс преобразования модели, существующего состояния объекта, в модель требуемого состояния: К. - Кт.

Далее рассматриваются различные подходы к решению сложных задач: централизованный, распределённый и сметанный.

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

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

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

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

В настоящее время выделяют три основных вида агентных архитектур:

- Делиберативная (классическая, совещательная) архитектура;

- Реактивная архитектура;

- Гибридная (смешанная) архитектура.

Делиберативная (совещательная) архитектура. В качестве примеров были рассмотрены следующие системы: IREM, AUTODRIVE, Softboat, PHÖNIX, IRMA, GRATE, PEA.

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

Реактивные агенты не имеют внутренней модели мира, характерной для делиберативных архитектур. Внутренняя модель мира реактивных агентов представляет собой набор правил типа «ситуация-действие», каждое из которых выбирается в соответствии с текущей ситуацией. Под ситуацией понимается потенциально сложная комбинация внутренних и внешних состояний. В качестве примеров были рассмотрены следующие системы: «моботы» Брукса, ситуативный автомат, GAPPS, RULER.

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

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

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

В качестве примеров были рассмотрены следующие системы: PRS, «Touring Machine», COSY, «футбольный агент», InteRRaP, гибридная система профориентации, гибридный агент, реализованный в рамках инструментального программного обеспечения ESWin.

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

Во второй главе дается определение простой задачи решающих систем второго рода.

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

На основании этого даётся определение понятия «агент».

Агент - решающая система второго рода, ориентированная на решение простых задач

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

На рис.1, изображен состав среды агента системы анализа изображений.

Агент

Рис. 1 Состав среды агента 6

В необходимое и достаточное окружение агента входят:

1) объект исследования (ОИ) - предметная область;

2) множество знаков внешней знаковой системы, посредством которых агент информируется о состоянии исследуемого объекта (цифровое изображение);

3) пользователь системы (П);

4) сам агент;

5) язык, как средство коммуникации пользователя и агента;

6) физические объекты, посредством которых передаются сообщения пользователя и агента, соседей и знаки внешней знаковой системы;

7) пользователь и система как единое целое, образуемое в процессе решения исходной задачи,

8) языковые средства коммуникации агента с соседями (выше и ниже стоящими агентами).

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

Рис 2. Обобщённая структура агента 7

• Планировщик осуществляет процесс планирование хода решения исходной задачи и отвечает за координацию взаимодействия всех подсистем агента.

• Компонент «Обучение агента» ответственен за модификацию знаний агента, потребность в которой может возникнуть и возникает в ходе решения всякой агентной задачи.

• Компонент «Обучение пользователя» ответственен за разъяснение пользователю системы его роли в процессе решения агентной задачи и за обучение пользователя навыкам работы с конкретным агентом.

• Компонент «Коммуникация Агент-Пользователь» осуществляет преобразование внешнего представления сообщения пользователя во внутреннее агентное и наоборот.

• Компонент «Коммуникация Агент-Агент» ответственен за связь текущего агента с его соседями.

• Компонент «Восприятие данных» осуществляет восприятие агентом анализируемого фрагмента изображения.

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

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

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

1) Операция ограничения;

2) Операция обобщения;

3) Коммуникация («агент-агент», «агент-пользователь»). Функционально агент, может быть описан, в виде обобщённой продукции

Поста:

[I; в; Р; (А В); N3

где,

I - уникальное обозначение агента;

в - описание ситуации предъявленной агенту для классификации. Р - условия применимости агента. А - посылка агентного правила. В - заключение агентного правила.

(А->В) - ядро продукции. Ядро продукции считается сработавшим, если посылка правила (А) принимает значение «истина и заключение (В) так же принимает значение «истина».

N - постусловие выполнения правила. Для рассматриваемого агента, в общем случае, постусловием будет: а) опознать реакцию среды на

произведённое воздействие; б) отреагировать сообразно полученной реакции.

Принимая во внимание указанную продукцию, обобщённый алгоритм работы агента представляет собой следующее (Рис. 3).

1) Агент переходит в активизированный режим управляющим воздействием своей надсистемы. Если признаковое описание предъявленной ему цели соответствует признаковому описанию пространства целей текущего агента, то текущий агент активируется, перейти к пункту 2, в противном случае, перейти к пункту 13.

2) Если значения описания предложенной цели удовлетворяют области определения пространства целей текущего агента, перейти к пункту 3, в противном случае перейти к пункту 5.

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

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

5) Обучение. В процессе обучения могут быть скорректированы: признаковые описания пространства целей и пространства обобщения агента; область определения каждого из этих пространств; разбиение указанных пространств на классы, то есть знания агента о конкретных целях и обобщённое знание агента о результатах достижения подцелей. Обучение, в общем случае, происходит в результате взаимодействия текущего агента с его надсистемой и соседями. Завершив обучение, агент возобновляет преследование предъявленной цели с некоторого шага, в зависимости от вида пройденного обучения.

6) Если признаковое описание предъявленного нижележащими агентами результата адекватно признаковому описанию знаний текущего агента, перейти к пункту 7, в противном случае перейти к пункту 5.

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

8) Если в результате проведённой классификации-обобщения результатов работы нижележащих агентов результат был опознан как принадлежащий к одному из известных агенту классов обобщений, перейти в пункт 9, в противном случае перейти в пункт 5.

Рис. 3. Схема обобщённого алгоритма работы агента

9) Обобщив результаты достижения подцелей, текущий агент формирует и отсылает вызвавшей его надсистеме результат собственной работы, то есть результат достижения предъявленной ему цели.

10) Если реакция надсистемы на сформированное решение отрицательна, значит, текущий агент решил поставленную перед ним задачу по достижению предъявленной цели неверно. В этом случае перейти к пункту 5. Если же реакция системы положительна, перейти к пункту 11.

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

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

13) Агент дезактивируется и возвращается в пассивный режим.

В описанном алгоритме, в пунктах (1-4) и (10-13), агент находится в режиме поиска управляемого целями. В остальных случаях агент находится в режиме поиска управляемого данными.

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

- Рассмотреть процесс формирования пространств агента (целей и обобщения) и их структурирования, т.е. процесс формирования БЗ агента.

- Определить зависимость коллектива горизонтально взаимодействующих агентов от неоднородности анализируемых данных и заданной точности анализа.

В качестве исходных данных для эксперимента был взять космофотоснимок «ЬапсЬа! ТМ» лесов приполярного Урала. Экспертом на этом изображении была задана выборка, соответствующая интересующему его классу сомкнутости листвиничника.

Начальное множество признаков описывающих точки изображения, приведено в таблица 1, где Уаг=[£(ху - М)2]/(п -1); Зке^евБ = ]Е(хи - М)3|/ (п

- ^Уаг"2; М= (Еху)/п, п = 3x3, 5x5, 7x7. После вычисления начальное множество признаков декоррелируется и упорядочиваются по информативности разделения элементов изображения со свойствами выборочных данных от всего остального. Упорядочение признаков агентом уровня примитивов показало, что наиболее информативными для выделения элементов изображения со свойствами выборочных данных (рис. 4.), оказались признаки 3-й и 4-й, таблица 2, которые и являются описанием пространства обобщения текущего агента уровня примитивов.

Все элементов изображения со свойствами выборочных данных отображаются в пространство обобщения текущего агента. Внутренняя структура данных выявляется методом ГБООАТА (рис. 5). Было определено, что структура текущих данных - два кластера в пространстве обобщения

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

Таблица 1.

№ признака Спектр альны й диапазон (мкм) пространс твенное разрешени е Характеристика отражения

1 0.45-0.515 30 0.44-0.49 мкм -хлорофилл, 9-10 каналы

2 0.525- 0.605 30 0.526-.556 мкм -хлорофилл, осадочные породы, 11-12 каналы

3 0.63 - 0.690 30 0.62-0.67 мкм - 1 канал, 0.66-0.68мкм -13,14 каналы, атмосфера, осадочные породы, флюоресценция хлорофилла

4 0.75-0.90 30 0.84-0.88мкм - 2 канал, изменение растительности, 0.74-0 Л9мкм-15-17 каналы, аэрозоли, атмосфера, облачность

5 1.55-1.75 30 1.63-1.65мкм - 6 канал, отделение снега и облаков

6 10.40-12.5 60 10.8-123МКМ-31,32 каналы, лесные пожары, вулканы, температура поверхности Земли

7 2.09-235 30 2.1-2.15мкм - 7 канал, Облачность

№ признака Функция

8 Уаг (3x3)

9 Уаг (5x5)

10 Уаг (7x7)

11 вкечупе» (3x3)

12 вкеоде» (5x5)

13 §ке>¥пе88 (7x7)

Рис. 4. «Элементы изображения со свойствами выборочных данных»

число признаке в перечень признаков в порядке их информативности разделяемость

1 X' 6,07048

2 х'.х* 6,68814

3 X', Х\ X" 6,79813

4 X"1, Х\ Ху, X' 6,89052

5 X1, х^.х'.х» 6,95058

6 X3, X4, Ху, X1, х", хш 6,99064

7 Х'1, X4, Хч, X1, X8, хш, X1 6,99682

8 •уЗ у4 уУ у' V" у'" л , л , л , л ) л ) л у Л ) л 7,00173

9 уЗ у4 уУ у! у! у|Ц у! у^ уи А у Л у А ) Л | Л | л ) л ) л ) л 7,00225

10 X3, X4, X*, X', X®, х'и, X3, X1, Xй,X' 7,00275

11 х\ х4, х", X1, X«, Хш, X1, X2, х",х',х" 7,00316

12 X3, X4, X9, X1, X8, Х1", X4, X2, Хи,Х',Хи,Х" 7,00328

13 X', X4, X*, X', X', X'", Х\ XХиЛ'Х\Х"Х 7,00332

Таблица 3 Разделяемость элементов выборки от «всего остального»

Рис. 5. Структура пространства обобщения текущего агента уровня примитивов (тёмные точки - элементы 1 -ого класса, белые точки - элементы 2-ого класса, чёрные точки - ^расклассифицированные данные)

Структура нерасклассифицированных элементов изображения выявлялась в другой системе признаков: декоррелированая система признаков упорядочивалась по информативности отделения нерасклассифицированных элементов изображения от всего остального. Такими признаками оказались 1 и 5. Выявленная структура текущих данных (2 класса и множество нерасклассифицированных данных) - структура пространства обобщения второго агента уровня примитивов: расклассифицировано 77 % ранее нерасклассифицированных элементов обладающих свойствами выборочных данных. Итого, двумя агентами было расклассифицировано 93% элементов изображения со свойствами выборочных данных, образующих пятна на поле изображения размеров от 5 пикселей (рис. 7).

Поскольку 7% элементов изображения обладающих свойствами выборочных данных и входящих в состав примитивов анализируемого изображения (пятна не менее 5 пикселей) были не расклассифицированы, возникает необходимость привлечения ещё одного агента уровня »

примитивов. Ранее описанным способом было получено пространство общения очередного агента: признаки 6 и 9. Всего текущим агентом от общего числа обработанных им элементов изображения „

расклассифицировано 72 %. Всего 3-мя агентами расклассифицировано 98% элементов изображения со свойствами выборочных данных, образующих примитивы на поле анализируемого изображения. (Рис 7).

Рис. 6. Элементы 1-ого и 2-ого класса.

Рис. 7. Элементы 4-х классов.

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

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

Рис 8. Элементы 6-и классов

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

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

2. Определена функциональная модель, позволяющая формализовать рассматриваемого агента.

3. Разработан алгоритм взаимодействия агента с его средой, реализующий решение агентной задачи.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Цибульский Г.М., Латынцев A.A. Агент и агентные задачи системы анализа изображений. «Исследовано в России», №3,2005

2. Цибульский Г.М., Латынцев A.A. Обучение агента системы анализа изображений. «Исследовано в России», №3,2005

3. Латынцев A.A. Агентный подход к решению задач. Материалы всероссийской научно-методической конференции «Повышение качества непрерывного профессионального образования». Красноярск, 5-7 апреля, 2005г. В публикации

4. Латынцев A.A. Задача обучения агента. Материалы всероссийской научно-методической конференции «Повышение качества непрерывного профессионального образования». Красноярск, 5-7 апреля, 2005г. В публикации

Соискатель:

Латынцев A.A.

Подписано в печать 01.03.2005. Формат бумаги 60x84 1/16

Усл. печ. л. 1,0 Тираж 100 экз. Заказ 58.

Отпечатано в ИПЦ КГТУ 660074, Красноярск, ул. Киренского, 28

РНБ Русский фонд

2005-4 42928

: у

? :

17

о

/- J J