Исследование и разработка программного обеспечения задач планирования действий тема автореферата и диссертации по математике, 01.01.10 ВАК РФ

ВВЕДЕНИЕ.

ГЛАВА I.ОБЗОР РАБОТ, ПОСВЯЩЕННЫХ СИСТЕМАМ ПЛАНИРОВАНИЯ

ДЕЙСТВИЙ .Ю

1.1.Логический подход

1.2.Теоретико-графовый подход

1.3.Процедурный подход.

1.4.Логико-лингвистические модели

1.5.Вывод ы.

ГЛАВА 2. ИСПОЛЬЗОВАНИЕ СИСТЕМЫ ТЕЙЛОС ДНЯ РЕШЕНИЯ ЗАДАЧ

ПЛАНИРОВАНИЯ дайствий.

2.1.Система ТБИЛОС

2.1.1.Структура системы

2.1.2.Модельная база данных

2.1.3.Логический процессор

2.1.4. Модификатор.

2.2.Представление семиотического языка

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

2.4.Вывод ы.

ГЛАВА 3.СИСТЕМА ПЛАНИРОВАНИЯ ДЕЙСТВИЙ СПДОТ.

3.1.Общая стратегия смешанного подхода.

3.2.Уровень стратегического планирования.

3.2.1.Представление знаний. Формулировка задачи планирования действий

3.2.2.Структура модели мира и предметной области

3.2.3.Стратегия уровня стратегического планирования

3.3.Уровень оперативного планирования

3.3.1.Стратегия уровня оперативного планирования

3.3.2.Процедуры обобщения и расширения

3.4.Уровень выполнения плана

3.4.1.Представление плана.

3.4.2.Стратегия уровня выполнения плана

3.5. Выводы.

ГЛАВА 4.РЕШЕНИЕ ЗАДАЧ С ПОМОЩЬЮ СЦЦОТ.

4.1.Решение задач радиационной химии

4.2.Автоматический синтез лисповских программ

4.3. Выводы.

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

В нашей стране таким задачам придается важное, государственное значение. Об этом свидетельствует постановление ЦК КПСС и Совета Министров СССР "О мерах по ускорению научно-технического прогресса в народном хозяйстве", принятое в августе 1983 года, в котором "ЦК КПСС и Совет Министров СССР определили в качестве одного из главных направлений работы по ускорению научно-технического прогресса широкую автоматизацию технологических процессов на основе применения автоматизированных станков, машин и механизмов, унифицированных модулей оборудования, робо-тотехнических комплексов и вычислительной техники" /34/.

Основные направления развития вычислительной техники в автоматизации современных систем управления отразились в "Основных направлениях экономического и социального развития СССР на I98I-I95 годы и на период до 1990 года": "На основе использования достижений науки и техники: развивать производство и обеспечить широкое применение автоматических манипуляторов (промышленных роботов), встроенных систем автоматического управления с использованием микропроцессоров и микро-ЭВМ, создавать автоматизированные цехи и заводы."

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

Задачи планирования действий (ЗГЩ) определяются заданием:

- модели исходной ситуации, описывающей исходную ситуацию среды;

- модели целевой ситуации, описывающей желаемую ситуацию среды;

- операторов-моделей возможных действий для воздействия на эту среду;

Решение ЗЦД состоит в поиске последовательностей операторов, преобразующих модель исходной ситуации в модель целевой ситуации, и моделировании выполнения этих последовательностей на ЭВМ.

Под ситуацией понимается конкретное статическое состояние среды. Описание ситуации задается перечислением свойств, состояний й отношений между объектами среды.

Среду будем называть сложной, если она характеризуется:

- громоздкостью: среда включает много объектов, связи с которыми не полностью определены;

- разнородностью: для среды характерно многообразие объектов и отношений;

- динамичностью: в среде существуют факты и действия, явно зависящие от времена.

Система, решающая ЗЦД, называется Системой планирования действий (СПД). Таким образом, СЦЦ на основе знаний, представляемых моделями исходных и целевых ситуаций и возможных операторов:

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

