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

ВВЕДЕНИЕ

ШВА I. АНАЛИЗ ЛОГИКО -ЛИНГВИСТИЧЕСКИХ МОДЕЛЕЙ В СИСТЕМАХ ОПЕРАТИВНО-ДИСПЕТЧЕРСКОГО УПРАВЛЕНИЯ СЛОЖНЫМИ ОБЪЕКТАМИ. J5.

1.1. Логико-лингвистические модели управления . Т5,

1.2. Методы представления информации в системах оперативно-диспетчерского управления сложными объектами

1.3. Основные понятия о семантических сетях . 31,

1.4. Структура семантических сетей . 38.

Выводы по первой главе .47,

ГЛАВА 2. ДЕДУКТИВНЫЙ ВЫВОД НА СЕМАНТИЧЕСКИХ СЕТЯХ . 48.

2.1. Принцип резолюции и его ограничения . 48,

2.2. Семантическая сеть - формализм для представления знаний в системах оперативно-диспетчерского управления.56.

2.3. Семантическая унификация.68.

2.4. Методы дедукции на семантических сетях в системах управления и принятия решений . 78,

2.5. Особенности семантических сетей в системах управления.87,

Выводы по второй главе . 95,

ГЛАВА 3. АЛГОРИТМИЧЕСКИЕ ОСНОВЫ ДЕДУКТИВНОГО ВЫВОДА НА

СЕМАНТИЧЕСКИХ СЕТЯХ .96.

3.1. Алгоритм дедукции на раскрашенных семантических сетях (Алгоритм .gg^

3.2. Алгоритм дедукции с использованием операторов удаления и расщепления вершин семантических сетей (Алгоритм . 102.

3.3. Полный алгоритм дедукции на семантических сетях (Алгоритм О^ъ") . 115.

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

Выводы по третьей главе . 124.

ГЛАВА 4. РЕАЛИЗАЦИЯ СИСТЕМЫ ОПЕРАТИВНО-ДИСПЕТЧЕРСКОГО

УПРАВЛЕНИЯ ЭНЕРГООБЪЕДИНЕНИЕМ. 125.

4.1. Принципы построения СПРИНТ . 125.

4.2. Постановка задачи автоматизации процессов поиска решений в системе СПРИНТ . 129.

4.3. Архитектура и принципы организации вычислительного процесса в система управления и принятия решений. 130.

4.3.1. Функциональная интерпретация архитектуры системы управления и принятия решений. 131,

4.3.2. Описание классов вычислительных процессов в системах управления и принятия решений . 134.

4.3.3. Организация вычислительного процесса принятия решений . 135,

4.3.4. Организация вычислительного процесса адаптации системы к предметной области . 138,

4.3.5. Организация вычислительного процесса администрирования системы . 140.

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

4.4. Архитектура системы "СПРИНТ" .145.

4.4.1. Архитектура комплекса технических средств . J45.

4.4.2. Архитектура комплекса программных средств "СПРИНТ" .147,

4.4.3. Архитектура компилируемого комплекса программных средств "СПРИНТ" .149.

4.4.4. Архитектура интерпретируемого комплекса программных средств.151.

4.4.5. Организация работы системы в ОС ЕС .154.

Вывода по четвертой главе .Х55.

ГЛАВА 5. МНОГОЭТАПНОЕ РАСПОЗНАВАНИЕ СОСТОЯНИЙ СЛОЖНОГО

ОБЪЕКТА С ДИНАМИЧЕСКИМИ ХАРАКТЕРИСТИКАМИ. 156.

5.1. Описание модели многоэтапного распознавания объектов . J56.

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

CMP-LISP . jgj i

Выводы по пятой главе . j7j

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

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

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

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

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

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

Рассматриваем^ класс сложных технологических объектов типа энергосистем и систем многоэтапного распознавания характеризуется тем, что многие из существующих алгоритмов управления не позволяют находить управляющие решения в заданные сроки даже на современных ЭВМ. Поэтому"решающим элементом? который в настоящее время в таких системах реализует алгоритмы оперативного управления, является человек-диспетчер. Исследования деятельности человека при оперативном управлении сложными объектами показали, что в стереотипных классах состояний объекта управления - классах ситуаций у человека всегда имеется модель поиска управляющих решений /27. Для ситуаций, не входящих в класс стереотипных, человек пытается строить такую модель на основе накопленных знаний и опыта управления.

По мере того, как зависимость управляющих решений от ситуации в системах оперативно-диспетчерского управления становилась все более сложной, использование численных алгоритмов поиска решений сделалось невозможным как из-за проблемы размерности, так и из-за временных ограничений. Поэтому в разработанных системах (СПРИНТ-LISP и СМР-/ЛЗР) решение задачи автоматизации процессов классификации и поиска решений предлагается проводить методами логического поис

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

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

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

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

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

В рамках данной диссертационной работы решаются следующие вопросы:

1) разработка теоретических принципов представления знаний о предметной области в виде семантических сетей;

2) разработка, моделирование и исследование алгоритмов дедуктивного вывода на семантических сетях;

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

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

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

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

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

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

Основные положения диссертационной работы доказаны теоретически и подтверждены экспериментальными данными, полученными при реализации в двух системах оперативно-диспетчерского управления (СПРИНТ -LZSP и CMP - LISP ).

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

- организации диалога на языке, ограниченном рамками профессиональной лексики;

- автоматизации процессов классификации ситуаций, поиска и обоснования управляющих решений;

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

Результаты диссертационной работы внедрены в системе оперативно-диспетчерского управления энергообъединением (ЦНИИ комплексной автоматизации (ЦНИИКА) ) и в многоэтапной системе распознавания Св/ч 56020), что подтверждается соответствующими актами внедрения.

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

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

