Применение механизма продукционных правил для вывода ограничений целостности в графических редакторах АСТПП

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Применение механизма продукционных правил для вывода ограничений целостности в графических редакторах АСТПП

Митин А.А.

В последнее время появилось большое количество программных систем, служащих для создания графического пользовательского интерфейса в АСУТП и АСТПП. Растет интерес к методам их создания. Пользователь, как правило, не обладает специализированными знаниями, связанными с управлением сложными вычислительными системами. Поэтому в современных графических пользовательских интерфейсах (ГПИ) применяются различные методы, дающие возможность пользователю упростить процесс взаимодействия с системой. Среди этих методов - метод, основанный на метафоре модели мира, прямое манипулирование объектами, вывод геометрических ограничений целостности и т.д. При этом пользователь должен иметь возможность быстро изучать принципы работы с системой и наиболее эффективно решать свои прикладные задачи.

Исследования в области построения графического пользовательского интерфейса позволили выявить следующее:

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

2. Эти соотношения должны обслуживаться пользовательским интерфейсом вместе с графическими объектами в БД как ограничения целостности.

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

4. Существуют попытки логически выводить ограничения целостности из действий пользователя.

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

Как было показано во многих работах, большое число задач автоматизации может быть решено за счет эффективного использования техники обработки ограничений. Особенно широко ограничения были использованы в задачах автоматического геометрического планирования в интерактивных пользовательских интерфейсах. Декларативная семантика языков ограничений позволяет определять графические объекты и их внутренние связи, избегая лишней информации о реализации алгоритмов визуализации. Одним из больших преимуществ использования ограничений является их способность описывать сложные объекты просто и естественно. Поэтому техника работы с ограничениями может использоваться для декларативного представления знаний о взаимном расположении объектов в процессе создания и ведения графической документации в графических редакторах АСТПП.

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

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

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

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

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

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

1. Проектируемые в графическом редакторе изображения имеют сложную структуру. Поэтому ПИ должен обеспечивать создание и управление объектами сложной структуры.

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

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

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

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

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

<G, C, F, R, P, V>,

где G - множество графических примитивов редактора;

C - множество ограничений, определенных в базовом наборе;

F - множество фактов, содержащих данные о графических объектах;

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

P - множество графических представлений, необходимых для осуществления функции визуализации;

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

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

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

· подмножества N имен объектов предметной области;

· подмножества P имен свойств, которые рассматриваются в качестве атрибутов объектов;

· подмножества V допустимых значений атрибутов.

Рисунок 1 - Структура графического редактора с выводом ограничений целостности

Подмножества N и V обычно перекрываются.

Используемая грамматика имеет вид триад объект-атрибут-значение. Триада (v,р,w) существует, если v N и р P, и w V. Например, триада (ТОЧКА, координата, значение) представляет отдельную точку, одна из координат которой имеет определенное значение.

Представленная синтаксическая форма обобщается в том случае, когда нужно для некоторого объекта v представить n вариантов пар атрибут-значение (р1,w1),…, (рn,wn). В таком случае они объединяются в вектор в форме (v, р1, w1, рn, wn) [4].

Для реализации продукционной системы в составе графического редактора АСТПП разработан специализированный язык представления продукционных правил для вывода ограничений целостности. В данном подходе левая часть правила или условие детализируется и состоит из двух частей: условие сопоставления конкретного объекта определенному классу (Сопоставить) и проверка атрибутов графического объекта на удовлетворение определенным условиям (Проверить). Правая часть правила состоит также из двух частей: создание нового факта в рабочей памяти (Создать) и выполнение методов, относящихся к определенным объектам (Выполнить). Эти методы могут быть направлены на модификацию значений атрибутов графических объектов или удаление определенных фактов (объектов) из рабочей памяти.

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

Рисунок 2 - Пример определения правила для ограничения параллельности отрезков

Разработанный механизм вывода геометрических ограничений целостности использует алгоритм, построенный на основе усовершенствованного алгоритма Rete. Разработанный алгоритм использует для представления модели системы граф или сеть. В контексте прямой цепочки рассуждений, алгоритм определяет процедуру, которая работает путем перемещения каждого нового факта через узлы сети, каждый из которых представляет операцию реляционной алгебры на одном или нескольких отношениях. Каждый факт представляет информацию об определенном графическом объекте. Узлы сети Rete делятся на два вида: альфа-узлы и бета-узлы. Альфа-узел - узел, в котором хранится отношение для определенного антецедента (левой части) продукционного правила. Отношение каждого альфа-узла накапливает все факты или утверждения, формирующиеся посредством операции SELECT. Бета-узел сети Rete - узел, хранящий результат объединения нескольких отношений, выполняемого с помощью операции реляционной алгебры JOIN.

На рисунке 3 представлена сеть Rete для правила, проверяющего отношение длин между двумя отрезками. Узлы A1, A2, A3 - альфа-узлы, сформированные для каждого антецедента продукционного правила с помощью операции реляционной алгебры SELECT. Узлы B12, B23 - бета-узлы, полученные объединением отношений альфа-узлов посредством операции JOIN. Результирующее отношение, хранящееся в узле Результат, формируется посредством операции проекции PROJECT по соответствующим атрибутам графических объектов.

Так как для вывода ограничений используется продукционная система, то сложность алгоритма вывода ограничений полностью зависит от алгоритма, выбранного для функционирования продукционной системы. Для реализации механизма вывода был использован алгоритм, построенный на основе усовершенствованного алгоритма Rete. Известно, что сложность алгоритма Rete зависит от количества правил (точнее, от общего количества элементарных условий в левой части правил) и количества фактов в системе.

Таким образом, сложность алгоритма Rete составляет O(с*f), где с - общее количество элементарных условий в левой части правила, а f - количество фактов.

Так как количество фактов при усложнении графического изображения (чертежа) увеличивается, в результате работы системы вывода появляется большое количество вопросов к пользователю по принятию тех или иных ограничений. Для устранения такого эффекта было принято решение производить в системе вывод новых ограничений только для выделенных объектов. В результате время работы алгоритма вывода ограничений перестало зависеть от общего количества фактов, представляющих данные об графических объектах, тем самым сложность алгоритма вывода составляет O(c). Так как набор правил фиксирован, то время работы алгоритма вывода ограничений также фиксировано.

Рисунок 3 - Сеть Rete для правила, проверяющего отношение длин между двумя отрезками

Литература

1. Myers, B. A. Creating Interaction Techniques by Demonstration [Text] / B.A. Myers // IEEE Computer Graphics and Applications. - 1987. - P. 51 - 60.

2. Myers, B. A. Creating User Interfaces by Demonstration [Text] / B.A. Myers. - Boston: Academic Press. - 1988.

3. Borning, A. Constraint-Based Tools for Building User Interfaces [Text] / A. Borning, Duisberg // ACM Transactions on Graphics, 1986. - Vol. 5. - N.4. - P. 345 - 374.

4. Питер, Дж. Введение в экспертные системы [Текст] : учеб. пособие : [пер. с англ.] / Джексон Питер. - М.: Издательский дом «Вильямс», 2001. - 624 с.

5. Рамбо, Дж. UML [Текст] : специальный справочник / Дж. Рамбо, А. Якобсон, Г. Буч. - СПб.: Питер, 2002. - 656 с.

Размещено на Allbest.ru