МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Государственное образовательное учреждение высшего профессионального образования "Ижевский государственный технический университет"
УТВЕРЖДАЮ Ректор ______________ И.В. Абрамов "_____"________________ 200__г.
KG – учебная система для проектирования информационных технологий и экспертных систем Методические указания по выполнению дипломного проекта, лабораторных и курсовых работ по дисциплинам "Информационные технологии", "Системы искусственного интеллекта", "Проектирование АСОИУ", "Разработка САПР" для студентов специальностей 220200 Автоматизированные системы обработки информации и управления, 220300 Системы автоматизированного проектирования, 552800 Информатика и вычислительная техника Форма обучения очная и заочная
Ижевск 2004
Кафедра "Автоматизированные системы обработки информации и управления".
Составители: Кучуганов В.Н., д.т.н., профессор, Габдрахманов И.Н. , ст. преподаватель, Шутов Е.А., ст. преподаватель.
Методические указания составлены на основании государственного образовательного стандарта высшего профессионального образования и утверждены на заседании кафедры Протокол от "____" ________________ 200__ г. № ______.
Заведующий кафедрой
____________________ В.Н. Кучуганов "____" ________________ 200__ г.
СОГЛАСОВАНО: Председатель учебно-методической комиссии по специальности ____________________ В.Н. Кучуганов "____" ________________ 200__ г.
Методические указания предназначены для выполнения дипломного проекта, лабораторных и курсовых работ по дисциплинам "Информационные технологии", "Системы искусственного интеллекта", "Проектирование АСОИУ", "Разработка САПР" студентами специальностей 220300 Системы автоматизированного проектирования, 220200 Автоматизированные системы обработки информации и управления, направления 552800 Информатика и вычислительная техника.
Начальник учебно-инженерного отдела ____________________ А.М. Ефимова "____" ________________ 200__ г. 2
СОДЕРЖАНИЕ ВВЕДЕНИЕ.............................................................................................................. 4 1. МОДЕЛЬ ЗНАНИЙ СИСТЕМЫ KG................................................................. 6 2. ПРОЦЕССЫ И СЦЕНАРИИ .............................................................................. 8 2.1. Представление процессов, сценариев и работ в KG.................................. 8 2.2. Логический вывод и решатель задач......................................................... 10 2.3. Представление графиков и траекторий движения................................... 12 2.4. Алгоритм заимствования движений.......................................................... 12 2.5. Процессы и их отношения с невербальной информацией...................... 13 2.6. KG и семантика естественных языков ...................................................... 14 2.7. Рабочая память как модель информационной сети в процессе решения задачи................................................................................................................... 15 2.8. Динамика проектов ..................................................................................... 16 2.9. Вычислительные модели ............................................................................ 17 3. ОПИСАНИЕ КОНЦЕПТА ............................................................................... 19 3.1. Атрибуты общих свойств ........................................................................... 19 3.2. Атрибуты состава сборки ........................................................................... 20 3.3. Атрибуты схемы функционирования........................................................ 21 4. ПРОЕКТИРОВАНИЕ БАЗ ЗНАНИЙ.............................................................. 22 4.1. Работа с деревьями знаний......................................................................... 23 4.2. Работа с концептами ................................................................................... 23 4.3. Работа с атрибутами.................................................................................... 24 4.4. Работа с экземплярами................................................................................ 24 5. Язык программирования системы KG ............................................................ 25 ЛИТЕРАТУРА ....................................................................................................... 33
3
ВВЕДЕНИЕ Система управления базами знаний (СУБЗ) KG (Knowledge's Guidebook – путеводитель по знаниям) предназначена для создания и управления базами знаний и данных, ориентированных на экспертные системы и информационные технологии сквозной поддержки жизненного цикла изделий (CALS – технологии). Область применения – образовательный процесс, а также средние и малые производственные и коммерческие фирмы. Характерные черты: 1. Коллективная и персональная версии. 2. Иерархическая организация знаний. 3. Специализированные средства для обработки конструкторских данных и знаний. 4. Визуальное конструирование процессов. 5. Логический синтез составных процессов из простых. 6. Специализированный инструментарий для работы с деревьями составов (которые, в отличие от деревьев классов, не наследуют свойств, но заимствуют геометрические модели образцов). 7. Средства реорганизации и адаптации баз знаний к специфике задач. 8. Наличие вербальной и невербальной информации в базах данных. 9. Высокая динамичность по составу компонентов, атрибутов, отношений. 10. Расширяемая библиотека функций и команд для разработки приложений. Признаки СУБД: − −
вся информация в таблицах; операции реляционной алгебры.
Признаки СУБЗ: − смысловое описание информации; − структурированность; − связанность; − активность; − логический вывод (поиск) решения. Признаки объектно ориентированного программирования: − наследование; − связи «многие-ко-многим»; − полиморфизм.
4
Собственные признаки и ограничения: − наследование свойств; − заимствование и параметризация компонент состава из различных деревьев; − двойственность процессов: редко используемые процессы хранятся как данные (образцы), часто используемые – как концепты, которые могут активизироваться; − синтез отношений по шаблонам (вычислительным моделям); − семантические сети образуются ребрами наследования, заимствования, отношений; − адаптация – синтез задачно-ориентированных БЗ и БД; − визуальное конструирование предметов; − открытая архитектура.
5
1. МОДЕЛЬ ЗНАНИЙ СИСТЕМЫ KG Знаниями будем считать информацию проблемно систематизированную с помощью классификационных деревьев, таблиц, графиков, функций, закономерностей, правил, планов действий, примеров, т.е. знания - это концентрированная информация. Иерархия элементов БЗ: Дерево
Концепт
Экземпляр
Рис. 1.1 Дерево задает иерархию концептов. Концепт базы знаний (понятие) определяет подмножество экземпляров, у которых значения параметров удовлетворяют данному понятию, т.е. экземпляры являются листьями деревьев. Виды концептов Концепт
Предмет или часть
Абстракция (внешние данные)
Описание ГМ
Процесс или подпроцесс
Программа исчисления
Параметризация (преобразование)
Отношение
Время
Место
Свойство
Степень родства
Рис. 1.2 <Концепт> ::= <Имя>, <Комментарий>, <Список атрибутов> [,<Список компонент> [, <Список отношений между компонентами>]] [,<Вычислительная модель> | <Геометрическая модель>] <Комментарий> ::= <Текст на естественном языке> <Атрибут> ::= <Концепт-свойство>, <Тип>, <Диапазон изменения значений>, <Ожидаемое значение> 6
Свойство может стать атрибутом некоторого концепта, например, "автомобиль", "перевозка грузов". <Компонент> ::= <Часть предмета>| <Подпроцесс> <Геометрическая модель> ::= <Растровая> | <Векторная> | <Текстовая> <Вычислительная модель> ::= <Список операторов> | <Предикат> | <Функция> | <Таблица> | <Внешняя программа> Процессы параметризации являются мощным инструментом заимствования компонент при конструировании новых объектов. Параметризация геометрических моделей - это получение нового предмета путем изменения параметров прототипа. Параметризация вычислительных моделей - это настройка процесса на новый класс данных. Таким образом, описанная модель знаний обладает признаками систем управления базами данных (СУБД), систем управления знаниями (СУБЗ) и объектно ориентированного подхода.
7
2. ПРОЦЕССЫ И СЦЕНАРИИ 2.1. Представление процессов, сценариев и работ в KG Процесс хранится в KG как экземпляр (строка таблицы) некоторого концепта "Процессы": <Процесс>:: = <Имя><Свойства>[<Длительность>] [<Вычислительная модель>] <Список имен входных структур данных> <Список имен выходных структур данных> [<Состав подпроцессов> <Список отношений подпроцессов>]. Списки имен входных и выходных структур данных заданы с помощью текстовых атрибутов. Атрибуты "вычислительная модель", "структуры входных данных", "структуры выходных данных" представляются в виде текста с целью сокращения количества классов процессов и удобства логического вывода. Структуры данных, утвержденные коллективом разработчиков, описываются в KG стандартным образом. Процесс задает некоторую последовательность действий, выполняемых в общем случае, одним процессором. Отношения (связи) между подпроцессами описывают порядок передачи управления. Процессы, которые могут изменять (редактировать) данные, содержат дополнительную выходную структуру, куда в виде текста или файла записывается цепочка изменений типа "UnDo-ReDo". Все другие процессы не могут изменять значения входных данных, но их выходные структуры могут содержать ссылки на входные. Закон – это вычислительная модель высокой степени общности в смысле диапазонов входных данных. Например: I = U / R; "Хлеб падает маслом вниз". Сценарий – это план выполнения процессов, который конкретизируется в ходе работы в зависимости от оперативной обстановки и получаемых результатов. Сценарий может быть ориентирован на участие в нем человека – пользователя, игрока. В общем случае, сценарий описывает схему взаимодействия коллектива акторов (процессов): <Сценарий>:: = <Имя><Свойства><Длительность> [<Место действия>] <Состав> <Список отношений элементов состава>. 8
Состав сценария представляет собой список процессов верхнего уровня типа Process (Sq.), Repeat, Case, If (см. рис. 2.1). Отношения между процессами - компонентами, составляющими сценарий, как правило, бывают двух типов: - отношения "кто за кем" аналогичны линиям передачи управления в блок-схеме программы; - отношения "кто когда" отображают временную диаграмму с помощью множества бинарных отношений вида {
}, где: Rij – смещение по времени между началом j-того процесса относительно конца i-того процесса, если pi не указан, то относительно начала данного сценария. Очевидно, i-тый процесс может быть выполнен только, если входные структуры данных для него заполнены. Внешний вид плана ├─── Process1 │ ├── │ ├── │ └── ├─── Repeat │ ├── │ ├── │ └── ├─── Case │ ├── │ ├── │ └── ├─── IF (x <= a) │ ├── ├── │ │ └── Рис. 2.1 Сценарии являются экземплярами некоторого концепта "Сценарии". Ситуация – это состояние (образец) параметров множества предметов и процессов, задействованных в сценарии. Простая ситуация описывает один предмет или один процесс. Анализ (распознавание) ситуации обычно осуществляется в момент выбора очередного действия.
9
Решатель задач – это блок системы KG, осуществляющий сборку и выполнение заданного сценария, а также выгрузку ненужных процессов и структур в соответствии с временной диаграммой сценария. Решатель задач рассматривает сценарий как совокупность связанных между собой временных диаграмм и компонент – структур входных, выходных данных и программ (процессов). Решатель задач получает на вход сценарий и, в соответствии с ним, извлекает необходимые структуры данных. Если сценарий прописан не конкретно, то подключается модуль логического вывода. Система управления знаниями может иметь несколько решателей задач, специализированных и настроенных на различные классы задач. Пользователь прикладной задачи, выбрав нужный сценарий из множества доступных, получает в левом окне экрана план в виде перечня подзадач, которые он должен в ходе работы выполнить в интерактивном режиме (рис. 2.1). При этом ему предоставляется доступ к просмотру и редактированию соответствующих структур данных, в то время, как все другие структуры для него закрыты. Так в системе KG осуществляется адаптация к специфике задачи. Протокол (работа, проект) отображает конкретную реализацию некоторого исполненного сценария и отличается от него тем, что отдельные процессы в нем могут повторяться многократно. При записи в KG протокола выполненной работы все созданные или измененные структуры данных записываются как экземпляры соответствующих концептов-предметов и перечисляются в данном протоколе в графе "Состав (сцены)". В дальнейшем, при записи протокола в KG можно будет сохранять только отличия от предыдущего аналога. 2.2. Логический вывод и решатель задач Событие (сюжет) – это исполненный сценарий или протокол. Например: "Камень упал на крышу". События бывают состоявшиеся, текущие и ожидаемые. Из событий мы можем извлечь некоторые факты. Факты – это значения атрибутов некоторых объектов. Множество фактов можно разбить на 2 группы: - факты, дополняющие атрибуты и значения некоторого объекта (экземпляра); - факты, вычисляемые относительно других объектов, т.е. связывающие объект с другими объектами.
10
Например: Шкаф выше Стол; Невеста.Возраст >= 18; Маша любит Петя; Маша сестра Петя; Пример рабочей таблицы фактов приведен в таблице 2.1. Таблица 2.1 Имя 1 2
Концепт операнда Человек.Жених Человек.Жених
Атрибут операнда Возраст Возраст
Значение (ВМ) 18 старше Невеста
Таблица правил (вычислительных моделей). Посылки можно представить как логические функции, вычисляющие истинность выражений, в которых переменными (операндами) являются имена атрибутов (фактов). Пример таблицы правил приведен в таблице 2.2. Таблица 2.2 Имя 1 2
Сущность Достиг ли жених брачного возраста Достиг ли жених брачного возраста по уважительной причине
Источник Посылка (ВМ) Статья 13, Жених.Возраст >= 18 п.2 СК
Следствие (новый факт-атрибут) Жених.ДостигБрачногоВозраста = true
Статья п.2 СК
Жених.ДостигБрачногоВозраста true
13, (Жених.Возраст >= 16) and (УважитПричинаДо18)
Алгоритм простейшего логического вывода. Под логическим выводом условимся понимать сборку процессов (компонент, программ, функций, продукций, предикатов) в такую последовательность, которая приводит к нужному результату, т.е. к решению поставленной задачи. Дано: - список процессов; - список известных фактов, пополняемый в ходе рассуждений. Требуется найти или вычислить неизвестные параметры ситуации. Алгоритм логического вывода – это Case-функция, которая осуществляет: 1. Перебор процессов. 2. Анализ ситуации и проверка выполнимости i-того процесса, т.е. наличие всех входных данных (фактов) для него. 3. Выбор из нескольких возможных процессов: а) выполнить все или б) выбрать один j-тый процесс, воспользовавшись некоторой стратегией. 4. Пополнение списка фактов результатами j-того процесса. 11
=
5. Закончить вывод, если нет новых фактов. Следовательно, для логического вывода необходимо: 1. Выделить метаправила – стратегии и рекомендации. Процессы могут обладать атрибутом приоритетности, значение которого определяется экспертом или автоматически, в соответствии с выбранной стратегией. 2. Выделить правила типа "требования" и, соответственно, факты, принимаемые априорно, например: "Лекции академика Петрова должны проходить по понедельникам с 8-30 утра". Замечания. 1. Результаты логического вывода зависят от стратегии. 2. Задачи типа "расписание" порождают правила, которые удобно представить в виде гиперграфа – множества ситуаций, в которых те или иные правила могут выполняться. 3. Процессы могут быть одноразовые и многоразовые в рамках одного сценария. 2.3. Представление графиков и траекторий движения В концепте "Траектории движения" описывается структура данных и некоторые вспомогательные атрибуты, например, имя движущегося объекта или класса объектов. Собственно траектория может быть представлена подмножеством экземпляров, по одному на каждый отрезок прямой, дуги, сплайна или в виде файла геометрической модели. В этом случае в KG потребуется один экземпляр на одну траекторию, а для ручного ввода и корректировки траектории будет использоваться функция "распаковки", которая переведет файл в список экземпляров. Аналогичным образом задаются и графики. 2.4. Алгоритм заимствования движений Параметры процесса движения должны быть приведены к параметрам кинематической схемы (КС). Для каждого движения на КС задается ведущее звено, например, при ходьбе – пятка, стопа, носок. Функции движения (графики) всех остальных звеньев должны быть параметрически связаны с ведущим звеном и (или) предыдущим по цепочке передачи движения с помощью специализированных функций передачи влияния (например, хромой персонаж). Отношения, определяющие ограничения и характерные особенности движения, также должны связывать между собой параметры КС, движения, окружающие предметы, время. Параметры масштабирования движения вычисляются только по параметрам двух КС.
12
Задача учета отношений ограничения решается аналогично задаче построения переходов при объединении нескольких движений и (или) путем расчета необходимых смещений в пределах имеющейся степени свободы. Нужно разработать структуры данных, совместимые с KG, для тестовых примеров (ходьба) со степенью подробности, достаточной для программирования. Описать математически множество необходимых операций. Чем они мельче, тем легче программировать. Тогда, алгоритм заимствования (масштабирование – смещение − параметризация) сводится к алгоритму логического вывода, т.е. выбору необходимых и допустимых операций, в том числе, дополнительных операций, вызванных необходимостью подгонки под характерные особенности переносимого движения. И так для каждой цепочки, каждого звена и КС в целом, в каждый момент времени, в соответствии с выбранным шагом аппроксимации. 2.5. Процессы и их отношения с невербальной информацией 1. Невербальная информация (растр, 3D ГМ, чертеж, текст) в БЗ всегда имеет сопроводительную информацию, т.е. концепт такой базы, состоящей из потоков данных, имеет общие описательные атрибуты, создаваемые менеджером знаний и заполняемые пользователем. В их числе: время, принадлежность, а также тип потока и инструмент обработки (например, RBGD). 2. Все необходимые инструменты для обработки потоков невербальной информации находятся в расширяемой библиотеке команд СУБЗ – это есть простейшие невербальные процессы СУБЗ. 3. Вербализованные (описанные на понятийном уровне) процессы СУБЗ KG представляются строго в соответствии с парадигмой системы KG виде: – атрибуты цели, функционального описания и пользовательской принадлежности; – состав подпроцессов (иерархическая схема) вплоть до невербальных процессов; – план (схема алгоритма) реализации; – атрибуты описания входной и выходной информации и ресурсов. 4. Состав процесса и план обработки информации могут быть заданы (в относительно простых случаях) с помощью вычислительных моделей (ВМ). Из ВМ схема извлекается автоматически и наоборот. 5. Вычислительные модели бывают следующих видов: - арифметические или логические выражения, включающие в себя невербальные функции; - список операторов и (или) команд; - список правил (предикатов); 13
6. Решатель задач активизирует и выполняет некоторый концептпроцесс на вербальном уровне. Если процесс задан списком правил, то включается механизм логического вывода. Когда встречается не вербализованная функция или команда, она выполняется как обычная подпрограмма. 2.6. KG и семантика естественных языков Одно и то же слово или его основа может быть существительным, глаголом, прилагательным. В каждом из этих состояний оно может иметь несколько семантических значений в зависимости от контекста (ситуации). Напомним, что ситуация – это состояние (образец) параметров связной совокупности предметов и процессов. Простая ситуация описывает один предмет и (или) процесс (в естественном языке – это выражение, фраза, предложение). Знания о мире ├─── Быт │ ├─── Предметы │ ├─── Процессы │ ├─── Свойства │ └─── Опыт ├─── Медицина ├─── Военное дело ├─── Авиация и космонавтика ├─── Морское дело └─── Информатика Рис. 2.4 Свойство имеет шкалу качественных знаний. То или иное значение чаще всего выражается прилагательным, имеющим различную степень сравнения или разными прилагательными. Примеры: 1) Плохой – Ужасный; 2) He's crazy about tennis – он помешан на теннисе; 3) He's slaving at his books – он рабски привязан к своим книгам. Простая ситуация может быть представлена как кортеж <Объект, [Процесс], Свойства>, где множество свойств отвечает на вопросы: где?, когда?, какой?, как? и т.п. Множество ситуаций, классифицированных по предметным областям, составляет опыт индивидуума или системы. Ситуации связаны между собой протоколом (см. п. 2.1), где они упорядочены по времени. 14
Сложная ситуация связывает отношениями множество предметов/процессов. Например, "Случайный прохожий (или сыщик?) шел за Джимом и остановился у витрины, когда тот оглянулся". Базу данных слов удобнее всего задать следующим образом: <Слово или основа> ::= <значение><Морфологические Признаки> <Состав> <Отношения>, где каждое отношение связывает текущее слово с предметом, процессом или свойством через типовую ситуацию, в т.ч. с несколькими различными понятиями в различных предметных областях. В различных предметных областях одно и тоже слово может иметь одну сущность, но разные значения (красная роза – красное лицо). Одна и та же сущность может обозначаться разными словами. Например, пароход плывет (в быту) – пароход идет (у моряков). Смысловая окраска – это ассоциация слова в конкретном месте текста одновременно с несколькими предметными областями, благодаря чему этому слову приписывается сразу несколько смысловых значений или оно придает описываемому предмету/процессу несколько свойств. Это часто происходит в стихах. Многие шутки основаны на двойном значении некоторого слова.
2.7. Рабочая память как модель информационной сети в процессе решения задачи Назовем графической нейронной памятью (NGM – Neuron Graphical Memory) специализированную сеть для хранения данных, представленных в виде графов, оптимизации графов и решения различных прикладных задач на графах. NGM представляет собой совокупность слоев данных, где каждый слой хранит некоторый граф, и все слои связаны между собой информационно и физически (ссылочно) снизу вверх как источники и результаты некоторых процессов (подзадач). Всякая подзадача – это агент, который как паук плетет свою сеть, опираясь на одну или несколько сетей (слоев), созданных другими агентами, но не нарушает их целостности и не добавляет к ним ни своих данных, ни своих методов. Агенты, решающие свои задачи, связаны между собой планом общей задачи, заданным в базе знаний KG, как сказано выше, в виде граф-схемы. Оптимизация на графах – это классические задачи: - кратчайшие пути и "отмирание" излишних; - распределение (перекачка) ресурсов между вершинами слоя; - статистический анализ, интеграция данных в сети; - вербализация (например, размерные отношения); 15
- выявление "опорных сеток" как базы для конструкторских построений; - выделение признаков (конец, разветвление, угол, радиус и т.п.); - синтез вспомогательных подграфов (треугольники, хорды, сечения); - распознавание (сопоставление) графов; - перевод абсолютных значений параметров в относительные. Решатель логических задач (демон) управляет на логическом уровне агентами в процессе решения задач. Менеджер интерфейса (менеджер проекта) управляет процессом создания, визуализации, поддержки и удаления слоев NGM в режиме диалога с пользователем, работающим над некоторым проектом, обеспечивая ему максимум комфортности и наглядности. 2.8. Динамика проектов Характерной особенностью банков конструкторских данных (БКД) и, соответственно, систем PDM (Product Data Management) является динамичность проектов, которая выражается следующими наиболее частыми изменениями: - чертеж детали; - значения размеров детали; - состав сборки (удаление, добавление, замена компонентов); - значения межобъектных размеров. Введем следующие понятия. Модификация (вариант) продукта – это вариант изделия, в рамках некоторой базовой модели. Например, вариант комплектации (поставки) базовой модели автомобиля Иж2126. Прототип – это модель детали или изделия, используемой при конструировании новой модели (версии) детали изделия для применения в той же или другой предметной области путем изменения параметров и топологии ГМ. Оригинал – ГМ, не имеющая прототипов. Рабочий проект (работа) – это последовательность всех не законченных и законченных версий, полученных в ходе работы над деталью/изделием от выбранного прототипа, если он был, до утвержденной версии. Законченный и утвержденный вариант детали/изделия, имеющий прототип и отличающийся от него только параметрами (размерами), содержит список отличающихся именованных размерных отношений и (или) именованных элементов состава. Законченный вариант оригинальной детали/изделия не имеет прототипа и, соответственно, атрибутов отличий. Рабочий проект содержит последовательность пар {ГМ, ОПЕР_ИЗМ}, где КОЛ(ОПЕР_ИЗМi) ≤ δ при любом i. 16
Рабочий проект представляет собой архив, содержащий все варианты продукта, в том числе не законченные, полученные в ходе проектирования, причем, чем больше допустимая длина файла операций изменения от варианта к варианту, тем меньше общая длина архива проекта. Таким образом, архив (история) – это еще один, но не обязательный (или обязательный только на рабочем месте конструктора) атрибут продукта. 2.9. Вычислительные модели Пример: Дано: 1. Контракты 2. Поставщики 3. Заказчики Найти: контракты такие, что поставщик и заказчик находятся в разных городах. Тогда: Входные параметры: Контракты, Поставщики, Заказчики; Выходные параметры: Контракты; Вычислительная модель: Поставщик.Город ≠ Заказчик.Город. Примечание: В качестве выходных параметров могут быть указаны для наглядности отчета любые промежуточные и вспомогательные атрибуты. Поставщики Имя …………
Адрес Улица …………
Город …………
………
Дом …………
…………
Адрес Город
Город
Улица
Дом
Имя
Страна
Клиенты Имя Город
Адрес Улица
Габариты Длина, м
Ширина, м
………
Дом
Цвет Высота, м
R
17
G
B
Сделки Код
Поставщик
Клиент
Материал
Количество единиц
……..
Материал Имя
Цена
Плотность
Цвет G
R
…………
B
Междугородные контракты Сделка Код
Поставщик
Клиент
Поставщик
Клиент
Город
Клиент
Материал Цвет R
Промежуточная информация Стоимость ВМ: Сделка. количество * материал. Цена;
18
G
B
Стоимость поставки
……
3. ОПИСАНИЕ КОНЦЕПТА Описание концепта содержит (рис. 3.1): -
имя концепта; текстовое описание сущности; формула метода вычисления; атрибуты общих свойств; атрибуты состава сборки; атрибуты схемы функционирования;
Связи Список адресов связей
Адреса геометрических моделей денотатов
Элементы Список адресов узлов
Адрес ГМ
Шасси
Двигатель Ваз 2106
Адрес модели
Цена 60000
Кузов
Расход бензина 10
Схема
Адрес модели
Скорость 150
Состав сборки
Вес
Общие свойства
1100
Имена денотатов Иж2126
Денотаты
Концепт
Структура описания концепта и его денотатов Имя : автомобиль Сущность : Средство передвижения Метод вычисления : ……….. Атрибуты
Рис. 3.1 3.1. Атрибуты общих свойств Общие атрибуты представляют собой ссылки на концепты – узлы деревьев, описывающих модели соответствующих свойств. Кроме того, здесь указаны: тип, ожидаемое значение, пределы варьирования значений, в каких единицах измеряется данный атрибут. Которые принимают значения этого свойства на множестве денотатов данного концепта. Если появляется денотат, у которого какой-либо атрибут отличается настолько, что не вписывается в диапазон, определенный концептом, то должен быть создан новый концепт либо требуется изменить свойства старого концепта. Сложный атрибут – это группа родственных свойств объекта, объединенных общим именем. Например, характеристики материалов. 19
Сложный атрибут имеет тип record , т.е. кортеж простых и сложных атрибутов. В СУБЗ KG тип record содержит ссылку на прототип и список необходимых полей, которые нужны в данном приложении. Например, в структурах, изображенных на рис. 1.1, междугородные контракты. Материал имеет в качестве прототипа концепт «материал», но не содержит все его поля. В СУБЗ KG предусмотрено три способа хранения значений сложного атрибута: 1. Общий случай. Значения находятся непосредственно в строках таблицы денотатов, принадлежащей текущему концепту. 2. Значения хранятся в отдаленной (прикладной) таблице. Концепт отдаленной таблицы является прототипом атрибута, присоединенного к текущему концепту. В этом случае данный атрибут можно рассматривать как простой атрибут, значениями которого являются ссылки на соответствующие строки отдаленной таблицы. 3. Прикладная часть денотата имеет большое количество однородных полей, которые неудобно располагать в одну строку с общей частью. Например, химический состав продукта. В этом случае значениями являются ссылки на таблицы составов (см. ниже). 3.2. Атрибуты состава сборки Если некоторый объект составлен (собран) из нескольких подобъектов, то его концепт содержит группу атрибутов состава. В описании концепта состав объекта задается только компонентами верхнего уровня иерархии с помощью ссылок на соответствующие концепты деталей или подсборок, из которых составляется данный объект. Конкретные образцы продукта содержат ссылки на конкретные образцы (денотаты) деталей и подсборок из множества денотатов того концепта, на который указывает концепт данной сборки. Следует отметить, что состав продукта в KG не программируется, а конструируется пользователем в привычном для него интерактивном режиме путем компоновки структуры из существующих (типовых) и новых (оригинальных) деталей и подсборок. Если появляется новый образец продукта, отличающийся от концепта наличием дополнительных деталей или отсутствием каких-либо деталей, то в дереве классов создается новая вершина – класс, который становится потомком известного класса и куда относится новый образец.
20
3.3. Атрибуты схемы функционирования Для большинства задач АСУП достаточно иметь состав изделия, в то время как многие проектные и конструкторские задачи требуют наличия схемы (кинематической, электрической, функциональной и т.п.), т.е. морфологическое описание объекта. Концепт объекта, задаваемого схемой, помимо атрибутов общих свойств содержит два атрибута схемы: элементы и связи. Денотаты такого объекта в качестве значения «элементы» имеют список адресов в множестве денотатов элементов, например, в файле денотатов «элементы блок-схем», если это схема алгоритма некоторой программы. Концепт для элементов блок-схем находится в дереве классов «символы блок-схем». Аналогично, конкретные связи между элементами некоторой схемы определены концептом, описывающим нужный тип отношения, и находятся в множестве его денотатов. Благодаря этому мы можем устанавливать между элементами схемы различные связи, описывающие различными наборами свойств.
21
4. ПРОЕКТИРОВАНИЕ БАЗ ЗНАНИЙ Проектирование баз знаний выполняется пользователем в диалоговом режиме. СУБЗ предоставляет пользователю набор баз знаний в виде отдельных деревьев. Общий вид СУБЗ в режиме проектирования баз знаний представлен на рис. 4.1.
Рис.4.1 Описание некоторой предметной области в СУБЗ начинается с описания общих понятий, а затем постепенно пользователь переходит к описанию объектов и их свойств. Пользователь имеет возможность создать, переименовать и удалять деревья знаний. Концепты в дереве можно добавлять, переименовывать и удалять. Для быстрого перемещения по деревьям концептов СУБЗ имеет систему закладок. Экземпляры концепта представляются в виде таблицы на вкладке «Экземпляры». Шапка таблицы содержит атрибуты, а строки - экземпляры. Ячейки таблицы заполнены значениями атрибутов соответствующих денотатов. Значения атрибутов по умолчанию выделяются в таблице зеленым цветом. Таблица денотатов может содержать большое количество денотатов. Имена экземпляров в приделах концепта и его потомков должны быть уникальны.
22
4.1. Работа с деревьями знаний Деревья знаний, как и все их концепты, отображаются в области «Концепты». Узлы верхнего уровня этого дерева являются деревьями знаний. Имена деревьев знаний должны быть уникальны. Добавить новое дерево можно через контекстное меню или нажатием клавиши insert, когда выделенный узел дерева «Концепты» является тоже деревом. При создании дерева система попросит ввести имя нового дерева и шаблон, который задает минимальный базовый набор атрибутов дерева. Удаление дерева можно осуществить также через контекстное меню или клавишей delete. 4.2. Работа с концептами Концепт может описывать предмет, процесс, понятие и т.п. Концепт выполняет собирательную функцию - объединяет понятия (концептыпотомки) и образцы в класс. Концепты-листья содержат значительную часть экземпляров предметной области. Концепты "кроны дерева" содержат экземпляры не попавшие в концепты-потомки лишь из-за недостатка информации для их полной идентификации. Классификация производится от общих понятий к более конкретизированным. На рис. 4.2. приведен фрагмент базы знаний, содержащей информацию о деревьях.
Рис. 4.2
23
4.3. Работа с атрибутами Определение атрибутов концепта осуществляется на странице «Атрибуты». Пользователь имеет возможность добавить новый атрибут, изменить свойства существующего атрибута. При добавлении нового атрибута система требует выбора прототипа атрибута. Прототип атрибута должен уже существовать до его использования. Прототипы атрибутов создаются в деревьях построенных на основе шаблона «Свойства». 4.4. Работа с экземплярами Таблица экземпляров (рис. 4.3) содержит информацию о конкретных объектах, которые входят в класс-концепт. Строки таблицы содержат экземпляры. Ячейка таблицы содержит значение атрибута соответствующего экземпляра. Тип атрибута определяет способ выравнивания значения в ячейке таблицы. Значения «по умолчанию» выделяются зеленым цветом.
Рис. 4.3 Таблица экземпляров находится на странице «Экземпляры». Данная страница также содержит странички для описания связей и компонентов состава отдельных экземпляров. Страница «Состав» отвечает за добавление и удаление компонентов состава. В состав экземпляра может быть включен экземпляр из деревьев, построенных на шаблонах: «Предмет» и «Процесс». Страница «Связи» позволяет определять и удалять связи (отношения) экземпляра. Связи экземпляра должны быть заранее определены в одном из деревьев, построенных на основе шаблона «Связи».
24
5. Язык программирования системы KG Данное руководство содержит описание объектов системы KG, доступных через интерпретатор языка LUA. Язык предназначен для создания функциональных расширений системы управления базами знаний KG. Объект Manager. Для работы с объектами баз знаний используется объект Manager. Этот объект позволяет получить все остальные объекты системы. Свойства объекта Manager: 1) count - содержит количество деревьев(только для чтения). 2) version - выдает строку, содержащую версию системы(только для чтения). 3) trees - выдает таблицу(массив) деревьев(массив проиндексирован с 1). Методы объекта Manager: 1) gettreebyname - метод возвращает дерево по имени. У метода один параметр - имя; 2) addtree - метод позволяет добавить дерево. Первый параметр имя, второй – шаблон. Коды шаблонов см. Дерево.pattern. 3) getconcept - метод позволяет получить концепт по имени. Параметр метода должен содержать полное имя концепта; 4) getinstance - метод позволяет получить экземпляр по имени. Параметр метода должен содержать полное имя экземпляра; 5) gettreebyindex – данный метод позволяет получить дерево по его индексу в массиве деревьев системы. Если обращаться к объекту Manager как к массиву, то данный массив будет содержать все деревья. Массив индексируется с нуля. Пример. Вывести наименования всех деревьев и посчитать количество всех концептов. ts = Manager.Trees – получили массив деревьев s = "" -- строка, в которую запишем все имена k = 0 – счетчик концептов for index, value in ts do – траверс массива(таблицы) s =s .. value.name .. "\n"—конкатенация строк; -- value- текущее дерево; value.name – имя дерева k = k + value.count -- value.count- количество концептов в текущем дереве end print(s) – выводим сообщение Объект Дерево. Свойства: 1) name- содержит имя дерева. Имя дерева совпадает с именем его корневого концепта. 25
2) Fullname- содержит полное имя дерева (только для чтения). 3) count- содержит количество концептов в дереве(только для чтения). 4) root – содержит ссылку на корневой концепт дерева (только для чтения) 5) pattern – содержит код шаблона дерева. Может принимать следующие значения: • 0 – нет; • 1 – свойство; • 2 – объект; • 3- процесс; • 4 – факт; • 5- связь. Методы: 1) getconceptbyname – возвращает ссылку на концепт по заданному имени. Метод использует один параметр – имя концепта. Если концепт с таким именем не найден, то возвращается nil. 2) delete – позволяет удалить дерево. Метод не имеет параметров. В случае успешного удаления дерева метод возвращает true, иначе – false. 3) getisvalidname – проверяет имя дерева на синонимичность с заданным именем. Пример. Найти дерево по имени Atrs и вывести его шаблон. t = Manager:GetTreeByName("Atrs") -- дерево по имени if t ~= nil then -- дерево найдено s = t.name -- имя дерева s = s .. " = " .. tostring(t.pattern) -- шаблон в строку end print(s) – выводим сообщение с именем дерева и его шаблон Объект концепт. Свойства: 1) name- содержит имя концепта. 2) Fullname- содержит полное имя концепта(только для чтения). 3) childscount- содержит количество всех потомков концепта, включая потомки потомков (только для чтения). 4) directchildscount- содержит количество непосредственных потомков. Поле используется только для чтения. 5) parent- содержит ссылку на концепт- предок. Если предка нет, то данное поле содержит nil. 6) instancescount- содержит количество экземпляров концепта, включая и экземпляры концептов- потомков(только для чтения). 7) directinctancescount- содержит количество экземпляров концепта(только для чтения). 26
8) attributescount- содержит количество атрибутов концепта, включая пронаследованные атрибуты(только для чтения). 9) directattributescount- содержит количество собственных атрибутов концепта(только для чтения). 10) attributes- содержит массив атрибутов концепта, включая пронаследованные атрибуты(только для чтения). 11) directattributes- содержит массив собственных атрибутов концепта(только для чтения). 12) essence- поле содержит сущность концепта(пока не используется). 13) instancenames- поле содержит все имена экземпляров концепта (только для чтения). Имена разделены символами #13#10. 14) childs- содержит массив всех потомков концепта(только для чтения). 15) directchilds- содержит массив собственных потомков концепта(только для чтения). 16) instances- содержит массив всех экземпляров концепта(только для чтения). 17) directinstances- содержит массив собственных экземпляров концепта(только для чтения). 18) tree- содержит ссылку на дерево, которому принадлежит данный концепт(только для чтения). Методы: 1) getisvalidname- проверяет имя концепта на синонимичность с заданным именем. 2) getchildbyname- возвращает ссылку на концепт-потомок по заданному имени. 3) getchildbyindex- возвращает ссылку на концепт-потомок по заданному индексу. 4) getdirectchildbyname- возвращает ссылку на собственный концептпотомок по имени. 5) getdirectchildbyindex- возвращает ссылку на собственный концептпотомок по индексу. 6) getinstancebyname- возвращает ссылку на экземпляр концепта по имени. 7) getinstancebyindex- возвращает ссылку на экземпляр концепта по индексу. 8) getdirectinstancebyname- возвращает ссылку на собственный экземпляр концепта по имени. 9) getdirectinstancebyindex- возвращает ссылку на собственный экземпляр концепта по индексу. 10) getstrainedinstances- возвращает массив экземпляров концепта, удовлетворяющих выражению, заданному единственным параметром метода. 27
11) getdirectstrainedinstances- возвращает массив собственных экземпляров концепта, удовлетворяющих выражению, заданному единственным параметром метода. 12) getattributebyname- возвращает ссылку на атрибут концепта по его имени. 13) getattributebyindex- возвращает ссылку на атрибут концепта по его индексу. 14) getdirectattributebyname- возвращает ссылку на собственный атрибут концепта по его имени. 15) getdirectattributebyindex- возвращает ссылку на собственный атрибут концепта по его индексу. 16) addchild- позволяет добавить потомка концепту. Первый параметр метода должен содержать имя нового потомка. Если в качестве имени указана пустая строка, то метод сгенерирует новое уникальное имя. Метод возвращает ссылку на созданный концепт-потомок. Если второй параметр задан как true и потомок с данным именем уже существует, то метод возвращает ссылку на существующий потомок с заданным именем и не добавляет новый потомок. Если второй параметр задан как false и потомок с данным именем уже существует, то метод возвращает nil. 17) addinstance- позволяет добавить экземпляр концепту. Первый параметр метода задает имя нового экземпляра. Если в качестве имени указать пустую строку, то метод сам сгенерирует новое уникальное имя экземпляру. Метод возвращает ссылку на созданный экземпляр. Если второй параметр метода задан как true и экземпляр с таким именем уже существует, то метод вернет существующий экземпляр. Если второй параметр метода задан как false и потомок с данным именем существует, то метод возращает nil. 18) addattribute- позволяет добавить атрибут концепту. Первый параметр метода должен содержать ссылку на экземпляр- прототип атрибута. Второй параметр должен содержать имя нового атрибута. Если имя атрибута задано пустой строкой, то метод сгенерирует новое уникальное для атрибута. Если третий параметр метода задан как true и атрибут с именем, заданным вторым параметром, уже существует, то метод возвращает существующий атрибут. Если третий параметр метода задан как false и атрибут с именем, заданным вторым параметром, уже существует, то метод возвращает nil. 19) delete- позволяет удалить концепт. Метод имеет один параметр логического типа- признак переноса экземпляров концепта в предок. 20) clear- позволяет удалить все потомки, экземпляры, атрибуты концепта. 21) getdesdcendant- проверяет не является ли концепт, заданный параметром метода, потомком данного концепта. Если обращаться с данным объектом как с массивом, то он будет содержать все экземпляры концепта. 28
Пример. Вывести массивы атрибутов и экземпляров корневого концепта первого дерева. t = Manager:gettreebyindex(0) -- первое дерево. if t ~=nil then -- дерево получили? c = t.root --корень дерева s = c.fullname .. "\n" -- полное имя концепта s = s .. "atrscount = " .. tostring(c.attributescount) .. "\n" -- количество атрибутов print (s) -- выводим сообщение atrs = c.attributes -- массив всех атрибутов s = "atrs:\n" -- будем формировать строку for i, atr in atrs do -- перебираем массив атрибутов s = s .. atr.name .."\n" -- добавляем в строку имя атрибута end print(s) -- выводим сообщение inss = c.instances -- массив всех значений s = "inss:\n" --будем опять формировать строку for i, ins in inss do --перебираем весь массив s = s .. ins.name .."\n" -- добавляем в сообщение имя экземпляра end print(s) -- выводим сообщение print("same to: ", c.instancenames) -- пока не работает, видимо end Объект Атрибут. Свойства: 1) prototype- содержит ссылку на прототип атрибута. Прототипом атрибута может являться любой экземпляр концепта, находящегося в дереве, созданном на основе шаблона «свойства». 2) owner- содержит ссылку на концепт, которому принадлежит данный атрибут. 3) valuetype- содержит тип атрибута. Может принимать следующие значения: • 0- без типа; • 1- целый; • 2- вещественный; • 3- логический; • 4- строковый; • 5- ссылочный (ссылка на любой экземпляр); • 6- потоковый (stream); • 7- групповой (record); • 8- перечисляемый (enum); • 9- дата; • 10- время; • 11- деньги. 29
4) valuelist- содержит все возможные значения, которые может принимать атрибут. Поле строкового типа. Только для чтения. Работает только для логических и ссылочных типов атрибутов. 5) value- содержит значение атрибута. Поле содержит значения в типах LUA. 6) minvalue- содержит минимальное значения атрибута. Зарезервировано. 7) maxvalue- содержит максимальное значения атрибута. Зарезервировано. Методы: 1) delete- позволяет удалить атрибут. Если атрибут удалился успешно, то метод возвращает истину, иначе - ложь. 2) moveup- позволяет переместить атрибут на одну позицию выше в списке атрибутов концепта. 3) movedown- позволяет переместить атрибут на одну позицию ниже в списке атрибутов концепта. Объект Экземпляр. Свойства: 1) owner- содержит ссылку на концепт, которому принадлежит экземпляр. 2) values- содержит массив всех значений экземпляра. Только для чтения. 3) components- содержит массив всех компонентов экземпляра. Только для чтения. 4) relations- содержит массив всех связей(отношений) экземпляра. Только для чтения. 5) boxescount- содержит количество компонентов экземпляра. 6) boxes- содержит все гнезда компонентов экземпляра. Только для чтения. 7) relationcount- содержит количество связей экземпляра. Методы: 1) getvaluebyname- возвращает значение по имени атрибута экземпляра. Если такового нет, то возвращает nil. 2) getvaluebyindex- возвращает значение по его индексу в массиве значений экземпляра. 3) delete- позволяет удалить экземпляр. Если метод вернул true, то удаление прошло успешно, иначе экземпляр не был удален. 4) isright- позволяет проверить логическое выражение над экземпляром, заданное единственным параметром метода. 5) execute- позволяет выполнить текст программы над данным экземпляром.
30
6) getnamedvalues- возвращает массив значений атрибутов в заданном порядке. Единственный параметр функции должен содержать массив имен атрибутов. 7) setnamedvalues- позволяет установить значения заданных атрибутов экземпляра. Первый параметр должен содержать массив имен атрибутов, а второй параметр- массив значений атрибутов. 8) addbox- позволяет добавить новое гнездо компонента. Метод возвращает индекс гнезда в массиве гнезд экземпляра. Параметр метода должен быть следующего вида: {x = {x = ; y = ; z = }; z = {x = ; y = ; z = }; shift = {x = ; y = ; z = }; scale = ; action = 0 | 1; obj = <экземпляр>}. 9) deletebox- позволяет удалить гнездо компонента экземпляра по его индексу. 10) addrelation- позволяет добавить новую связь экземпляра. Параметр метода должен содержать экземпляр концепт, созданного на основе шаблона «связи». 11) deleterelation- позволяет удалить связь по его индексу. 12) getbox- возвращает гнездо по индексу. 13) getrelation- возвращает связь по индексу. Если использовать данный объект как массив, то массив будет содержать значения атрибутов экземпляра. Пример. Вывести все значения первого экземпляра корневого концепта первого дерева. t = Manager:gettreebyindex(0) -- первое дерево if t~= nil then -- проверка на то, что дерево получено c= t.root -- корень дерева i = c:getdirectinstancebyindex(0)-- первый экземпляр концетп if i ~= nil then -- первый экземпляр концепт есть? vals = i.values -- массив значений экземпляра s = "vals:\n" -- будем формировать строку for j, value in vals do -- перебираем все значения s = s .. tostring(value) .. "\n" -- переводим каждое значение в строку end print(s) -- выводить сообщение с сформированной строкой end end Функция search может быть использована для выборки экземпляров по определенному условию. Для этого необходимо первым параметром функции задать полное имя концепта – область выборки и условие выборки вторым параметром (логическое выражение на языке LUA). Функция save позволяет сохранить (скопировать) список экземпляров в заданный концепт. Первым параметром функции задается полное имя концепта, в который будут скопированы экземпляры, заданные вторым парамет31
ром. Функция при необходимости дополняет концепт- получатель атрибутами концепта-источника, которому принадлежат сохраняемые экземпляры. Пример использования функций search и save. Выбрать все экземпляры концепта «Atrs», названия которых содержат четыре символа, в концепт Temp. inss = select('/atrs', 'self[“вес”] == 4') --произвели выборку по условию temp = Manager:AddTree(“Temp”, 0) -- создаем концепт save(Temp.root.fullname, inss) --сохраняем выборку
32
ЛИТЕРАТУРА 1. В.Н. Кучуганов, Семантика графической информации. Известия ТРТУ. Тематический выпуск «Интеллектуальные САПР». Материалы Международной научно-технической конференции «Интеллектуальные САПР». Таганрог: Изд-во ТРТУ, 2002, №3(26). с. 157 – 166. 2. Аверкин А.Н., Гаазе-Рапопорт М.Г., Поспелов Д.А. Толковый словарь по искусственному интеллекту. М.: Радио и связь, 1992. 3. Справочник по искусственному интеллекту / В 3-х т. Под ред. Э.В.Попова и Д.А. Поспелова. - М: Радио и связь, 1990. 4. Roberto Ierusalimschy. Programming in Lua. Published by Lua.org, 2003 288 p.
33