- в системе СПРИНТ- LI$P управления энергообъединением для автоматического формирования управляющих рекомендаций, принимаемых при оперативно-диспетчерском управлении энергосистемами (ЦНИИКА);

- в системе СМР-££>Р для формирования алгоритма управления многоэтапной системой распознавания (в/ч 56020).

Пакет программ СПРИНТ-LISP реализован на ЭВМ EC-I033 на языке LISP и имеет объем порядка 1300 функций языка LISP (350 килобайт памяти ЭВМ).

Пакет программ (Ж-LISP управления многоэтапной системой распознавания имеет объем около 900 функций языка LTSP (250 килобайт).

Апробация работы. Основные положения диссертации докладывались и обсуждались на Всесоюзной школе-семинаре "Семантические аспекты формализации интеллектуальной деятельности" (Телави, 1983), "Логико-алгебраические модели представления знаний в экономических, технических и организационных системах" (Ашхабад, 1983), "Программные системы для семиотического моделирования и ситуационного управления" (Калининград, 1983), на семинарах: "Интеллектуальные банки данных" (Бакуриани, 1980), "Интерактивные системы" (Боржоми,1980), "Методы разработки и опыт эксплоатации АСУ" (Тбилиси, 1981), "ХХШ Республиканская конференция профессорско-преподавательского состава ГПИ" (Тбилиси, 1981), на научных семинарах кафедры ПМ и Щ АН СССР.

Публикации. Материалы по данной диссертационной работы опубликованы в 10 статьях и I отчете по НИР.

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

Выводы по пятой главе

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

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

2. принципиальную возможность использования алгоритмов дедуктивного вывода для построения системы многоэтапного распознавания структурно-информационных объектов;

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

СПРИНТ-£/5/7" оперативного управления энергообъединением, а также для построения алгоритма распознавания объектов в системе многоэтапного распознавания"СМР-/,/15/7 Реализация этих алгоритмов показала их пригодность для обработки семантических сетей размерностью 200 и более вершин.

7. Экспериментальное моделирование и внедрение разработанных алгоритмов и программ системы "СПРИНТ-/,/^/7 " и "<Ж-Ы£Р " показало: а) обоснованность применения теоретических принципов, положенных в основу создания таких систем; б) принципиальную возможность использования алгоритмов дедуктивного вывода и их эффективность для построения систем оперативно-диспетчерского управления сложными объектами.