- моделирует выполнение запланированных действий.

К ЗЦЦ сводится большой класс задач робототехники, автоматизации научных исследований и проектирования, автоматический синтез программ. Большое народнохозяйственное значение имеет использование СЦЦ для решения задач планирования действий роботов, задач радиационной химии, в частности для прогнозирования восстановления-окисления ионов различных металлов. Перспективно применение СЦЦ для принятия многошаговых решений в АСУ и для решения задач, связанных с работами ". в области создания гибких автоматизированных производств и систем автоматизированного проектирования и их использования в народном хозяйстве" /34/.

Цель работы состоит в разработке метода построения и реализации конкретной СЦЦ, названной СЦЦОТ (система планирования действий на основе ТБШЮС), которая должна быть универсальной (не должна зависеть от конкретных предметных областей), мобильной, легко представляемой на разных ЭВМ и решающей реальные ЗЦЦ в сложных средах. СЦЦОТ должна:

- использовать для представления знаний систему, основанную на современных методах организации баз данных;

- обеспечивать процесс поиска решений задач;

- организовывать процедуры обобщения конкретных результатов решения задач для создания классов задач;

- выполнить запланированные действия.

Научная новизна проведенной работы состоит в том, что построена система планирования действий СЦЦОТ на базе подходов логических систем и логико-лингвистических моделей, которая решает задачи не только с помощью этих подходов, но и смешанным подходом; ее можно представить в следующем виде: модель предметной области должна иметь вид, типичный для логико-лингвистических моделей, Если конкретная задача полностью решается по данной модели, т.е. является конкретизацией одного из классов решаемых задач, задачу полностью решает метод логико-лингвистических моделей. В случае возникновения непредвиденных ситуаций должна срабатывать стратегия поиска решений логических систем, на которую возлагается задача планирования достижения целевой ситуации.

СЦЦОТ осуществляет перепланирование в случае невозможности выполнения запланированных действий при возникновении новых событий в среде в процессе моделирования выполнения планов.

СЦЦОТ способна функционировать также вместе с лингвистичес-ко-фреймной подсистемой диалоговой информационно-логической системы ТБИДОС /35/, обеспечивающей возможность обращения к СПДОТ на естественном языке. Это дает возможность использовать диалоговый режим в описании моделей исходной и целевой ситуации и операторов, а также для уточнения некоторых решений, принимаемых составными частями СЦЦОТ.

В СЦЦОТ применяется новый метод синтеза самоуправляющихся объектов МВД, называемый самосинтезом, который позволяет динамически использовать управляющие объекты и результаты обобщения.

Практическая ценность полученных результатов заключается в создании СЦЦОТ, которая может быть применена для решения реальных ЗПД в сложных средах.

Система планирования действий СЦЦОТ:

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

- осуществляет решение задач с помощью конкретизации плана в том случав, если существует класс, к которому относится поставленная задача, или дедуктивной стратегий, если такого класса не существует;

- обобщает решенные задачи и соответствующие планы и пополняет ими модель предметной области;

- реализует процесс перепланирования в случае невозможности выполнения планов.

На основе разработанной методики реализована СПДОТ для машин серии ЕС в операционной системе ОС. Все программы написаны на языке Лисп /20,22,43/, а некоторые методы представлены с помощью объектов Модельной базы данных системы ТЕШЮС.

СЦЦОТ была использована для решения задач радиационной химии, в частности задач прогнозирования окисления-восстановления ионов различных металлов. Она внедрена в Институте неорганической химии и электрохимии АН ГССР.

Основные результаты работы докладывались на семинарах отдела программирования в Институте вычислительной математики АН ГССР, на втором, четвертом и шестом грузинских республиканских семинарах "Интерактивные системы" (Боржоми, 1980; Сухуми, 1982; Батуми, 1984), на Всесоюзных конференциях "Диалог Человек-ЭВМ" (Ленинград, 1982; п.Протвино Московской обл., 1983), на конференции "Семантические вопросы искусственного интеллекта" (Киев, 1982), на семинаре "Диалоговые и обучающие системы" (Ужгород, 1984), а также опубликованы в работах /1-5, 36/.

