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

ргв па

2 0 ноя ^пп

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

Сиротин Эдуард Евгеньевич

МЕХАНИЗМЫ ПОИСКА И АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ АВТОМАТИЗАЦИИ СУДОВОЖДЕНИЯ НА ВНУТРЕННИХ ВОДНЫХ ПУТЯХ

05.13.16 - применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (в механике)

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

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

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

Научный руководитель:

кандидат технических Цибульский Г. М.

наук, профессор

Официальные оппоненты:

доктор биологических наук, профессор

Харук В.И.

Ведущая организация:

кандидат технических Сорокин В.А. наук, профессор

Институт Вычислительного Моделирования СО РАН (г. Красноярск)

кандидат технических

Защита диссертации состоится 23 июля 2000 г. в 14С0 на

заседании диссертационного совета К064.54.01 при Красноярском

государственном техническом университете по адресу: 660074, г. Красноярск, ул. Киренского, 26.

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

Автореферат разослан .?<? июня 2000 г. Ученый секретарь диссертационного совета

к.т.н., доцент

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

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

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

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

' см. Е.И. Ефимов. Решатели интеллектуальных задач. М., «Наука» 5982г.

в работе решаются следующие задачи: 1) анализ существующих методов поиска в символических системах и разработка их классификации; (2) разработка гетерархической стратегии поиска для автоматизированной системы обеспечения безопасности судовождения на ВВП; (3) разработка структуры системы; (4) разработка алгоритмов решения задачи определения координат судна и всех объектов в зоне внимания, и задачи распознавания опасных ситуаций; (5) разработка программной системы, реализующей изложенные выше методы.

Научная новизна. В процессе проведенных исследований получены следующие основные научные результаты: 1) предложена новая классификация методов поиска в интеллектуальных системах; (2) разработана гетерархическая стратегия управления для использования в автоматизированных системах обеспечения безопасности судовождения на ВВП; (3) разработан алгоритм определения координат судна и объектов в зоне внимания по входным данным, представляющими собой радиолокационные изображения окружающей обстановки; (4) разработан алгоритм распознавания опасных ситуаций в зоне внимания на основе прогнозирования возможных перемещений судна и объектов и прослеживания во времени зон их возможного местонахождения.

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

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

Апробации работы. Основные результаты по теме диссертации докладывались и обсуждались на межвузовской научной конференции студентов, аспирантов и молодых ученых «Информатика и информационные технологии» (Красноярск, 1997г.); на научно-практической конференции «Достижения науки и техники - развитию города Красноярска» (Красноярск, 1997г.); всероссийской конференции с международным участием «РОАИ-98 Распознавание образов и анализ изображений: новые информационные технологии» (Новосибирск, 1998г.).

По теме диссертации опубликовано 4 работы, в том числе 1 работа опубликована в международном журнале «Pattern Recognition and Image Analysis» (1999г.)

Структура u объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка используемой литературы и трех приложений. Матер пат изложен на 156 страницах машинописного текста. Рисунков - 35. Библиография - 104 наименования.

СОДЕРЖАНИЕ РАБОТЫ Во введении дана общая характеристика работы, обоснована актуальность темы, поставлена цель и определены задачи исследований. Сформулированы основные положения, выносимые на защиту, научная новизна и практическая значимость полученных результатов. Дано краткое изложение содержания работы.

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

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

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

Введение понятия пространства задач в конце 60-х послужило толчком к пониманию необходимости иерархической организации

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

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

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

Конкретные пространства содержат текущее знание об исследуемом объекте, представленные в виде исходных данных, и результатов поиска в абстрактных и метапространствах.

Абстрактные пространства содержат априорное знание решающей системы об исследуемом объекте.

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

между пространствами. Метазнания - это знание обо всех элементах внешней среды решающей системы, при этом сама решающая система (или её компоненты) также является элементом этой среды.

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

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

В качестве классификационных признаков выбраны следующие: 1) объём информации, используемой для управления поиском: (2) адаптивность; (3) накопление знаний.

Первый признак представлен порядковой шкалой. Второй и третий принимают только два значения: «1» или «О».

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

Приобретение лачиш

Аоаппюцня

"эвристики