Результаты диссертационной работы внедрены в двух организациях (ЦНИИКА и в/ч 56020), что подтверждается соответствующими актами внедрения (см.Приложения 2 и 4).

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

2. Поспелов Д.А., Пушкин Б.Н., Мышление и автоматы. М., Советское радио, 1972, 224 с.

3. Автоматизация управления энергообъединениями. Под ред. Совалова С.А. М., Энергия, 1979, 432 с.

4. Mylopoulos J, An Overview of Knowledge Representation.SIGART News Lettle . )^74,I98I,pp5-I8.

5. Кузин Л.Т. Основы кибернетики, т.2. Основы кибернетических моделей. М., Энергия, 1979, 584 с.

6. Попов Э.В., Фирдман Г.Р. Алгоритмические основы искусственного интеллекта и интеллектуальных роботов. М., Наука, 1976, 456 с.

7. Башлыков А.А. Реализация "интеллектуальной" системы управления энергообъединением. М., Экспресс-информация. Средства и системы управления в энергетике, 1978, № II. с.8-11.

8. Башлыков А.А. Логико-модельный подход к проектированию и построению АСУ ТП. Тезисы докладов респ.НТС "Метода и модели в задачах управления производством", Таллин, 1979.

9. Bonczek R.H., Whinston А.В. The integration of network database management and problem resolution. "Information зуз terns". Vol.4, #2, 1979, pp.143-154.

10. Griffith R.L. Three principles of representation for semantic networks. ACM Transactions on Database Systems,

11. Vol.7, №3, 1982, pp. 417-442.

12. Korf R.E. Toward a model of representation Changes. "Artificial Intelligence". 1980, V.I4, PP.41-78.

13. Брябрин В.М. Диалоговая информационно-логическая система. М., Научный Совет по комплексной проблеме "Кибернетика", 1977.

14. Коен Ф., Милопулос Д., Борджида А. Некоторые аспекты представления знаний. Труды I МОКИИ, 1975, т.2, с.2.42-2.S4.

15. Вольфенгаген В.Э., Воскресенская О.В., Горбанев Ю.Г. Система представления знаний с использованием семантических сетей. Вопросы кибернетики, вып.55. М., АН СССР, Научный Совет по комплексной проблеме "Кибернетика", 1979, с.49-69.

16. Вольфенгаген В.Э., Вязьмин С.А., Рыбина Г.В. Фреймы в системе представления знаний. Информационно-программное обеспечение систем искусственного интеллекта. М., МДНТП им.Ф.Э.Дзержинского, 1978, с.18-26.

17. Виноград Т. Программа, понимающая естественный язык. Мир, 1976, 230 с.

18. Гладун В.П., Рабинович З.Л. Формирование модели мира в системах искусственного интеллекта. М., Научный Совет по комплексной проблеме "Кибернетика", 1977.

19. Гладун В.П., Ващенко Н.Д. Методы формирования понятий на ЦВМ. Кибернетика,,1975, № 2.

20. Associative Networks.Representation and Use of Knowledge by Computers.Edited by N.V.Findler.Academic Press N.Y. 1979.

21. Hayes Ph.J. On semantic nets,frames and associations. Proceedings of the 5-th International Joint Conference on Artificial Intelligence, 1977, PP.99-107.

22. Rossopoulos N.D. A Semantic Network Model of Data Bases. -Toronto,1977.

23. Roussopoulos N, Mylopoulos J. Using Semantic Network for

24. Data Base Management.-Proc. of the I Int.Conf. on Very Large Data Bases, Boston, 1975, 50 p.

25. Чень 4., Ли P. Математическая логика и автоматическое доказательство теорем. М., Мир, 1983, 360 с.

26. Robinson J.A. A Machine-Oriented Logic Based on the Resolution Principle .J.ACM, 12,№ I, 1965, pp.23-41.

27. McSkimin J.R., Minker J., A Predicate Calculus Based Semantic Networl for Deductive Searching. В Associative Networks . Representation and Use of Knowledge by Computers.Edited by

28. N.V. Findler. Academic Press. N.Y. 1979.

