Механизмы поиска и алгоритмы решения задачи автоматизации судовождения на внутренних водных путях тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат технических наук Сиротин, Эдуард Евгеньевич

• Сиротин, Эдуард Евгеньевич
• кандидат технических наук
• 2000

Оглавление диссертации кандидат технических наук Сиротин, Эдуард Евгеньевич

ВВЕДЕНИЕ.

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

Список литературы диссертационного исследования кандидат технических наук Сиротин, Эдуард Евгеньевич, 2000 год

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