(>Леночиые Ф) нкцин

Иерархическая I !ришшп

[снерация- Нисходящее наименьших

1сровсрка Согхоставложс уточнение свершений

- •-#—--

Объем

сшриорпиИ

информации

Адшрктм Харш, ИИЛЬСОНЙ И

Рафаэля,

/

/

/

Адапгшншс ирнмср см н

мсюл равных цен,

альфа-бета)

+-----V-------

Направляемые 1 ¡«иравлмемыс /шннымн данными

(без (Ю) (хронологический

бектрекинг)

" /

/

У

/

/

----

Смешанны« (СЪаваегу)

.V------

СобраШий |'горарчичсскис

СЦЯ1ЬЮ (смс)емл (АСММУМ, Сирайи) 81(|МА)

Рис.1. Классификация методов поиска.

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

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

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

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

Внешняя среда

ч;

Рис. 2. Схема поиска при отсутствии априорного знания, управляющего процессом

поиска.

Помех 1нани*,

необходимого

_„ 1 для построения

алгоритма

решения

Знания, необходимые для построения алгоритма решения (конкретные V ^пространства)

Внешняя среда

V

Построение Исполнение

алгоритма алгоритма

решения

Ошибка

Желаемый результат достигнут

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

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

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

Определить область 1 в которой будет , у осуществляться

Управление

Данные

Рис. 4. Гетерархическая стратегия управления системой.

Третья глава посвящена разработке автоматизированной системы обеспечения безопасности судовождения на внутренних водных путях «АРМ Судоводителя». Этот процесс включал в себя следующие этапы:

1. На основе анализа процесса управления судном в пути следования сначала была разработана модель системы управления.

2. На основе интерпретации данной модели с уточнением состава и функций экспертной системы была разработана структура самой системы.

3. Проведена редукция цели на подзадачи.

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

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

6. Проведена программная реализация системы.

В качестве модели процесса управления была использована следующая (см. рис. 5.).

Здесь : 2 - цель (целевое - требуемое состояние); У - состояние объекта управления, Х- состояние среды;

I/ - управление (рекомендации ЭС для ЛПР); V - управление (воздействие ЛПР на органы управления объектом);

X' - измеренные параметры состояния среды; V - измеренные параметры состояния объекта управления;

2 = {г,} г, = [:,,} - множества подцелей;

У = ЯД, С), точнее У,-+/ = Р(Х¡,11),! - 1-й момент времени;