СОДЕРЖАНИЙ РАБОТЫ. В главе I дается критический обзор имеющейся литературы по СПД, выявляются общие принципы планирования, на основе представления знаний и поиска решения выделяются четыре подхода к построению СЦЦ (логический, теоретико-графовый, процедурный и логико-лингвистические модели), приводятся основные характеристики этих подходов, обосновывается подход, предпринятый в настоящей работе и формулируются требования, которым должна удовлетворять СЦЦОТ, реализованная на базе предложенного подхода.

В главе 2 рассматривается система ТЕШЮС, на основе которой построена СПДОТ, описываются структура системы, объекты Модельной базы данных (МБД), логический процессор и модификатор, обосновывается возможность ее применения в качестве аппарата реализации СЦЦОТ, а также для представления операций семиотического языка, являющегося основой логико-лингвистических моделей, и дедуктивной стратегии логической системы, STtiiP?.

В главе 3 описываются смешанный подход планирования и принципы организации процессов решения на уровнях стратегического планирования, оперативного планирования и выполнения плана. Рассматриваются представления знаний в СЦЦОТ, формулировки ЗЦЦ, структура модели предметной области, дедуктивная стратегия поиска решения, процедуры обобщения, процедура расширения предметной области, представления планов в СЦЦОТ, процессы перепланирования и самосинтеза.

В главе 4 показана возможность применения СЦЦОТ для решения прикладных ЗЦЦ: задач радиационной химии и автоматического синтеза лисповских функций.

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

В приложении приведены программы процесса планирования, осуществленные в СЦЦОТ на языке программирования Лисп, для ЕС-ЭВМ в операционной системе ОС.

4.3. Выводы

1.Показана возможность применения СПД для решения задач радиационной химии, в частности радиационно-химического окисления-восстановления ионов различных металлов.

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

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

ЗАКЛЮЧЕНИЕ

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

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

3.Реализована система планирования действий СЦЦОТ на основе смешанного подхода; она способна решать задачи и автономно по принципам планирования логических систем и логико-лингвистических моделей. В качестве аппарата реализации используется диалоговая информационно-логическая система ТЕШЮС.

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

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

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

- но

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

8.С помощью СПДОТ решены прикладные задачи планирования действий: задачи прогнозирования радиаыионно-химического окисления-восстановления ионов различных металлов и задачи автоматического синтеза лисповских программ над базами данных; полученные экспериментальные данные подтверждают достоверность работы системы.

1.Арчвадзе Н.Н., Пховелишвили М.Г. Решение задач планирования действий в системе ТБИЛОС. - В кн.: Интерактивные системы. Тезисы докладов второй школы-семинара (Боржоми, февраль, 1980 г.). Книга 1. - Тбилиси: Мепниереба, 1980, с.36-41.

2. Арчвадзе Н.Н. Диалоговый планировщик действий. В кн.: Интерактивные системы. Тезисы докладов четвертой школы-семинара. (Сухуми, 10-19 мая, 1982). - Книга I. - Тбилиси: Мепниереба, 1982, с.61-63.

3. Арчвадзе Н.Н. Планирование действий. В кн.: Вычислительная математика и программирование. АН ГССР, Институт вычислительной математики им.Н.И.Мусхелишвипи. Труды ХХ1У: I. -Тбилиси: Мепниереба, 1984, с.ПО-124.

4. Ващенко Н.Д. Формирование понятий в семантической сети.-Кибернетика, 1983, № 2, с.101-108.

5. Галаган Н.И. siTPLftM язык описания задач преобразования ситуаций. Киев: Институт кибернетики, 1973, с.48.

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

7. ТО.Гладун В.П., Галаган Н.И., Ващенко Н.Д. Системы планирования действий для сложных сред. Кибернетика, 1982, № 5, с.88т95.

