Метод вывода ограничений целостности в графических редакторах АСТПП

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

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

Метод вывода ограничений целостности в графических редакторах АСТПП

Митин А.А.

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

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

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

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

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

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

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

Одной их первых техник автоматизированного задания ограничений явились правдоподобные предположения, использованные в системе Peridot [1], [2]. При создании объекта система рассматривала все возможные геометрические взаимоотношения этого объекта с введенными ранее объектами и предлагала пользователю выбрать из списка требуемое ограничение или ввести дополнительную информацию, поясняющую его желание. При большом количестве введенных геометрических объектов такой подход оказывается неудачным, т.к. количество потенциально возможных ограничений слишком велико, и пользователю приходится производить много вспомогательных действий для указания желаемого ограничения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Множество ограничений C, определенных в базовом наборе, включает такие ограничения: ВЕРТИКАЛЬНОСТЬ, ГОРИЗОНТАЛЬНОСТЬ, ПЕРПЕНДИКУЛЯРНОСТЬ, ПАРАЛЛЕЛЬНОСТЬ прямых, ПРИНАДЛЕЖНОСТЬ ТОЧКИ прямой, ПРОПОРЦИЮ, СУММАТОР, ИНЦИДЕНТНОСТЬ точек, УГЛЫ между прямыми.

Описанный базовый набор ограничений можно условно разбить на два класса: геометрические ограничения и негеометрические. К геометрическим ограничениям можно отнести такие ограничения, как ВЕРТИКАЛЬНОСТЬ, ГОРИЗОНТАЛЬНОСТЬ, ПЕРПЕНДИКУЛЯРНОСТЬ, ПАРАЛЛЕЛЬНОСТЬ прямых, ПРИНАДЛЕЖНОСТЬ ТОЧКИ прямой, ИНЦИДЕНТНОСТЬ точек, УГЛЫ между прямыми. Эти ограничения формально могут быть определены с помощью формул аналитической геометрии.

Негеометрические ограничения ПРОПОРЦИЯ и СУММАТОР выражают простые математические зависимости. Атрибут КОЭФФИЦИЕНТ этих ограничений в зависимости от типа ограничений представляет коэффициент пропорции или величину приращения, используемую сумматором. С ограничением ПРОПОРЦИИ связаны методы, определяющие одну из связываемых объектом величин через другую и коэффициент пропорции. Методы, ассоциированные с ограничением СУММАТОР, так же определяют значения связываемых величин друг через друга и определяемую атрибутом КОЭФФИЦИЕНТ разницу между ними.

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

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

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

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

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

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

Подмножества 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 по соответствующим атрибутам графических объектов.

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

В соответствии с требованиями к графическому редактору с выводом ограничений целостности и его структуре, показанной на рисунке 1, разработано представление реализации графического редактора средствами языка UML [5]. Рисунок 4 иллюстрирует компоненты графического редактора с выводом ограничений целостности в нотации языка UML.

Рисунок 4 - Диаграмма компонентов графического редактора с выводом ограничений целостности в нотации языка UML

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

Компонент диаграммы «Действия пользователя» обрабатывает действия пользователя при работе с графическим редактором. Действия пользователя при работе с графическим редактором можно разделить на две группы: действия, связанные с внесением или изменением информации о графических объектах, и действия, связанные с выбором или отклонением ограничений из некоторого набора представленных пользователю пиктограмм. При взаимодействии пользователя с системой происходит создание, модификация, удаление графических объектов (методы Insert, Pick, Move, Delete), а вместе с тем изменение информации об объектах в базе фактов, где данные о них представлены в виде атрибутной грамматики. Результатом работы компонента является модифицированное состояние базы фактов.

Компонент «База данных фактов» формирует представление информации о графических объектах и ограничениях, принятых в системе.

Компоненты на построенной диаграмме взаимодействуют посредством интерфейсов. Интерфейсы на диаграмме представлены в виде кружков. Непрерывная линия, идущая от компонента к кружку-интерфейсу, указывает на то, что данный компонент обеспечивает работу интерфейса. В том случае, когда от компонента к интерфейсу идет пунктирная стрелка, это означает, что компонент требует для своей работы наличия доступа к данному интерфейсу.

Так на диаграмме компоненты «Действия пользователя» и «База данных фактов» взаимодействуют через интерфейс «Изменение данных об объектах». Результатом работы данного интерфейса является модификация базы данных фактов.

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

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

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

Все правила, используемые графическим редактором с выводом ограничений целостности, хранятся в базе данных правил. На диаграмме (рисунок 4) набору правил соответствует компонент «База данных правил».

Компоненты «База данных правил» и «Редактор правил» взаимодействуют посредством интерфейса «Модификация правил». Интерфейс должен обеспечивать механизмы изменения продукционных правил, использующихся системой логического вывода.

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

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

Исходя из семантики продукционных правил компоненту «Вывод ограничений» необходимо получить доступ к информации о графических объектах, которая хранится в базе данных фактов. При чтении информации из базы данных фактов проводится проверка соответствия значений атрибутов графических объектов предпосылкам продукционных правил. Таким образом, компоненты «Вывод ограничений» и «База данных фактов» связаны на диаграмме посредством интерфейса «Выбор и модификация данных». Основным результатом работы интерфейса является выбор атрибутов графических объектов и их значений для интерпретатора продукционных правил.

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

Для работы с ограничениями на диаграмме введен компонент «Представление ограничений», взаимодействие которого с модулем удовлетворения ограничений реализуется посредством интерфейса «Набор уравнений». Множество уравнений служит для пересчета значений атрибутов графических объектов.

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

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

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

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

Литература

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

2. Myers B.A. Creating User Interfaces by Demonstration. - Boston:
Academic Press. -1988.

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

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

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

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