V = Ф(Х'1, У",-./, [/'¡.¡, V , 7, г,, ¡(¡), где Я,- - ресурсы, какими вся система располагает на 1-й момент времени, точнее,

Рис. 5. Модель системы управления.

U', = Ф(Л";, IIr(-)Z\\ (&/V)]|rw (-) г, II, Ui,Ri)\

Ui = 4> (X'h Y'i.t, U„,, Z, Zu «;), точнее,

ÜI= 4{X't, ||F' (-) Z\ (&/V) II Г(-) Zf Ц, Uui, R-,), где Ф -

функция управления (принятия решения о некотором управляющем воздействии на органы управления объектом) реализуемая JITIP, V -функция управления (принятия решения о выдаче рекомендаций ЛПР) реализуемая ЭС, ||J" (-) Z|j (||FW (-) z-, Ц) - некоторый критерий, оценивающий насколько достигаются цели Z (текущие подцели г/) при измеренных параметрах состояния объекта управления Y' (при измеренных параметрах состояния объекта управления Y' ¡.t на i-1-й момент времени), (&./V) - расшифровывается И\ИЛИ

Выход из подсистемы ЛПР обозначается как Ü= <U'„Zi>, где z i -управляющее воздействие ЛПР на ЭС, заключающееся в переопределении текущих подцелей z .

Структура системы представлена на рис. 6..

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

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

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

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

ЛПР - лицо, принимающее решение (капитан, штурман и др.)

(ЭТ

Рис. 6. Структура «АРМ Судоводителя».

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

градуса в обе стороны. Если поворот произведён в сторону, противоположную истинной, то степень близости повёрнутого таким образом тРЛИ и эталона уменьшится. Зная истинное направление поворота, необходимо поворачивать тРЛИ в данном направлении на малый угол до тех пор, пока степень близости тРЛИ и эталонного изображения с которым в данный момент сравнивается тРЛИ) увеличивается. Как только она начнёт уменьшаться, значит, оптимальный угол достигнут. Близость изображений характеризует величина - 1/С, С= 2л (FiJ - Су) , где /•'и <7 - матрицы элементов, представляющих яркость пикселей тРЛИ и эталонного изображения, соответственно. В качестве процедуры поиска глобального минимума С используется градиентный поиск, модифицированный для уменьшения вероятности остановки в локальном минимуме.

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

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

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

Рис. 7. Прогнозирование столкновения с подвижным объектом.

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

Программное обеспечение разработано на платформе MS Windovvs-95 с использованием технологий объектно-ориентированного программирования и управления событиями, COM (ActiveX), OLEAutomation. Для представления и манипулирования картографическими данными используется ГИС <(Геоконструктор 1.6.» Межпрограммное взаимодействие между компонентами системы организовано при помощи поддерживаемых MS Windows-95 механизмов DDE, OLE, общей памяти, семафоров.

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

Эксперименты проводились на учебно-демонстрационном варианте системы, который не имеет входа от РЛС, а для моделирования тРЛИ используется программный эмулятор. Кроме этого, в состав данного варианта системы включен компонент, позволяющие моделировать реальную обстановку в зоне внимания. В качестве ЭНК и РЛК использовались навигационные и радиолокационные карты 22-х километрового участка реки Енисей от места впадения реки Маны до горы «Гремячий лог». На данном участке реки обеспечивается моделирование репрезентативного множества опасных ситуаций. За время проведения экспериментов модель судна прошла по карте 2216 км. Кроме этого, для выявления точности определения координат во время старт-привязки, было проведено по 100 экспериментов в различных точках фарватера для начальных квадратных областей со сторонами от 30м до 1000м.

Результаты экспериментов показали: 1. определение координат судна с точностью 10-20м, что соответствует разрешению РЛИ, происходит в 85% случаев при старт-привязке, и в 97% - во время движения судна. Ошибочный процент возникает из-за остановки алгоритма поиска в локальных минимумах.

2. высокое быстродействие алгоритма определения координат во время движения судна (время определения 0,3 с. при скорости движения 40 км/ч), что на порядок меньше времени одного оборота антенны РЛС).

3. высокую точность и быстродействие алгоритма распознавания опасных ситуаций (ОС, при их наличии, распознавались в 100% случаев, 5% случаев распознавания при отсутствии ОС, время распознавания не превышает 3-х секунд, при сопровождении системой до 50 судов одновременно).

4. решения, принятые системой при выполнении маневров расхождения, обгона и оборота, соответствуют «Правилам плавания по внутренним водным путям РСФСР 1988г.» (тестировалось выполнение маневров в штатных ситуациях)

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

В приложениях представлены технические требования к системе предварительной обработки и передачи данных «БоРОС», предназначенное для разработчиков подобных систем.

ВЫВОДЫ

На защиту выносятся следующие результаты:

1. Классификация методов поиска в интеллектуальных системах.

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

3. Алгоритм определения координат судна и объектов в зоне внимания по входным данным, представляющими собой радиолокационные изображения окружающей обстановки, получаемые от судовой РЛС.

4. Алгоритм распознавания опасных ситуаций в зоне внимания, на основе прогнозирования возможных перемещений судна и объектов и прослеживания во времени зон их возможного местонахождения.

Основные положения диссертации опубликованы в следующих работах:

1. Е Е. Sirotin G.M. TsibuPskii. Combined Search Strategies in Systems of Image Analysis and Interpretation/ Pattern Recognition and Image Analysis vol.9, No. 2, 1999.

2. Э.Е. Сиротин, Г.М. Цибульский. Комбинированные стратегии поиска в системах анализа и интерпретации изображений/ Труды РОАИ-98, 1998г.

3. Э.Е. Сиротин. Система обеспечения безопасности судовождения на внутренних водных путях (на примере реки Енисей)/ Информатика и информационные технологии: Тез. докл. межвузовской научной конференции студентов, аспирантов и молодых ученых 1997г.

4. Э.Е. Сиротин, A.M. Кутьин. «АРМ Судоводителя» - система обеспечения безопасности судовождения на внутренних водных путях (на примере Енисея)/ Достижения науки и техники - развитию города Красноярска: сб. докладов научно-практической конференции. 1997г.

Соискатель:

ТиражЮО экз. Заказ №481 Отпечатано в типографии КГТУ 660074, Красноярск, ул. Киренского 26

ВВЕДЕНИЕ.

1. РАЗВИТИЕ ПОНЯТИЯ СИМВОЛИЧЕСКОЙ СТРУКТУРЫ.

1.1. Пространство состояний.

1.2. Пространство задач.

1.3. Представление пространства поиска в виде иерархии подпространств.

1.4. Альтернативные пространства.

1.5. Динамические пространства и множественные модели.

1.6. Символы и символические системы.

1.7. Выводы.

2. КЛАССИФИКАЦИЯ МЕТОДОВ ПОИСКА В СИМВОЛИЧЕСКИХ СИСТЕМАХ.

2.1. Выбор информативных признаков.

2.2. Слепые методы поиска.

2.3. Направленные (эвристические) методы поиска.

2.3.1. Методы поиска, использующие простейшие эвристики.

2.3.2. Методы поиска, использующие оценочные функции.

2.4. Поиск, направляемый данными.

2.5. Поиск, направляемый целями.

2.6. Комбинированный поиск.

2.7. Гетерархическая стратегия управления автоматизированной системы обеспечения безопасности судовождения на внутренних водных путях «АРМ Судоводителя».

2.8. Выводы.

3. АВТОМАТИЗИРОВАННАЯ СИСТЕМА ОБЕСПЕЧЕНИЯ БЕЗОПАСНОСТИ СУДОВОЖДЕНИЯ НА ВНУТРЕННИХ

ВОДНЫХ ПУТЯХ «АРМ СУДОВОДИТЕЛЯ».

3.1. Обзор существующих навигационных систем.

3.2. Разработка структуры системы «АРМ Судоводителя».

3.3. Алгоритм работы подсистемы определения координат судна и объектов в зоне внимания - «SADCo».

3.4. Алгоритм работы подсистемы распознавания опасных ситуаций «RDS».

3.5. Структура программного обеспечения системы.

3.6. Организация межпрограммного взаимодействия между компонентами системы.

3.7. Выводы.

4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ.

4.1. Установка для проведения экспериментальных исследований.

4.2. Исходные данные для экспериментальных исследований.

4.3. Описание экспериментов.

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

4.4.1. Анализ работоспособности алгоритма определения координат.

4.4.2. Анализ работоспособности алгоритма распознавания опасных ситуаций.

4.4.3. Анализ работоспособности экспертной системы.

4.5. Выводы.

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

Рис. 0.1. Радиолокационное изображение участка реки

Рис. 0.2. Фрагмент навигационной карты того же участка реки.

Поэтому «Правилами» [59] вводится ряд ограничений на организацию движения судов в условиях ограниченной видимости, в частности запрещается движение пассажирских судов и судов с нефтегрузами, их остатками, взрывчатыми и ядовитыми веществами [см. 59 (правило 20)].

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

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

1. анализ существующих методов поиска в символических системах и разработка их классификации;

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

3. разработка структуры системы;

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

5. разработка программной системы, реализующей изложенные выше методы.

Автор защищает:

- классификацию методов поиска в интеллектуальных системах;

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

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

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

Результаты данных исследований были опубликованы в следующих работах:

1. Е.Е. Sirotin G.M. Tsibul'skii. Combined Search Strategies in Systems of Image Analysis and Interpretation/ Pattern Recognition and Image Analysis vol.9, No. 2, 1999.

2. Э.Е. Сиротин, Г.М. Цибульский. Комбинированные стратегии поиска в системах анализа и интерпретации изображений/ Труды РОАИ-98, 1998г.

3. Э.Е. Сиротин. Система обеспечения безопасности судовождения на внутренних водных путях (на примере реки Енисей)/ Информатика и информационные технологии: Тез. докл. межвузовской научной конференции студентов, аспирантов и молодых ученых 1997г.

4. Э.Е. Сиротин, A.M. Кутьин. «АРМ Судоводителя» - система обеспечения безопасности судовождения на внутренних водных путях (на примере Енисея)/ Достижения науки и техники - развитию города Красноярска: сб. докладов научно-практической конференции. 1997г.

Основные научные и практические результаты были представлены на следующих конференциях:

1. межвузовской научной конференции студентов, аспирантов и молодых ученых «Информатика и информационные технологии» (Красноярск, 11997г.);

2. научно-практической конференции «Достижения науки и техники -развитию города Красноярска» (Красноярск, 1997г.);

3. Всероссийской конференции с международным участием «Распознавание образов и анализ изображений РОАИ-98» (Новосибирск, 1998г.); 8

Содержание работы.

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

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

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

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

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

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

В приложениях представлены технические требования к системе предварительной обработки и передачи данных «8оРБС» для разработчиков аппаратного обеспечения подобных систем. 9

4.5. Выводы

Результаты представленных в данной главе экспериментальных исследований показали:

1. высокий процент точного вычисления координат судна и объектов и высокое быстродействие алгоритма определения координат (точность определения координат от 10 до 20 м. в 85% случаев при старт-привязке и в

139

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

1. Спроектирована и программно реализована автоматизированная система обеспечения безопасности судовождения на ВВП.

2. Разработан учебно-демонстрационный вариант автоматизированной системы обеспечения безопасности судовождения на ВВП предназначенный для использования в учебном процессе.

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

140

1. Александров В.В., Горский Н.Д. Представление и обработка изображений. Рекурсивный подход. - Л.: Наука, 1985.

2. Александров В.В., Горский Н.Д. Экспертные системы анализа изображений. Л.: ЛИИАН, 1986.

3. Альсведе Р., Вегенер И. Задачи поиска: Перев. С нем. М. : Мир, 1982.

4. Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. М.: Мир, 1990 г.

5. Быков P.E., Гуревич С.Б. Анализ и обработка цветных и объемных изображений, М: Радио и связь, 1984 г.

6. Вагин В.Н., Викторова Н.П. Вопросы структурного обобщения и классификации в системах принятия решений// Изв. АН СССР. Техн. кибернетика. 1982. №5.

7. Васильев И.В. Распознающие системы. Справочник. Издание второе. Киев, Наукова думка, 1983., 424 с.

8. Винокуров и др. Корабельное радиооборудование и автономные системы навигации. Л.: Судостроение, 1988.

9. Воробьев К.Ю., Тимонькин Г. Н., Харченко В. С., Мельников В. А. Иерархическая обработка изображений и пирамидальные системы/ Зарубежная радиоэлектроника М: Радио и связь, 1991г., №7.

10. Гитлина Л.С., Голендер В.Е., Розенблит А.Б. Обобщение информации об объектах, представленных графами. Семиотика и информатика вып. 17, 1981.

11. Гладун В.П. Планирование решений. Киев: Наукова думка, 1987.

12. Гладун В.П. Эвристический поиск в сложных средах. Киев: Наукова думка, 1977.

13. Голубев А.И. Радиолокационные методы судовождения на внутренних водных путях. М.: Транспорт, 1986.141

14. Гульбинас Р.Ю. Разработка методов, алгоритмов и создание системы автоматизированного анализа структурных изображений. /Дисс. к.т.н.: 05.13.01 Каунас, 1987.

15. Дал У., Дейкстра Э., Хоор К. Структурное программирование, пер. с англ. М.: Мир, 1975.

16. Деллинг В., Эссинг Г. Диалоговые системы "Человек ЭВМ". Адаптация к требованиям пользователя. /М.:Мир. - 1984. -112 с. (сер. "Математическое обеспечение ЭВМ").

17. Денисов Д.А. Компьютерные методы анализа видеоинформации Красноярский государственный университет, Красноярск. 1991.

18. Денисов Д.А., Дудкин А.К., Плаксин М.В. Представление и обработка видеоинформации в системах машинного зрения. //Техническая кибернетика, 1989, N 5, с. 205 228.

19. Денисов Д.А., Дудкин А.К., Пяткин В.П. Структурные методы описания объектов изображений. 799.

20. Денисов Д.А., Дудкин А.К., Пяткин В.П. Цифровой анализ изображений (Методы описания геометрических структур). Препринт 747. Новосибирск, 1987. 54 с.

21. Довгяло А.М. Диалог пользователя и ЭВМ, и место средств искусственного интеллекта в его реализации //Кибернетика. N2.

22. Дракин В.И., Попов Э.В., Преображенский А.Б. Общение конечных пользователей с системами обработки данных. М.: Радио и связь, 1988

23. Дуда Р., Харт П. Распознавание образов и анализ сцен. М: Мир. 1976, 512 с.

24. Дюбуа Д., Прад А. Теория возможностей. Приложения к представлению знаний в информатике: Пер. с фр. М.: Радио и связь, 1990 г.

25. Ефимов Е.И. Решатели интеллектуальных задач М.: Наука,1982.

26. Искусственный интеллект, в 3-х кн., кн. 1. Системы общения и экспертные системы М.: Радио и связь. - 1990.142

27. Искусственный интеллект: в 3 книгах, кн. 2. Модели и методы / Справочник под ред. Э.В.Попова. М.: Радио и связь. - 1990.

28. Кибернетика: Неограниченные возможности и возможные ограничения. Перспективы развития. М.: Наука, 1981 г. (Серия "Наука и технический прогресс").

29. Клир Дж. Системология. Автоматизация решения системных задач: Пер. с англ. М.: Радио и связь, 1990 г.

30. Коутс Р., ВлеймникИ. Интерфейс "Человек-компьютер". М: Мир, 1990.

31. Кречмар В. Модель внешнего мира и ее применение для анализа изображений с помощью ЭВМ. /Дисс. к.т.н.: 05.13.16 Ленинград, 1985.

32. Крупников Г.П., Марков И.А., Подвысоцкая H.A., Сергеев М.П. Зарубежные серийно выпускаемые анализаторы изображений (обзор). //Вопросы атомной науки и техники. Серия: ядерное приборостроение, 1985, вып. Н, с. 191-217.

33. Левин Р. и др. Практическое введение в технологию искусственного интеллекта и экспертных систем с иллюстрациями на Бейсике. М. : Финансы и статистика, 1990 г.

34. Лорьер Ж.-Л. Системы искусственного интеллекта: пер. с франц. М.: Мир, 1991.

35. Луговой Н.В. О распознавании объектов специального вида. Вопросы кибернетики, вып. 100, 1983

36. Ляпиков А.П. Корабли, автоматы, роботы. Л.: Судостроение, 1985.

37. Маккалистер Дж. Искусственный интеллект и Пролог на микроЭВМ. М.: Машиностроение, 1990 г.143

38. Малышев Н.Г. и др. Нечеткие модели для экспертных систем САПР. М.: Энергоатомиздат, 1991 г.

39. Матюшков Л.П., Лихтарович A.A. Основы машинной математики. Мн.: Нар. асвета, 1988 г.

40. Мелихов А.Н. Ориентированные графы и конечные автоматы. Главная редакция физико-математической литературы изд-ва "Наука", М., 1971, 416 с.

41. Миллер Дж. Магическое число семь, плюс или минус два. //Сб. ст.: Инженерная психология. М.-1964.

42. Минский М. На пути создания искусственного разума // Вычислительные машины и мышление М: Мир, 1967.

43. Мишкинд С. И. Системы технического зрения для автоматизации машиностроительного производства//Технология машиностроительного производства. М.: НИИмаш, 1982.

44. Нильсон Н. Принципы искусственного интеллекта : пер. с англ. М.: Радио и связь, 1985.

45. Нильсон. Н. Искусственный интеллект. Методы поиска решений: пер. с англ. -М: Мир, 1973.

46. Ньюэлл А. и Саймон Г. Информатика как эмпирическое исследование/ в сб. Лекции лауреатов премии Тьюринга М.: Мир 1985.

47. Ope О. Теория графов. Главная редакция физико-математической литературы изд-ва "Наука", М., 1968.

48. Павлидис Т. Алгоритмы машинной графики и обработки изображений, М: Радио и связь, 1986.

49. Павлидис. Т. Иерархические методы в структурном распознавании образов. ТИИЭР, 1979, т. 67, N 5, с. 39-49.

50. Перспективы развития вычислительной техники: в 11кн.: Справ, пособие/ Под ред. Ю.М. Смирнова. Кн. 2. Интеллектуализация ЭВМ. М.: Высш. шк., 1989 г.144

51. Писаревский А. Н., Чернявский А. Ф., Афанасьев Г. К. И др. Системы технического зрения. Л.: Машиностроение. Ленингр. отд-ние, 1988.

52. Попов Э.В. Общение с ЭВМ на естественном языке. М.: Наука.

53. Попов Э.В. Экспертные системы: Решение неформализованных задач в диалоге с ЭВМ. М.: Наука, 1987.

54. Поспелов Г.С., Поспелов Д.А. Искусственный интеллект прикладные системы. М.: Знание.-1986. (Сер. Математика, кибернетика), по п. 2.1.

55. Поспелов Д.А. Логико-лингвистические модели в системах управления. М., Энергоиздат, 1981.

56. Поспелов Д.А., Пушкин В.Н., Садовский В.Н. Эвристическое программирование и эвристика как наука// Вопросы философии. -1967. №7.

57. Построение экспертных систем / Под ред. Ф. Хейса-Рота, Д. Уотермана, Д.Лената. М.: Мир, 1987.

58. Правила плавания по внутренним водным путям РСФСР/ Минречфлот РСФСР. М. Транспорт, 1988г.

59. Представление и использование знаний: Пер. с япон./Под ред. X. Уэно, М. Исидзука. М.: Мир, 1989 г.

60. Прэтт У. Цифровая обработка изображений М: Мир, - 1982, в 2 т., т.2

61. Садыков С.С., Кан В.Н., Самандаров И.Р. Методы выделения структурных признаков изображений. Ташкент: Фан. 104 с.63. сб. Психология машинного зрения, под ред. П. Уинстона, пер. с англ. М: Мир, 1978г.

62. Сираи Й. Анализ массивов интенсивности с использованием знаний о сценах/ в сб. Психология машинного зрения, под ред. П. Уинстона, пер. с англ. М: Мир, 1978г., сс. 112-136.

63. Советов Б.А. Информационная технология. М.: Высш. шк., 1994 г.

64. Удачин B.C., Соловьёв В.Б. Судовождение на внутренних водных путях. М.: Транспорт, 1990. 285 с.145

65. Уотермен Д. Руководство по экспертным системам : пер. с англ. М.: Мир, 1989.

66. Фатькин И.В. Разработка и исследование интерактивных методов интерпретации дистанционных изображений на основе логических методов принятия решений. Диссертация на соискание ученой степени кандидата технических наук. Ленинград. ЛЭТИ 1991.

67. Федоров Д.К., Чепин Е.В. Алгоритмы распознавания образов на основе атрибутивных грамматик для цифровой обработки изображений. Московский инженерно-физический институт. Препринт. 1988, N 008.

68. Фокс Дж. Программное обеспечение и его разработка. М: Мир, 1985.

69. Фу К.С. Структурные методы в распознавании образов. /Пер. с англ. Под ред. М.А.Айзермана. М: Мир, 1977, 320 с.

70. Хант Э. Искусственный интеллект: пер. с англ. М.: Мир, 1978.

71. Харари Ф. Теория графов. М: Мир, 1973, 302 с.

72. Хорошевский В.Ф. Интеллектуальные диалоговые системы. //ИКА.-1980. NN 5-6.

73. Цибульский Г.М. Исследование и разработка интерактивной программной системы сегментации текстурных изображений. /Дисс. к.т.н.: 05.13.16 Красноярск, 1987.

74. Цибульский Г.М., Маглинец Ю.А. К проблеме классификации методов поиска при решении интеллектуальных задач. //Сборник КГТУ, 1997 г.

75. Цибульский Г.М., Маглинец Ю.А. О семиотическом подходе к построению экспертных систем. /Математическое обеспечение и архитектура ЭВМ. Материалы научно-технической конференции "Проблемы техники и технологий XXI века" Красноярск, 1994.

76. Чен Ш.-К. Принципы проектирования систем визуальной информации: Пер. с англ. М: Мир, 1994.-408 е., ил.

77. Честнов Е.И. Судовождение на внутренних водных путях. Л.: Судостроение, 1986.

78. Чукин. Структуры данных для представления изображений. //Зарубежная радиоэлектроника. 1983, N 8.

79. Шейко Г.М. Судовые электрорадионавигационные приборы и установки управления. Л.: Судостроение, 1988.

80. Шишов С. А. Системы видения для анализа аэрофотоизображений/ Зарубежная радиоэлектроника М: Радио и связь, 1991г., №3.

81. Экспертная система для руководства сегментацией изображений. З.П.Ху, Т.Пун и Ц.Пелегрини. Центр компьютерных наук, Женевский университет. 1991.

82. Яншин В.В. Анализ и обработка изображений: принципы и алгоритмы. -М.: Машиностроение. 1994. 112с.: ил. .

83. A model-based scheme for image understanding: Pap. Meet. Appl. Artyf. Intell. VI. Orlando, F la, 4-6 Apr., 1988 / Eshera M.A.//Proc. Soc. Photo-Opt. Instrum. Eng.-1988.-937.

84. An overview of ANDES: a knowledge-based scene analysis system/ Simoni Paulo Ouvera&//4th Conf. Artif. Intell. Appl., San Diego, Calif., March 1418, 1988: Proc Washington (D.C.), 1988.

85. Ballard D., Brown C. Computer Vision Prentice Hall Inc., N.J., 1982. - 5731. P

86. Carpon R., Curci M., Ditmar E. Analyse morphologique des suires formées lors de la combustion des matériaux. Définition d'indicateurs.//Rew.met, 1994, v.91, N 2, s. 349.

87. Expert systems, image processing and image interpretation. Chassery JeanMarc, Garbay Catherine. //8th int. conf. pattern recogn., Paris. Oct, 27-31, 1986. Proc.

88. Hiromichi Iwase, Takashi Toriu, and Toshiyuki Gotoh. An expert system for image processing. //4th Conf. Artif. Intell., San-Diego, Calif., March 14-18, 1988.

89. Knowledge acquisition in image processing system "explain" /Tanaka Toshikazu, Sueda Naomich.//Proc.Int.Workshop Artif. Intell., Hitachi City, May 25-27, 1988.-New York, 1988.

90. Knowledge-based interpretation of remotely sensed images. Anita Tailor, Alan Cross, David C. Hoggt and David C.Mason. //Image and vision computing. 1986, v. 4, N 2.

91. L.J.de Haas, Automatic programming of machine vision systems, in Processings, 10th LJCAI, 1987.

92. Levine M.D., Shaheen S.I. A Modular Computer Vision System for Picture Segmentation and Interpretation // IEEE Trans. -1981. -Vol. PAMI-3, №5.

93. Matsujama T. Knowledge-based aerial image understanding systems and expert systems for image processing. IEEE Trans, on geosciense and remote sensing, vol. 6e-25, N 3, May 1987.

94. Matsuyama T. Expert Systems for Image Processing: Knowledge-based composition of image analysis Processes. //Computer Vision, Graphics, and Image Processing, v. 48, N 1, 1989, pp. 22-49.

95. Matsuyama T. Knowledge Organization and Control Structure in Image Understanding //Pro. 7th Int. Conf. Pattern Recogn., Monthreal, Juli 1984. -V. 2.-pp. 1118-1127.

96. Nagao M. Toward a Flexible Pattern Analysis Method //8th Int. Conf. Pattern Recogn., Paris, Oct. 1986.

97. Nazif A.M. and Levine M.D. Low lewel image segmentation: an expert system. //IEEE Trans on pattern analysis and machine intelligence, vol. PAMI-6, N 5, Sept. 1984.

98. Newell A., Simon M.A. Computer science and empirical enquiry: Symbol and search.-Communication of the ACM.-1976.-V.19, N3.

99. Nicolin B. and Labler R. A knowledge-based system for the analysis of aerial images. IEEE Trans. Geoscience and remote sensing, Vol. GE-25, N 3, May 1987.149