8. Н.Глушков В.М., Стогний А.А., Биба И.Г. и др. Системы автоматизации творческих процессов в научных исследованиях, проектировании и задачах управления роботами. Кибернетика,1981, В 6, C.II0-II6.

9. Доран Дж. Планирование и роботы. В кн.: Интегральные роботы. - М.: Мир, 1973, с.339-355.

10. Ефимов Е.И. СФИНКС система формального интеллекта комплексных стратегий. - В кн.: Вопросы кибернетики, вып.18. Теория и практика ситуационного управления. - М.: Научный Совет по комплексной проблеме "Кибернетика", 1977, с.14-21.

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

12. Дуков Л.Г. Об одном алгоритме индуктивного формирования понятий. В кн.: Вопросы кибернетики, вып.18. Теория и практика ситуационного управления. - М.: Советское радио, 1977,с.167-17I.

13. Клннг Р. Пример системы, осуществляющей выводы аналогии. В кн.: Интегральные роботы. Выпуск 2. - М.: Мир, 1975, с.473-513.- ИЗ

14. Клыков Ю.И., Горков Л.Н. Банки данных для принятия решений. -М.: Сов.радио, 1980, 208 с.

15. Кузин Е.С., Фоминых И.Б., Хахалин Г.К. Системы принятия решений в интегральных роботах. В кн.: Интегральные роботы. Выпуск 2. - М.: Мир, 1975, с.364-378.19.1^гзин Л.Т. Основы кибернетики, т.2. М.: Энергия, 1979, 584 с.

16. Лавров С.С., Силагадзе Г.С. Автоматическая обработка данных. Язык Лисп и его реализация. М.: Наука, 1978, 176 с.

17. Мансон Дж. Робот планирует, выполняет и контролирует в неопределенной среде. В кн.: Интегральные роботы. - М.: Мир, 1973, с.355-382.

18. Маурер У. Введение в программирование на языке ЛИСП. М.: Мир, 1976, 104 с.

19. Мики Д. Формирование и выполнение планов вычислительной машиной. В кн.: Интегральные роботы. Выпуск 2. - М.: Мир, 1975, с.378-406.

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

21. Нильсон Н. Искусственный интеллект. М.: Мир, 1973, с.320.

22. Ныоэлл, А., Шоу Дж., Саймон Г. Эмпирические исследования машины логик-теоретик. В кн.: Вычислительные машины и мышления. -М.: Мир, 1967, c.III-ПЗ.

23. Пильщиков В.Н. Язык Пяэнер. М.: Наука, 1983, 208 с.

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

25. Попов В.П., Верещагин А.Ф., Зенкевич С.Л. Манипуляцион-ные роботы. Динамика и алгоритмы. М.: Наука, 1978, 400 с.

26. Поспелов Д.А. Принципы ситуационного управления. Изв. АН СССР. Техническая кибернетика, 1971, № 2, с.10-18.

27. Поспелов Д.А. Семиотические модели в задачах искусственного интеллекта. В кн.: Труды 17 МОКИИ, книга I. - М.: 1975, с.158-170.

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

29. Поспелов Д.А. Фантазия или наука. На пути к искусственному интеллекту. М.: Наука, 1982, 224 с.

30. Правда, № 240(23766), 28.08.1983.

31. Зб.Пховелишвили М.Г. Построение и применение диалоговыхинформационно-логических систем. Тбилиси: Мецниереба, 1982, 64 с.

32. Пховелишвили М.Г., Арчвадзе Н.Н. Применение диалога в системе планирования действий. В кн.: Тезисы докладов всесоюзной конференции "Диалог Человек-ЭВМ", часть I. - Л., 1982, с.270-272.

33. Рафаэл Б. Думающий компютер. М.: Мир, 1979, 408 с.

34. Рубинштейн С.Я. Методика экспериментальной патопсихологии. М.: 1962, 320 с.

35. ЗЭ.Сакердоути Э. Нелинейная природа планов. В кн.: Труды 1У МОКИИ, книга 4. - М.: 1975, с.98-134.

