Содержание к диссертации
ВВЕДЕНИЕ 4
ГЛАВА I.ОБЗОР РАБОТ, ПОСВШЦЕННЫХ СИСТЕМАМ ПЛАНИРОВАНИЯ
ДЕЙСТВИЙ Ю
I.I.Логический подход 10
1.2.Теоретико-графовый подход 17
1.3.Процедурный подход 19
1.4.Логико-лингвистические модели 20
1.5.Выводы 23
ГЛАВА 2.ИСП0ЛБ30ВАНИЕ СИСТШЫ ТЕЙЛОС ДНЯ РЕШЕНИЯ ЗАДАЧ
ПЛАНИРОВАНИЯ ДЙЙСТВИЙ 25
2.1.Система ТБИЛОС 26
2.I.I.Структура системы 26
2.1.2.Модельная база данных . 27
2.1.3.Логический процессор 36
2.1.4. Модификатор 39
2.2.Представление семиотического языка 41
2.3.Представление стратегии логического подхода . . 48
2.4.Выводы 54
ГЛАВА 3.СИСТЕМА ПЛАНИРОВАНИЯ ДЕЙСТВИЙ СПДОТ 58
3.1.Общая стратегия смешанного подхода 58
3.2.Уровень стратегического планирования 61
3.2.1.Представление знаний. Формулировка задачи
планирования действий 61
3.2.2.Структура модели мира и предметной области . 66
3.2.3.Стратегия уровня стратегического планирования 74
3.3.Уровень оперативного планирования 79
3.3.1.Стратегия уровня оперативного планирования . 79
3.3.2.Процедуры обобщения и расширения 85
3.4.Уровень выполнения плана 93
3.4.1.Представление плана 93
3.4.2.Стратегия уровня выполнения плана 96
З.б.Выводы 100
ГЛАВА 4.РЕШЕНИЕ ЗАДАЧ С ПОМОЩЬЮ СЦЦОТ 102
4.1.Решение задач радиационной химии 102
4.2.Автоматический синтез лисповских программ . . 106
4.3.Выводы 108
ЗАКЛЮЧЕНИЕ 109
ЛИТЕРАТУРА III
ПРИЛОЖЕНИЯ 118
Введение к работе
Одним из основных направлений прогресса является автоматизация с помощью средств вычислительной техники процессов решения задач в сфере научно-технической деятельности человека:планирование поведения в сложных средах, проектирование и конструирование, синтез программ, доказательство теорем, игры и другие задачи, которые принято считать интеллектуальными.
В нашей стране таким задачам придается важное, государственное значение. Об этом свидетельствует постановление ЦК КПСС и Совета Министров СССР "О мерах по ускорению научно-технического прогресса в народном хозяйстве", принятое в августе 1983 года, в котором "ЦК КПСС и Совет Министров СССР определили в качестве одного из главных направлений работы по ускорению научно-технического прогресса широкую автоматизацию технологических процессов на основе применения автоматизированных станков, машин и механизмов, унифицированных модулей оборудования, робо-тотехнйческих комплексов и вычислительной техники" /34/.
Основные направления развития вычислительной техники в автоматизации современных систем управления отразились в "Основных направлениях экономического и социального развития СССР на I98I-I95 годы и на период до 1990 года": "На основе использования достижений науки и техники: развивать производство и обеспечить широкое применение автоматических манипуляторов (промышленных роботов), встроенных систем автоматического управления с использованием микропроцессоров и микро-ЭВМ, создавать автоматизированные цехи и заводы..."
Из класса интеллектуальных задач можно выделить множество задач, называющихся задачами планирования действий. Решение их
весьма актуально.
Задачи планирования действий (ЗЦЦ) определяются заданием:
модели исходной ситуации, описывающей исходную ситуацию среды;
модели целевой ситуации, описывающей желаемую ситуацию среды;
операторов-моделей возможных действий для воздействия на эту среду;
Решение ЗЦЦ состоит в поиске последовательностей операторов, преобразующих модель исходной ситуации в модель целевой ситуации, и моделировании выполнения этих последовательностей на ЭВМ.
Под ситуацией понимается конкретное статическое состояние среды. Описание ситуации задается перечислением свойств, состояний и отношений между объектами среды.
Среду будем называть сложной, если она характеризуется:
громоздкостью: среда включает много объектов, связи с которыми не полностью определены;
разнородностью: для среды характерно многообразие объектов и отношений;
динамичностью: в среде существуют факты и действия, явно зависящие от времени.
Система, решающая ЗЦЦ, называется Системой планирования действий (СЦЦ). Таким образом, СЦЦ на основе знаний, представляемых моделями исходных и целевых ситуаций и возможных операторов:
- осуществляет механизм, обеспечивающий планирование после
довательностей операторов, преобразующих модель исходной ситу
ации в модель целевой ситуации;
- моделирует выполнение запланированных действий.
К ЗЦЦ сводится большой класс задач робототехники, автоматизации научных исследований и проектирования, автоматический синтез программ. Большое народнохозяйственное значение имеет использование СЦЦ для решения задач планирования действий роботов, задач радиационной химии, в частности для прогнозирования восстановления-окисления ионов различных металлов. Перспективно применение СЦЦ для принятия многошаговых решений в АСУ и для решения задач, связанных с работами "... в области создания гибких автоматизированных производств и систем автоматизированного проектирования и их использования в народном хозяйстве" /34/.
Цель работы состоит в разработке метода построения и реализации конкретной СЦЦ, названной СЦЦОТ (система планирования действий на основе ТБШЮС), которая должна быть универсальной (не должна зависеть от конкретных предметных областей), мобильной, легко представляемой на разных ЭВМ и решающей реальные ЗЦЦ в сложных средах. СЦЦОТ должна:
использовать для представления знаний систему, основанную на современных методах организации баз данных;
обеспечивать процесс поиска решений задач;
организовывать процедуры обобщения конкретных результатов решения задач для создания классов задач;
выполнить запланированные действия.
Научная новизна проведенной работы состоит в том, что построена система планирования действий СЦЦОТ на базе подходов логических систем и логико-лингвистических моделей, которая решает задачи не только с помощью этих подходов, но и смешанным подходом; ее можно представить в следующем виде: модель пред-
метной области должна иметь вид, типичный для логико-лингвистических моделей, Если конкретная задача полностью решается по данной модели, т.е. является конкретизацией одного из классов решаемых задач, задачу полностью решает метод логико-лингвистических моделей. В случае возникновения непредвиденных ситуаций должна срабатывать стратегия поиска решений логических систем, на которую возлагается задача планирования достижения целевой ситуации.
СПДОТ осуществляет перепланирование в случае невозможности выполнения запланированных действий при возникновении новых событий в среде в процессе моделирования выполнения планов.
СПДОТ способна функционировать также вместе с лингвистичес-ко-фреймной подсистемой диалоговой информационно-логической системы ТЕШЮС /35/, обеспечивающей возможность обращения к СІЩОТ на естественном языке. Это дает возможность использовать диалоговый режим в описании моделей исходной и целевой ситуации и операторов, а также для уточнения некоторых решений, принимаемых составными частями СПДОТ.
В СЦЦОТ применяется новый метод синтеза самоуправляющихся объектов МВД, называемый самосштезом, который позволяет динамически использовать управляющие объекты и результаты обобщения.
Практическая ценность полученных результатов заключается в создании СЦЦОТ, которая может быть применена для решения реальных ЗБД в сложных средах.
Система планирования действий СПДОТ:
формирует модель предметной области в виде классов задач с соответствующими решениями;
осуществляет решение задач с помощью конкретизации плана в том случав, если существует класс, к которому относится пос-
тавленная задача, или дедуктивной стратегии, если такого класса не существует;
обобщает решенные задачи и соответствующие планы и пополняет ими модель предметной области;
реализует процесс перепланирования в случав невозможности выполнения планов.
На основе разработанной методики реализована СПДОТ для машин серии ЕС в операционной системе ОС. Все программы написаны на языке Лисп /20,22,43/, а некоторые методы представлены с помощью объектов Модельной базы данных системы ТЕИЛОС.
СДЦОТ была использована для решения задач радиационной химии, в частности задач прогнозирования окисления-восстановления ионов различных металлов. Она внедрена в Институте неорганической химии и электрохимии АН ГССР.
Основные результаты работы докладывались на семинарах отдела программирования в Институте вычислительной математики АН ГССР, на втором, четвертом и шестом грузинских республиканских семинарах "Интерактивные системы" (Боржоми, 1980; Сухуми, 1982; Батуми, 1984), на Всесоюзных конференциях "Диалог Человек-ЭВМ" (Ленинград, 1982; п.Протвино Московской обл., 1983), на конференции "Семантические вопросы искусственного интеллекта" (Киев, 1982), на семинаре "Диалоговые и обучающие системы" (Ужгород, 1984), а также опубликованы в работах /1-5, 36/.
СОДЕРЖАНИЙ РАБОТЫ. В главе I дается критический обзор имеющейся литературы по СБД, выявляются общие принципы планирования, на основе представления знаний и поиска решения выделяются четыре подхода к построению СЦЦ (логический, теоретико-графовый, процедурный и логико-лингвистические модели), приводятся основные характеристики этих подходов, обосновывается
подход, предпринятый в настоящей работе и формулируются требования, которым должна удовлетворять СІЩ0Т, реализованная на базе предложенного подхода.
В главе 2 рассматривается система ТЕШЮС, на основе которой построена СПДОТ, описываются структура системы, объекты Модельной базы данных (МВД), логический процессор и модификатор, обосновывается возможность ее применения в качестве аппарата реализации СДЦОТ, а также для представления операций семиотического языка, являющегося основой логико-лингвистических моделей, и дедуктивной стратегии логической системы, ЛТЩ/э?.
В главе 3 описываются смешанный подход планирования и принципы организации процессов решения на уровнях стратегического планирования, оперативного планирования и выполнения плана. Рассматриваются представления знаний в СЦЦОТ, формулировки ЗЦЦ, структура модели предметной области, дедуктивная стратегия поиска решения, процедуры обобщения, процедура расширения предметной области, представления планов в СЦЦОТ, пропессы перепланирования и самосинтеза.
В главе 4 показана возможность применения СЦЦОТ для решения прикладных ЗЦЦ: задач радиационной химии и автоматического синтеза лисповских функций.
В заключении сформулированы выводы, полученные в результате выполнения работы.
В приложении приведены программы процесса планирования, осуществленные в СЦЦОТ на языке программирования Лисп, для ЕС-ЭВМ в операционной системе ОС.
- ю -