29. Бужгулашвили Г.Т1., Кикнадзе В.Г., Ломинадзе Н.Н. Об организации вариантного анализа в задачах автоматизированного проектирования узлов ЭВМ. Техническая кибернетика. Научные труды ГПИ № 5(250). Тбилиси, 1982, с.59-62.

30. Босикашвили З.Б., Датунашвили М.Д., Кикнадзе Б.Г., Перадзе Л.В. Построение словаря для диалоговой системы общения с ЭВМ на естественном языке. Техническая Кибернетика. Научные труды ГПИ7(239), 1981, с.13-16.

31. Босикашвили З.Б., Кикнадзе Б.Г. Диалоговая система для общения с модельным роботом на естественном языке. Грузинский республиканский семинар "Человеко-машинные системы". Тезисы доклада. Тбилиси, 1980, с.70-75.

32. Попов Э.Б. Общение с ЭВМ на естественном языке. М., Наука,1982, 360 с.

33. Кикнадзе В.Г. Дедукция на семантических сетях. Научно-техническое совещание. Логико-алгебраические модели представления знаний. Ашхабад, 26-28 сентября 1983 г. (Тезисы докладов). Ашхабад. Ылым, 1983, 13 с.

34. Кикнадзе В.Г. О дедуктивных моделях представления знаний. Семиотические аспекты формализации интеллектуальной деятельности. Школа-семинар "Телави-83". Тезисы докладов и сообщений. Москва, 1983, с.66-67.

35. Kowalski R. "A Proof Procedure Using Connection Graphs", JACK 22 (1975), p.572-595.

36. Logic and Data Bases. H.Gallaire and J.Minker, eds., Plenum press, JTew York, 1978.

37. Winograd T. Extended inference modes in reasoning by computer systems.J.Artificial Intelligence. 1980, v.13, iJ? 1-2, pp.5-26.

38. Plaisted D.A. A Simplified problem reduction format. J. Artificial Intelligence. 1982. v.18, №3, pp. 227-261.

39. Davis R. Meta-Rules: reasoning about Control. Artificial In -telligence. 1980. V.I5, №3, pp.179-239.

40. Goad C.A. Proofs as descriptions of computation . Lecture notes on computer science. 1980, if 87, pp. 39-52.

41. Frickson R.W. The AFFIRM theorem prover: proof forests and management of large proofs. Lecture notes on computer science. 1980, В 87, pp.220-231.

42. Henschen L.J. Theorem proving by Covering Expressions. Journal of the Association for Computer Machinery. Vol. 26, }? 3. July 1979. pp. 385-400.-17948. Поспелов Д.А. Больше системы. Ситуационное управление, М., Знание, 1975, 64 с.

43. Поспелов Д.А. Семиотические модели: успехи и перспективы. Кибернетика, 1976, №6, с. II4-I23.

44. Поспелов Г.С., Поспелов Д.А. Влияние методов теории искусственного интеллекта на решение традиционных задач управления. М., Научный Соеет по комплексной проблеме "Кибернетика", 1977.

45. Уитсон П. Искусственный интеллект. М., Мир, 1980, 520 с.

46. Хант Э. Искусственный интеллект. М., Мир, 1978, 560 с.

47. Ефимов Е.И. Решатели интеллектуальных задач. М., Наука, Главная редакция физико-математической литературы, 1982, 320 с.

48. Шенк Р. Обработка концептуальной информации. М., Энергия, 1980, 360 с.

49. Минский М. Фреймы для представления знаний. М., Энергия, 1979, 152 с.

50. Марков А.А. Теория алгоритмов. Труды института им. СтеклоЕа, т.ХП. М., АН СССР, 1954, 376 с.

51. Башлыков А.А., Вагин В.Н. Принципы организации дедуктивных процессов в системах принятия решений. Тезисы докладов всесоюзной конференции "Семантические модели при управлении большими системами", М., 1979.

52. Башлыков А.А. Языки определения и манипулирования знаниями семиотических моделей АСУТП. В сб. "АСУ технологическими процессами", МДНТП, М., 1980, с.94-96.

53. Башлыков А.А. Концепция банка знаний в АСУП", Таллин, 1980.