36. Слейгл Дк. Искусственный интеллект. Подход на основе эвристического программирования. М.: Мир, 1973, 320 с.

37. Словарь по кибернетике. Под редакцией Глушкова В.М. -Киев: Главная редакция УСЭ, 1979, 624 с.

38. Турчин В.Ф. Программирование на языке Рефал. Предпринт, Институт прикладной математики АН СССР, 1971.

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

40. Файкс Р., Нильсон Н. Система ХТЫР? новый подход к применению методов доказательства теорем при решении задач. -В кн.: Интегральные роботы. - М.: Мир, 1973, с.382-404.

41. Файкс Р. Механизм поиска вывода для моделей, описывающих состояние. В кн.: Труды IУ МОКИИ, книга 3. - М.: 1975, с.206-227.

42. Файкс Р., Харт П., Нильсон Н. Новые направления в автоматическом решении задач роботом. В кн.: Интегральные роботы Выпуск 2. - М.: Мир, 1975, с.406-440.

43. Хант Э. Искусственный интеллект. -М.: Мир, 1978, 558с.

44. Хант Э., Марин Дж., Стоун Ф. Моделирование процесса формирования понятий на вычислительной машине. М.: Мир, 1970, 301 с.

45. Хейес Ф. Представление планов робота. В кн.: Труды 1У МОКИИ, книга 9. - М.: 1975, с.13-56.

46. Щепин B.C. Языки программирования для систем управления интегральными роботами и задач искусственного интеллекта. -В кн.: Интегральные роботы. Выпуск 2. М.: Мир, 1975, с.513--526.

47. Anderson R, Completeness results for E-resolution.-Proc.of trie AJ4PS, SJCC* 1970, p.653-656.

48. Becker J.D. The Modelling of Simple Analogic and Inductive processes in a Semantic Memory System.-Proc, Intern. Joint Conf. on Art if. Inlell., ACM, flew York, 1969, P. 655-668.

49. Davies D.I.M. Popler: a POP-2 planner. -Memo. MIP-R-89, Department of Machine Intelligence and perception, University of Edinburgh, 1971, P.65-78.

50. Derksen J., Rulifson J.F., Walding R.J. Ihe QA4 Language Applied to Robot Planning. -Pall Iont Сотр., Proe., 1972, p.1181-1192.

51. Doran J.E., Michie D„ Experiments with the Graph 'traverser Program. -Proc. Roy. Soc., A294, 1966, p .235-259.

52. Doran J.E. New Developments of the G-raps Traverser. -Machine Intelligence, vol.2, Edinburgh, 1968, p.119-135.

53. Ernst (J. Sufficient condition for the success of GPS. I.AGM, 16, n4, 1969, p.517-533.

54. Hewitt 0» Planner: A Language for Proving Theorems in Robots. -Intern. Joint Gonf. Artificial Intelligence, wasftington, D.G., 1969, p.295-301.

55. Kowalski R. And-or Graphs, Theorem-Proving Gfraps and BiDirectional search. -Machine Intelligence 7, American Publishing Co., New ¥ork* 1972, p.167-194.

56. Luckham D. Refinement Theorems in ftesolutional Hheory.symposium on Automatic Demonstration. Lecture lotes on Mathematics no. 125, Springer-verlag, Berlin and New York, 1970, p.67-94.

57. Marsh D. Memo functions, Graps Traverser, and a Simple Control Situation. -Machine intelligence 5, Americal Elsevier publishing Co., New xork, 1970, p.281-300.

58. Micftie D., Ross H. Experiment with the Adaptive araps Traverser. machine Intelligence 5, American Elsevier Publishing Go., i^ew lorlc, 1970, p. Э01-ЗШ.

59. Baphael ij. i'he jj'rame pro Diem in problem Solving Systems. Artificial Intelligence and Heuristic Programming.!, Edinburgh University press, 1971, P.159-169.

60. RuLif son j., Derksen J., W aiding R.J. QA4: a Procedural Canculus for Intuative Reasoning. AI Center, technical Note 73, SRI Project 8721, 1972, p.59-69.