автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Алгоритмы и программные системы для геометрических задач параметрического проектирования

На правах рукописи

Ершов Алексей Геннадьевич

Алгоритмы и программные системы для геометрических задач параметрического проектирования

О

Специальность 05 13 11 -Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

ооз

Новосибирск-2007

003160650

Работа выполнена в Институте систем информатики СО РАН

Научный руководитель: кандидат физико-математических наук

Ушаков Дмитрий Михайлович

Официальные оппоненты.

д ф -м н , профессор Лаврентьев Михаил Михайлович

Ведущая организация: Институт вычислительной математики и

математической геофизики СО РАН.

Защита состоится 8 ноября 2007 на заседании диссертационного совета К003 032 01 в Институте Систем Информатики им А.П Ершова Сибирского Отделения РАН по адресу 630090, Новосибирск, пр ак Лаврентьева, 6

С диссертацией можно ознакомиться в читальном зале библиотеки ИСИ СО РАН (пр ак. Лаврентьева, 6)

Автореферат разослан 28 сентября 2007

к ф -м н ,

Кашеварова Татьяна Петровна

Ученый секретарь диссертационного

совета К003 032 01

к ф -м н Мурзин Ф А

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Целью диссертации является разработка математических методов и алгоритмов, а также создание эффективных программных средств, позволяющих решать геометрические задачи параметрического проектирования

Задачи диссертационного исследования:

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

2 Разработка методов алгебраического моделирования, сводящих такие задачи к системам уравнений меньшей размерности, чем известные методы,

3 Разработка методов геометрической декомпозиции задач параметрического проектирования,

4 Изучение применимости интервальных методов для решения таких задач,

5 Эффективная программная реализация предложенных алгоритмов в рамках геометрических решателей

Научная новизна. В ходе работы над диссертацией получены следующие

новые, своевременно опубликованные научные результаты

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

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

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

4 Разработана и реализована библиотека вычислений элементарных функций с помощью разложения в степенные ряды Чебышева и Тейлора, позволяющая получать гарантированную интервальную оценку результата и обладающая высокой производительностью и точностью;

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

Практическая ценность работы заключается в том, что

1 На основе предложенных методов разработаны двухмерный геометрический решатель ЬОБ 2Т> и трехмерный геометрический решатель ЬвБ ЗО Эти решатели являются коммерчески востребованными программными продуктами и были успешно

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

2 Разработана библиотека Imath интервальных элементарных функций, вместе с несколькими реализованными автором интервальными методами составляющая часть универсального решателя задач в ограничениях LEMO,

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

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

• Second International Forum isiCAD «PLM+ERP Informational Environment of Modern Enterprise» - 2006,

• Международном семинаре «Интервальная математика и методы программирования в ограничениях» - 2004,

• First International Forum isiCAD «Research and Market Solutions for PLM, Modelmg and Computer Graphics» - 2004,

• Пятой международной конференции «Перспективы систем информатики» - 2003,

• Международной конференции «Современные проблемы прикладной математики и механики теория, эксперимент и практика» - 2001,

• Четвертом сибирском конгрессе по прикладной и индустриальной математике «ИНПРИМ» - 2000.

Автор имеет 17 публикаций, из них 12 по теме диссертационной работы

Практические программные разработки - геометрические решатели LGS 2D и LGS 3D - были внедрены в следующие коммерческие программные системы

• ADEM-VX, производитель ADEM Technologies, Россия,

• Masterwork, производитель Tecnos G А Sri, Италия,

• ClassCAD, производитель AWV, Швейцария,

• продукты для обмена данными САПР компании Proficiency, Израиль

Кроме того, клиент-серверное веб-приложение FlashLGS, созданное на

базе LGS 2D, используется в образовательных целях в Новосибирском

Государственном Техническом Университете

Личный вклад автора заключается в

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

• Разработке совместно с Руколеевым Е.В метода остовного моделирования, наибольший вклад автором внесен в разработку алгоритмов построения остовного представления,

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

• Руководстве разработкой архитектуры и программной реализацией геометрических решателей LGS 2D, LGS 3D и решателя LGSEP систем нелинейных уравнений,

• Единоличной программной реализации интервальной математической библиотеки элементарных функций Imath, а также многих методов решателей LGS и LEMO

На защиту выносятся следующие положения

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

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

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

• Разработанные на базе теоретических результатов и предложенных архитектурных решений программные компоненты для задач параметрического проектирования являются достаточно эффективными и сравнимыми с мировыми аналогами

Структура и объем работы

Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и приложения, содержит 168 страниц машинописного текста (153 без списка литературы и приложения), 31 рисунок, 6 таблиц, список литературы из 95 наименований

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обсуждается развитие области автоматизации проектирования, отмечается ключевое свойство наиболее современных и мощных САПР - способность к параметризации данных Выделяются два подхода к параметризации геометрических задач САПР иерархическое и вариационное проектирование

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

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

Далее во введении объявляется цель и задачи диссертационного исследования, дается краткое описание последующих глав диссертации

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

В параграфе 1 1 приводится известное определение понятия задачи параметрического проектирования как упорядоченной пары (V, Е), где V - множество геометрических объектов, а Е - множество ограничений между ними. Решением задачи называют такое положение геометрических объектов, что все ограничения удовлетворены Такое определение не учитывает

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

• Оптимизационного характера этих задач - пользователю нужно не любое решение задачи, а наиболее близкое к начальному положению объектов,

• Обработки задач с помощью ЭВМ, что подразумевает указание точности вычислений

В силу указанных недостатков в параграфе 1 2 предлагается более полное и адекватное определение задачи параметрического проектирования

Определение. Общая постановка (на ЭВМ) задачи параметрического проектирования в й -мерном пространстве есть упорядоченная шестерка Z = (V ,Е,С,80,Р,б), где

1 V = (V, Р) - структура объектов, состоящая из множества объектов V = У<1 , где V1 - множество из п с?-мерных

ТГ*

геометрических объектов, V - множество # вещественных переменных, и функции числа дополнительных параметров Р:¥а —> N Через Р:Уа—> N определяется общее число

обобщенных координат С : V —>■ N • для V е V *, С(у) = 1, для

дополнительных параметров

и функция числа

V

V е Г*, СО) = Р{у) + С= Р(у) + й{й + \)/2,

2 Е — (Е, а, А) - структура ограничений, состоящая из Е a J^J х R - множества т ограничений над объектами из V,

¡eN

функции арности а: Е —> N и функции аргументов

A:ExN—>V^J {0} Каждое ограничение е & Е является

вещественнозначной функцией, вычисляющей невязку,

е: (Лс«ы» х..х [0,оо),

3 G = {g1,..,gk} - множество к тел, с и (Jgt=Vd,

<6{i, ,*}

причем i Ф j <=> gt C\gj - 0,

4 S0={<vi,sl>,..,<vH,s„>}, где {vl,..,vn} = V, vt Ф vj <=> i ^ j , S: El R ^ — начальное означивание объектов,

5 F : S(V) x S(V) —> [0,oo) - функция близости означиваний,

6 e e [0, оо) - точность вычислений

Множество положений объектов описывается с помощью набора трансформаций Т = ((i1,..,ijt),(A1,. ,Др+9)), состоящего из движений

tj,. ,tk тел задачи и приращений А,,..,Ap+q & R ее переменных и

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

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

d(Z) = Y,<t(g) + P + <l-ЕА(е)'где P = ZP(y)' <i = card(V*),

geG ееЕ v

1г:Е N - функция степеней свободы ограничений, (I' С —> N -функция количества независимых параметров, необходимых для описания движения тела в пространстве с точностью до автоморфизмов. Это определение отличается от традиционного учитываются автоморфизмы тел, наличие переменных и объектов с дополнительными параметрами За счет этих отличий введенное определение позволяет более корректно задать понятия переопределенной, недоопределенной и хорошо определенной задачи Далее описываются гиперграфы и графы, представляющие задачи параметрического проектирования Доказывается, что множество графов хорошо определенных задач, все подзадачи которых недоопределены, бесконечно даже для простейшего подкласса двухмерных задач

В параграфе 14 выделяются три основных направления исследований в области методов решения задач параметрического проектирования методы алгебраического моделирования, методы геометрической декомпозиции и методы искусственного интеллекта Проводится анализ известных методов и оценка их слабых сторон, на основании этого анализа в параграфе 1 5 формулируются дальнейшие задачи диссертационного исследования

Вторая глава посвящена подходу к решению задач параметрического проектирования, заключающемуся в алгебраическом моделировании таких задач Этот подход предполагает два направления исследований разработку самого метода моделирования, переводящего ограничения в систему нелинейных алгебраических уравнений, и разработку методов решения получаемых систем уравнений Изложение традиционного способа алгебраического моделирования - 6-параметрического декартова моделирования - дано в параграфе 2 1 Параграф 2 2 представляет (для случая трехмерного пространства) новый метод остовного моделирования, разработанный на основе декартова моделирования Параграф 2 3 представляет способ использования методов базиса Гребнера для решения систем полиномиальных уравнений в рамках геометрического решателя

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

'я Л

трансформацией Т(а,/3,у,х,у,г) = ^

где Я = Я„ оЯй о^

а "р "у '

композиция вращений вокруг координатных осей, / = (х, у, г)7 - вектор

смещений Все положения тела g * относительно другого тела g, если между объектами этих двух тел v,w задано бинарное ограничение, как правило, можно описать формулой производного представления

К (РгР J = XI о T(Plрт ) о с о (Xv°Г1, где

Ху — положения объектов, С - некоторая константная

трансформация, называемая каноническим решением, а Т(р1,..,рт) -

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

• Ограничение таково, что множество его решений представимо в виде комбинаций вращений и смещений,

• Ограничение является геометрическим, то есть сохраняет свою невязку при воздействии на все его объекты одинакового движения;

• Представление положений параметризируемого тела в виде комбинаций вращений и смещений таково, что оно сводится к фиксированию нескольких параметров в Т(а, /3, у, x,y,z)

Для каждого их приведенных условий в тексте диссертации приводятся примеры ограничений, для которых это условие не выполняется

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

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

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

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

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

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

всегда можно разместить при любом положении объектов, не входящими в g, но являющимися аргументами ограничений V -образца Анализ

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

Function CuttingDecomposition(Z) For each e from E Rem(e) := FALSE Form(Degree,Mapping)

G' s= {g from G | Degree(g)<=C}, G* := {} While (G' is non empty) do loop A g := G' .pop()

If (CheckCuttmg(g,Mapping(g))) then do

For each e from Mapping(g) do loop В If (Rem(e)=TRUE) continue Rem (e) : = TRUE

For each g' from A(e) do loop С

Degree(g') := Degree(g')-l • If (Degree(g')<=C) then do

Reform(Mapping(g'),Rem) G'.push(g')

Endif End loop С End loop В G*.push(g) G.pop(g)

Endif End loop A

В этом псевдокоде, работающем на гиперграфе, вершинами которого являются тела, а гиперребрами - ограничения, используются следующие структуры данных Е - множество гиперребер, G -множество вершин, Rem - булевы пометки гиперребер, Degree -степени вершин, А - массивы инцидентных конкретному гиперребру вершин, Mapping - массивы инцидентных конкретной вершине гиперребер, G' - стек активных вершин, G* - готовая последовательность корректно отделяемых вершин-тел Константа С

равна Cf+1, где d - размерность пространства Функция CheckCuttmg

выполняет проверку соответствия тела корректным V -образцам из заранее заданного списка за константное время, общее время работы

алгоритма отделяющей декомпозиции линейно, причем его результат (множество С *) не зависит от порядка отделения тел

Новый метод предлагается применять для недоопределенных и хорошо определенных задач Далее рассматриваются расширения метода отделяющей декомпозиции с помощью V -образцов, корректность которых зависит от взаимного положения объектов внутри отделяемого тела (проверяемого априори), и с помощью нуль-эвристических образцов, для которых отделение тела корректно для всех случаев, кроме множества случаев меры нуль Рассматриваются свойства метода отделяющей декомпозиции, в том числе эффективность его комбинирования с методом двухсвязной декомпозиции

Четвертая глава посвящена применению для решения задач параметрического проектирования интервальных методов (как наиболее перспективных среди методов искусственного интеллекта согласно литературному обзору) Формулируется постановка двух задач разработки основ необходимой для применения интервальных методов интервальной библиотеки вычислений элементарных математических функций и исследования практической применимости интервальных методов для решения задач параметрического проектирования

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

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

1 погрешность, вызываемая использованием вместо бесконечного ряда его конечной частичной суммы,

2 погрешность, вызываемая использованием вместо истинных значений коэффициентов полиномов их машинных приближений,

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

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

1 В интервалах, содержащих нуль функции f(x), вычисляется ее разложение Тейлора,

2 В интервалах, на которых колебание f(x) превышает колебание х — f(x), вычисляется разложение Чебышева функции X — f(x),

3 На остальных интервалах вычисляется разложение Чебышева f {х)

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

В параграфе 4 3 приводится описание общей схемы работы интервальных методов сужения и бисекции, способной получить набор сколь угодно малых интервальных оценок, содержащих все решения задачи параметрического проектирования Для контроля за количеством элементов в этом наборе предлагается метод склейки корней на основе понятия доля решений в брусе Такой метод позволяет отделить проявления эффекта "ползущих корней" от наличия большого количества корней из-за недоопределенности задачи Далее рассматриваются вопросы применения интервальных методов к решению задач параметрического проектирования и сделан вывод, что они не должны применятся в качестве основного метода решения из-за экспоненциальной оценки времени работы Их можно использовать для

1 решения задач с интервальными данными,

2 решения проблемы определения совместности задачи,

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

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

диссертацией ЬЕМО - универсальный решатель задач с недоопределенными данными, 1Л38ЕР - решатель систем нелинейных уравнений, ЬвБ 2В и ЗБ - решатели двух- и трехмерных задач параметрического проектирования, 1таШ - библиотека вычисления интервальных функций с направленными округлениями Параграф 5 2 посвящен архитектуре реализованных под руководством автора геометрических решателей 1ХЗБ 2Э и ЗО, в том числе механизму вычислительных ветвей и схеме классификации задач для решения их специализированными методами. Параграф 5 3 излагает аспекты реализации решателя систем нелинейных уравнений 1Х»8ЕР, а параграф 5 4 - решателя ЬЕМО, в частности, оптимизацию работы метода бисекции Параграф 5 5 повествует об интеграции решателей 1Х}8 в конечно-пользовательские приложения, в т.ч САПР Параграф 5 6 посвящен оценке экспериментальных результатов от реализации предложенных автором теоретических методов

Экспериментальные результаты сравнения метода остовного моделирования с 6-параметрическим декартовым моделированием на базе из 3120 индустриальных трехмерных тестов

1 Уменьшение в 2 раза размера генерируемых систем уравнений,

2 Общее время решения всех тестов уменьшилось более чем в три раза,

3 Увеличилось число успешно решенных тестов

Результаты от внедрения метода остовного моделирования в существующую схему вычислительных ветвей решателя Ьв8 ЗБ на той же базе

1 Общее время решения всех тестов уменьшилось примерно в два раза,

2 Уменьшилось в два раза число не решаемых 1Л38 ЗО тестов

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

1 Общее время решения двухмерных задач уменьшилось в 24 8 раз,

2 Общее время решения трехмерных задач уменьшилось в 3 78 раз

Экспериментальная оценка интервальной библиотеки элементарных математических функций показала следующие результаты

1 В 80-90% вычислений функций для точечного аргумента результат является максимально узким интервалом,

2 Производительность отличается от производительности стандартной математической библиотеки С++ не более, чем на 1%,

3 Объем памяти для хранения коэффициентов составляет всего 69 килобайт

При внедрении решателя LGS 3D в одну из промышленных САПР

было проведено его сравнение с ранее использовавшимся коммерческим

решателем На базе из 3120 индустриальных трехмерных тестов были

получены такие результаты

1 Количество тестов, успешно решаемых LGS 3D, составило 99 29% против 83 17% у ранее используемого решателя,

2 Общее время решения всех тестов у LGS 3D меньше на 24%

В Заключении сформулированы основные результаты работы

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

2 Разработан новый метод отделяющей декомпозиции, относящийся к классу методов геометрической декомпозиции Метод корректно декомпозирует задачу и имеет линейную вычислительную сложность, он апробирован в коммерческом программном обеспечении и способствует многократному росту его производительности,

3 Проведены исследования в области интервальных методов решения задач параметрического проектирования, в том числе разработан подход к вычислению интервальных элементарных математических функций с направленными округлениями, основанный на разложении в ряд Чебышева и Тейлора Осуществленная программная реализация этого подхода позволяет получать неулучшаемые в 80-90% случаев интервальные оценки значений функций, причем производительность вычислений не уступает стандартной библиотеке С++,

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

5 Разработаны при участии автора в качестве руководителя или исполнителя следующие системы LGS 2D и LGS 3D - решатели

двумерных и трехмерных задач параметрического проектирования, LGSEP - решатель систем нелинейных уравнений, LEMO -универсальный решатель задач с недоопределенными данными, Imath- библиотека интервальных элементарных функций Решатели LGS 2D и 3D нашли практическое применение в отечественных и зарубежных программных системах, использующихся в коммерческих и образовательных целях

Публикации. Основные результаты диссертации изложены в работах

1 Ершов А Новый метод моделирования задач параметрического проектирования // САПР и Графика - 2007 - №9 - С 32-35

2 Семенов A JI, Важев И В , Кашеварова Т П, Бревнов Е В , Ершов А Г , Клейменов А Е , Лещенко А С , Лоенко М.Ю, Петунин Д В Интервальные методы распространения ограничений и их приложения Сборник научных трудов "Системная Информатика" №9, Институт систем информатики СО РАН - Новосибирск, 2004 -С 245-358

3. Ershov А, Eremchenko A Two New Decomposition Techniques m Geometric Constraint Solving // First International Forum isiCAD Proc -Novosibirsk, 2004 - P 91-102

4 Ershov A G , Kashevarova T P Interval Mathematical Library Based on Chebyshev and Taylor Series Expansion // Reliable Computing - 2005 — Vol 11, №5 -P 359-367

5 Ershov A., Ivanov I, Preis S , Rukoleev E , Ushakov D LGS Geometric Constraint Solver // Int Conf Perspectives of Systems Informatics, Novosibirsk, 2003 - Berlin, 2003 - P 423-430 - (Lecture Notes in Computer Science, 2890)

6 Ершов А Г Использование алгоритма построения базисов Гребнера в рамках концепции программирования в ограничениях // Тезисы докладов Четвертого сибирского конгресса по прикладной и индустриальной математике (ИНПРИМ-2000), Институт математики СО РАН. - Новосибирск, 2000 -Часть IV -С 105-106

7 Ershov A Enchancmg Techniques for Geometric Constraint Solving // Preprmt №3 - Novosibirsk, LEDAS Ltd., 2003 - 40 p

8 Ershov A, Ivanov I, Kazakov A, Lipski S , Markm V , Preis S., Rukoleev E., Sidorov V., Ushakov D LEDAS Geometric Solver product overview // Preprint №5 - Novosibirsk, LEDAS Ltd, 2003 - 56 p

Ершов А Г

АЛГОРИТМЫ И ПРОГРАММНЫЕ СИСТЕМЫ ДЛЯ ГЕОМЕТРИЧЕСКИХ ЗАДАЧ ПАРАМЕТРИЧЕСКОГО ПРОЕКТИРОВАНИЯ

Автореферат

Подписано в печать 27 09 2007 Объем 1,0 уч -изд л

Формат бумаги 60 х 90 1/16_Тираж 100 экз

Отпечатано в ЗАО РИЦ «Прайс-курьер»

630090, г Новосибирск, пр Ак Лаврентьева, 6, тел 330-72-02 Заказ №747

ВВЕДЕНИЕ.

1. Задачи параметрического проектирования.

1.1 Вводные определения.

1.2 Формальное определение задачи параметрического проектирования.

1.3 Степени свободы в задачах параметрического проектирования.

1.4 Обзор существующих методов решения.

1.4.1 Классификация направлений исследования.

1.4.2 Методы алгебраического моделирования.

1.4.3 Методы геометрической декомпозиции.

1.4.4 Методы искусственного интеллекта.

1.4.5 Методы решения систем нелинейных уравнений.

1.5 Выводы.

2 Алгебраическое моделирование задач параметрического проектирования.

2.1 Постановка задачи.

2.2 Метод остовного моделирования.

2.2.1 Геометрические основы метода.

2.2.2 Алгоритмическое описание метода остовного моделирования.

2.3 Схема использования метода базисов Гребнера.

2.4 Выводы.

3. Методы геометрической декомпозиции задач параметрического проектирования.

3.1 Начальные определения.

3.2 Критика известных методов декомпозиции.

3.3 Описание метода отделяющей декомпозиции.

3.4 Алгоритм отделяющей декомпозиции и его временная сложность.

3.5 Расширения метода отделяющей декомпозиции.

3.6 Свойства метода отделяющей декомпозиции.

3.7 Выводы.

4. Интервальные методы в задачах параметрического проектирования.

4.1 Постановка задачи.

4.2 Интервальная математическая библиотека.

4.2.1 Выбор подхода к вычислению элементарных функций.

4.2.2 Минимизация погрешности вычислений на каноническом интервале.

4.2.3 Минимизация погрешности вычислений при приведении аргумента.

4.2.4 Другие вычислительные аспекты.

4.3 Интервальные методы решения задач в ограничениях.

4.3.1 Описание метода CP распространения ограничений.ИЗ

4.3.2 Описание интервального метода бисекции.

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

4.4 Выводы.

5. Аспекты программной реализации и практического использования.

5.1 Реализованные программные компоненты.

5.2 Архитектура решателей LGS 2D и 3D.

5.2.1 Объекты интерфейса и их трансляция во внутреннее представление.

5.2.2 Схема использования эвристических вычислительных ветвей.

5.2.3 Механизм кластерных типов.

5.2.4 Функциональность решателей LGS.

5.3 Решатель систем нелинейных уравнений LGSEP.

5.4 Аспекты программной реализации в LEMO.

5.5 Конечно-пользовательские приложения решателей LGS.

5.5.1 Клиент-серверная технология FlashLGS и веб-приложение на ее основе.

5.5.2 Использование LGS 3D как вычислительного ядра САПР ADEM-VX.

5.5.3 Интеграция с САПР bCAD.

5.5.4 Другие примеры интеграции.

5.6 Экспериментальные результаты реализации предложенных методов.

5.6.1 Эффект от использования остовного моделирования.

5.6.2 Результаты реализации метода отделяющей декомпозиции.

5.6.3 Характеристики библиотеки вычислений элементарных функций.

5.6.4 Оценка эффективности решателя LGS в сравнении с другим решателем.

Системы автоматизированного проектирования (далее - САПР) по праву считаются одной из наиболее значимых для промышленности областей информатики. На протяжении многих лет они являются ключевыми компонентами процесса разработки изделий на современном предприятии [6]. Именно САПР позволяют выпускать продукты лучшего качества при более низкой себестоимости и за меньшее время [17]. В последние десять-пятнадцать лет в функциональном развитии и масштабировании систем автоматизированного проектирования достигнут серьезный прогресс. Были спроектированы полностью автоматизированным способом такие сложные устройства, как самолет Boeing 787 Dreamliner, множество различных моделей автомобилей, которые представляют собой механизмы с десятками и сотнями тысяч элементов. Кроме того, системы автоматизации проектирования развиваются и вширь, объединяясь с системами инженерного анализа, автоматизации производства и управления данными в единый комплекс управления жизненным циклом изделия (Product Lifecycle Management, или PLM) [15]. Долгое и интенсивное развитие САПР позволяет считать исследования в области их математических основ постоянно актуальными и практически важными.

Особый интерес представляют системы, обладающие возможностями параметризации модели, которая является мощным инструментом создания новых и переиспользования готовых моделей. Параметризация позволяет конструировать модели с заранее заданными характеристиками или модифицировать существующую модель путем изменения ее параметров. Наличие параметризации специалисты считают отличительной характеристикой наиболее совершенных САПР [16].

Далее будет рассматриваться широко востребованный класс параметрических задач, состоящий из задач определения положений деталей составной геометрической модели на плоскости или в пространстве. Для краткости такие задачи будут называться "задачи параметрического проектирования". Существует два классических типа параметрического проектирования: более традиционный иерархический, основанный на истории построения модели, и более совершенный по предоставляемым возможностям вариационный [33]. В настоящее время значительно более распространены САПР на основе истории построения модели [13].

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

Этот способ проще в реализации, но лишает пользователя многих возможностей, таких как размещение друг относительно друга двух объектов, уже вошедших в историю построения модели [14]. Это оказывается невозможным в силу образования циклов зависимостей между элементами и разрушения древовидной иерархической структуры. Если в модели имеются такие нетривиальные зависимости между элементами, то для ее описания нужен существенно другой подход [71]. Серьезным недостатком традиционного метода иерархического проектирования является и необходимость постоянно работать с полностью определенной геометрической моделью без внутренних степеней свободы, что ограничивает возможности ее редактирования [33].

На смену традиционному параметрическому подходу, основанному на истории построения модели, пришла концепция вариационного проектирования, которая заключается в выражении отношений между элементами и определяющими их параметрами посредством вариационных связей [4], или ограничений. Ограничение - это формальное декларативное описание произвольной связи между объектами модели, не предполагающее подчинения одного объекта другому [92]. Обычно ограничения классифицируются на логические геометрические (параллельность прямых, касание плоскости и цилиндра), параметрические геометрические (длина отрезка, радиус сферы, угол между гранями) и инженерные (площадь замкнутого контура, равенство параметров двух ограничений). С помощью задания ограничений пользователь может полностью управлять формой проектируемого изделия, при этом ему не надо просчитывать взаимное расположение частей модели - САПР автоматически определяет положения всех объектов, которые удовлетворяют всем заданным пользователем ограничениям [31].

Главным преимуществом вариационного подхода по сравнению с подходом, основанным на истории построения, являются значительно более высокие выразительные возможности системы. Конструктору модели не нужно полностью продумывать пошаговое создание изделия, а лишь задать желаемые свойства [25]. В любой момент можно добавлять и удалять ограничения или менять значения их параметров, после чего получать новую модель с заданными свойствами. Более совершенный механизм описания геометрической модели позволяет иметь дело с циклическими зависимостями [14] и не полностью определенными моделями [33]. Однако для поддержки всех этих возможностей необходимо уметь решать системы наложенных ограничений, или так называемую задачу вариационного проектирования. Для этого разрабатываются специальные решатели задач вариационного проектирования, или геометрические решатели.

Среди существующих сейчас на рынке сотен САПР лишь немногие системы предоставляют возможности вариационного проектирования, а еще меньшее количество САПР имеют собственный решатель, поскольку 6 реализация этой программной компоненты весьма трудоемка и наукоемка. Тем не менее, все современные крупномасштабные САПР, такие как CATIA, NX, Pro/E, SolidWorks, Solid Edge, Inventor, основаны именно на концепции вариационного проектирования, поскольку с ее помощью можно разрабатывать существенно более сложные изделия [53, 60]. Проблемы, которые порождает одновременное решение системы ограничений, можно решить с помощью разработки мощных методов решения задач вариационного проектирования [25, 49], что и является целью диссертационного исследования.

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

К сожалению, при всем обилии публикаций о практических применениях САПР и разработках САПР для конкретных прикладных областей [22, 29], в русскоязычной литературе очень скудно освещается вопрос о фундаментальных математических методах обработки параметрических задач. Если рассмотреть даже небольшое количество существующих русскоязычных публикаций о математических методах параметрического проектирования [20, 21, 26], среди них лишь считанное количество работ будет посвящены решению задач вариационного проектирования. Как правило, исследования посвящены иерархическому проектированию, задачам представления знаний [35] и различного рода гибридным методам для решения специальных классов задач. Обзор литературы позволяет сделать вывод, что в области общих задач вариационного проектирования нет сложившейся российской научной школы, есть лишь разрозненные исследования, недостаточно апробированные в промышленной практике. Тем не менее, все эти исследования выполнены недавно [8, 14], что позволяет надеяться на постепенное формирование этого направления как одного из значимых для отечественной науки в области САПР.

Объектами этого диссертационного исследования являются геометрические задачи параметрического проектирования и методы их решения. Термин "параметрическое проектирование" не вполне точен, так как охватывает и более широкую область иерархического проектирования, однако более корректный термин "вариационное проектирование" является значительно менее известным в русскоязычной литературе и имеет нежелательные ассоциации с вариационным исчислением. В иностранной литературе, как правило, вместо термина "геометрическая задача параметрического проектирования" применяется оборот "geometric constraint problem" [58], дословно переводимый как "задача в геометрических ограничениях". Тем не менее, этот термин не является достаточно устоявшимся, поэтому в данной работе автор будет придерживаться русскоязычной традиции [13].

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

Задачи, направленные на достижение указанной цели, включают:

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

• Разработку методов алгебраического моделирования таких задач;

• Исследование вопроса о корректной декомпозиции задач параметрического проектирования и создание корректных методов декомпозиции;

• Изучение применимости интервальных методов для решения задач параметрического проектирования;

• Эффективную программную реализацию предложенных алгоритмов в рамках решателей задач параметрического проектирования.

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

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

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

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

В пятой главе описывается комплекс созданных при участии автора программных систем, их архитектурные особенности и другие аспекты программной реализации. Излагается используемая в решателях LGS 2D и 3D схема работы вычислительных ветвей и механизм классификации задач параметрического проектирования по кластерным типам. Приводятся данные об интеграции разработанных геометрических решателей в различные программные продукты в области САПР. Далее излагаются экспериментальные результаты, показывающие эффективность разработанных автором и описанных в предыдущих главах методов решения задач параметрического проектирования, а также приводятся результаты сравнения решателя LGS с известным на рынке коммерческим геометрическим решателем.

Заключение

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

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

2) Разработан метод остовного моделирования, относящийся к классу алгебраических методов решения задач параметрического проектирования, позволяющий для решения этой задачи использовать систему уравнений с меньшим числом переменных и уравнений. Метод применим для широкого класса задач, является расширяемым и вычислительно эффективным. Он был разработан совместно с Руколеевым Е.В., наибольший вклад автором внесен в разработку алгоритмов построения остовного представления;

3) Проведены исследования в области интервальных методов решения задач параметрического проектирования, в том числе разработан подход к вычислению интервальных элементарных математических функций, основанный на разложении в ряды Чебышева и Тейлора с направленными округлениями. Работа выполнялась в сотрудничестве с Кашеваровой Т.П., при этом методы приведения аргумента в канонический интервал и схема контроля погрешности вычислений разработаны автором единолично;

4) Автором выполнен обзор исследований в области подходов к решению задач параметрического проектирования, произведена критика рассмотренных подходов, в том числе критика корректности известных методов геометрической декомпозиции. Выполнена математическая формализация понятия "задача параметрического проектирования", более строгая и общая, чем в опубликованных работах, учитывающая характер задач, встречающихся на практике. Также дано определение других понятий, ассоциированных с задачей параметрического проектирования.

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

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

2) В универсальном решателе систем уравнений с недоопределенными данными LEMO автор являлся, под руководством Семенова A.JI. и Важева И.В., разработчиком большого числа вычислительных методов, в том числе интервального метода бисекции и интервального метода Ньютона. Совместно с Петуниным Д.В. был реализован метод CP распространения ограничений;

3) В решателе двухмерных задач параметрического проектирования LGS 2D автор сначала выступал ответственным исполнителем под руководством Ушакова Д.М., а позднее - руководителем и архитектором. Автором была предложена и реализована идея метода отделяющей декомпозиции, после чего набор образцов для метода успешно увеличивался силами Рыкова И.А. Кроме этого, автор участвовал в разработке других методов LGS 2D, в том числе совместно с Еремченко А.А. реализовал и совершенствовал метод декомпозиции Хоффманна;

4) В геометрическом решателе трехмерных задач параметрического проектирования LGS 3D автор был руководителем и, совместно с Кусковым Р.Е., архитектором. Совместно с Руколеевым Е.В. был разработан и реализован метод остового моделирования, который в дальнейшем был усовершенствован Киселевым А.В.;

5) При разработке библиотеки вычисления элементарных математических функций с направленными округлениями Imath автор являлся единственным программистом-исполнителем.

К числу экспериментально проверяемых результатов, достигнутых автором, следует отнести:

1) разработку метода отделяющей декомпозиции, который многократно ускорил работу геометрических решателей на общей базе из 10 тысяч двухмерных и трехмерных тестов;

2) разработку метода остовного моделирования, который в 2 раза ускорил работу решателя на общей базе из 3 тысяч трехмерных тестов, и в два раза уменьшил число тестов, для которых LGS 3D не может найти решения;

3) разработку интервальной библиотеки вычисления элементарных функций с направленными округлениями на основе разложения в ряды Чебышева и Тейлора, производительность которой практически равна производительности стандартной библиотеки С++, результат вычислений является гарантированно корректным и в 80%-90% случаев неулучшаемым, а количество требуемой оперативной памяти составляет примерно 70 Кбайт.

1. Адамар Ж. Элементарная геометрия. - М., ОГИЗ, 1948. - 608 с.

2. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. М., Мир, 1987.-360 с.

3. Бухбергер Б., Калме Ж., Калтофен Э., Коллинз Дж., Лауэр М., Лафон Ж., Лоос Р., Минньотт М., Нойбюзер И., Норман А., Уинклер Ф., ван Хюльзен Я. Компьютерная алгебра. Символьные и алгебраические вычисления. -М., Мир, 1986 г.-392 с.

4. Голованов Н.Н. Геометрическое моделирование. М., издательство физико-математической литературы, 2002. - 472 с.

5. Горбатов В.А., Огиренко А.Г., Смирнов М.И. Искусственный интеллект в САПР: Учебное пособие. -М., МГГУ, 1994. 183 с.

6. Грувер М., Зиммерс Э. САПР и автоматизация производства. М., Мир, 1987.-528 с.

7. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М., Наука, 1990. - 384 с.

8. Еремченко А., Ершов А. Два новых метода декомпозиции задачи с геометрическими ограничениями // Препринт №11 Новосибирск, ЗАО ЛЕДАС, 2004.-36 с.

9. Ершов А. Гарантированно субоптимальные решения задач линейной оптимизации // Препринт №1 Новосибирск, ЗАО ЛЕДАС, 2002. - 20 с.

10. И.Ершов А. Новый метод моделирования задач параметрического проектирования // САПР и Графика. 2007. - №9. - С.32-35.

11. Клатте Р., Кулиш У., Неага М., Рац Д., Ульрих У. PASCAL-XSC. Язык численного программирования. -М., ДМК Пресс, 2000. -352 с.

12. И.Копорушкин П.А. Разработка структур данных и алгоритмов расчета параметрических моделей геометрических объектов : Автореф. дис. к-та тех. наук. Екатеринбург, 2005. - 22 с.

13. И.Копорушкин П.А., Партии А.С. Алгоритм расчета параметризованных геометрических объектов // Электронный журнал "ИССЛЕДОВАНО В РОССИИ". 2004. - С.184-197.

14. Кошелев В., Молочник В. Что такое PLM? // САПР и Графика. 2003. -№10.-С.34-37.

15. Кураксин С. А. Повышение эффективности проектирования изделий машиностроения на основе разработки автоматизированных методов и средств формирования параметрических сборочных моделей: Автореф. дис. к-та тех. наук. М., 1997. - 28 с.

16. Ли К. Основы САПР (CAD/CAM/CAE). СПб., Питер, 2004. - 559 с.

17. Лурье А.И. Аналитическая механика. М., Физматгиз, 1961. - 824 с.

18. Малюх В. Архитектура и базовые алгоритмы инструментального ядра графических САПР общего назначения: Дис. к-та физ.-мат. наук. -Новосибирск, 2006. 93 с.

19. Математическое и программное обеспечение САПР: Сб. науч. тр. / Под ред. В.К.Погребного; ТПУ Томск, 1997. - 262 с.

20. Математическое методы и модели в САПР: Сб. науч. тр. / Под ред. А.А.Калентьева; Самар. авиац. ин-т. Самара, 1991. - 145 с.

21. Моделирование интеллектуальных процессов проектирования и производства: Сб. науч. тр. / Под ред. А.Г.Ракович; Ин-т техн. кибернетики АН Беларуси. Минск, 1996. - 177 с.

22. Нариньяни А. С. Недоопределенные модели и операции с недоопределенными значениями // Препринт №400; АН СССР, Сиб. Отделение, ВЦ Новосибирск, 1982. - 33 с.

23. Нариньяни А.С. Недоопределенность в системах представления и обработки знаний // Известия АН СССР, серия "Теоретическая кибернетика". 1986. - №5. - С. 3-28.

24. Прейс С. LGS эффективный и доступный решатель геометрических задач // САПР и Графика. - 2003. - №9 - С. 48-50.

25. Программное обеспечение САПР: Сб. науч. тр. / Под редакцией И.Е.Педанова; ВЦ РАН. М., 1997 - 161 с.2 7. Ремез У.Я. Основы численных методов чебышевского приближения. -Киев, Наукова думка, 1969. 623 с.

26. Системы автоматизированного проектирования: ретроспективный библиографический указатель (1989-1993) / сост. Т.И. Кукуева. М., ГПНТБ РОССИИ, 1994. - 96 с.

27. Ушаков Д. М. Введение в математические основы САПР. Новосибирск, ЗАОЛЕДАС, 2006.-180 с.

28. Ушаков Д. М. Объектно-ориентированная среда для недоопределенных вычислений : Дис. к-та физ.-мат. наук. Новосибирск, 1998. - 160 с.

29. Ушаков Д. М. Технологии вариационного проектирования для разработки типичных приложений САПР http://plmnews.ru/11571.

30. Шалумов А.С., Багаев Д.В., Осипов А.С. Система автоматизированного проектирования КОМПАСС-График: Учебное пособие. Ковров, КГТА, 2003.-42 с.

31. Шестопал Ю.Т., Моисеев В.Б., Дорофеев В.Д. Основы интеллектуальных САПР-технологий. Пенза, Изд. ПГТУ, 1995. - 244 с.

32. Albajes L.S., Crosa Р.В. Geometric Relaxation for Solving Constraint-Based Models // Geometric Constraint Solving and Applications / Editors B. Bruderlin and D. Roller. Berlin, 1998. - P.259-270.

33. Becker Т., Kredel H., Weispfenning V. Grobner bases: a computational approach to commutative algebra. London, Springer-Verlag, 1993. - 574 p.

34. Bouma W., Fudos I., Hoffmann С. M. A Geometric Constraint Solver // Computer-Aided Design. 1995. - №27. - P.487-501.

35. Chiang C.-S., Joan-Arinyo R. Revisiting variable radius circles in constructive geometric constraint solving // Computer-Aided Geometric Design. 2004. -Vol. 21, Issue 4.-P.371-399.

36. Clement A., Riviere A., Serre P. New Technology for Solving Large-Scale Geometrical Networks // Int. Forum isiCAD : Proc / Conf. held at Novosibirsk, Russia, June 2004. Novosibirsk, 2004. - P. 11-20.

37. Dohmen M. A survey of constraint satisfaction techniques for geometric modeling // Computers and Graphics. 1995. - Vol. 19, №6. - P.831-845.

38. Dulmage A., Mendelsohn N. Coverings of Bipartite Graphs // Canad. J. Math. -1958.-Vol. 10.-P. 517-534.

39. Durand C., Hoffmann С. M. Variational Constraints in 3D // Int. Conf. on Shape Modeling and Applications: Proc / Conf. held at Aizu-Wakamatsu, Japan, March 1999. P.90-97.

40. Ershov A. Enchancing Techniques for Geometric Constraint Solving // Preprint №3 Novosibirsk, LEDAS Ltd., 2003. - 40 p.

41. Ershov A. G., Kashevarova T. P. Interval Mathematical Library Based on Chebyshev and Taylor Series Expansion // Reliable Computing. 2005. - Vol. 11, №5. -P.359-367.

42. Ershov A., Eremchenko A. Two New Decomposition Techniques in Geometric Constraint Solving // Int. Forum isiCAD: Proc / Conf. held at Novosibirsk, Russia, June 2004. Novosibirsk, 2004. -P.91-102.

43. Ershov A., Ivanov I., Kornienko V., Preis S., Rasskazov A., Rykov I. A new scheduling engine for PLM // Int. J. of Product Lifecycle Management. 2006. -Vol. 1,№ 2-P. 164-180.

44. Ershov A., Ivanov I., Kazakov A., Lipski S., Markin V., Preis S., Rukoleev E., Sidorov V., Ushakov D. LEDAS Geometric Solver: product overview // Preprint №5 Novosibirsk, LEDAS Ltd., 2003. - 56 p.

45. Ershov A., Ivanov I., Preis S., Rukoleev E., Ushakov D. LGS: Geometric Constraint Solver // Int. Conf. Perspectives of Systems Informatics, Novosibirsk, 2003. Berlin, 2003. - P.423-430. - (Lecture Notes in Computer Science, 2890).

46. Essert-Villard C., Schreck P., Dufourd J.-F. Sketch-based pruning of a solution space within a formal geometric constraint solver // Artificial Intelligence. -2000.-№124.-P.139-159.

47. Gao X.-S., Lin Q., Zhang G.-F. A C-tree decomposition algorithm for 2D and 3D geometric constraint solving // Computer-Aided Design. 2006. - №38. -P.l-13.

48. Heydon A., Nelson G. The Juno-2 Constraint-Based Drawing Editor : Research report 131a; Systems Research Center, Digital Equipment Corporation. Palo Alto, 1995.-19 p.

49. Hoffmann С. M. Constraint-Based Computer-Aided Design // J. of Computing and Information Science in Engineering. 2005. - Vol. 5, №3. - P. 182-187.

50. Hoffmann С. M. Robustness in Geometric Computations // J. of Computing and Information Science in Engineering. 2001. - Vol. 1, №2. - P.143-155.

51. Hoffmann С. M., Chiang C.-S. Variable-radius circles of cluster merging in geometric constraints: Part I. Translational clusters // Computer-Aided Design. 2002. - Vol. 34, №11. - P.787-797.

52. Hoffmann С. M., Chiang C.-S. Variable-radius circles of cluster merging in geometric constraints: Part II. Rotational clusters // Computer-Aided Design. -2002. Vol. 34, №11,- P.799-805.

53. Hoffmann С. M., Fudos I. Correctness Proof of a Geometric Constraint Solver // Int. J. of Computational Geometry and Application. 1996. - Vol. 6, №4. -P.405-420.

54. Hoffmann С. M., Joan-Arinyo R. A Brief on Constraint Solving // Computer-Aided Design and Applications. 2005. - Vol. 2, №. 5 - P.655-663.

55. Hoffmann С. M., Lomonosov A., Sitharam M. Geometric Constraint Decomposition // Geometric Constraint Solving and Applications / Editors B. Bruderlin and D. Roller. Berlin, 1998. - P.l 70-195.

56. Hoffmann С. M., Sitharam M., Yuana B. Making constraint solvers more usable: overconstraint problem // Computer-Aided Design. 2004. - Vol. 36, №4. -P.377-399.

57. Jafar J., Maher M. J. Constraint Logic Programming: A survey // J. of Logic Programming. -1994. Vol. 19/20 - P.503-581.

58. Jermann C., Trombettoni G., Neveu В., Mathis P. Decomposition of Geometric Constraint Systems: a Survey // Int. J. of Computational Geometry and Application.-2006.-Vol. 16, №5-6.-P.379-414.

59. Joan-Arinyo R., Luzon M.V., Soto A. Genetic algorithms for root multiselection in constructive geometric constraint solving // Computers and Graphics. -2003. Vol. 27, №1. -P.51-60.

60. Kim J., Kim K., Choi K., Lee J. Solving 3D Geometric Constraints for Assembly Modelling II Int. J. of Advanced Manufacturing Technology. 2000. -Vol. 16. - P.843-849.

61. Kim J., Kim K., Lee J., Jeong J. Generation of assembly models from kinematic constraints // Int. J. of Advanced Manufacturing Technology. 2005. - Vol. 26. -P.131-137.

62. Kim J., Kim K., Lee J., Jung H. Solving 3D geometric constraints for closed-loop assemblies // Int. J. of Advanced Manufacturing Technology. 2004. -Vol. 23. -P.755-761.

63. Klein R. The Role of Constraints in Geometric Modelling // Geometric Constraint Solving and Applications / Editors B. Bruderlin and D. Roller. -Berlin, 1998.-P.3-23.

64. Kramer G. A. A geometric constraint engine // Artificial Intelligence. 1992. -Vol. 58 -P.327-360.

65. Lamure H., Michelucci D. Qualitative Study of Geometric Constraints // Geometric Constraint Solving and Applications / Editors B. Bruderlin and D. Roller. Berlin, 1998. - P.234-258.

66. Lamure H., Michelucci D. Solving geometric constraint by homotopy // Third ACM Symposium on Solid modeling and applications: Proc. / Conf. held at Salt Lake City, USA. New York, USA, 1995. - p. 263-269.

67. Lee K.-Y., Kwon O-H., Lee J.-Y., Kim T.-W. A hybrid approach to geometric constraint solving with graph analysis and reduction // Advances in Engineering Software. -2003 Vol. 34.-P. 103-113.

68. Lhomme 0., Kuzo P., Mace P. Desargues: A Constraint-based system for 3D Projective Geometry // Geometric Constraint Solving and Applications / Editors B. Bruderlin and D. Roller. Berlin, 1998. - P.196-210.

69. Marriott K, Stuckey J. Programming with constraints: an introduction. -Cambridge, MIT, USA. 467 p.

70. Martinez M. L., Felez J. A constraint solver to define correctly dimensioned and overdimensioned parts // Computer-Aided Design. 2005. - Vol. 37. -P. 1353-1369.

71. Mathis P., Schreck P., Dufourd J.-F. YAMS: A Multi-Agent System for 2D Constraint Solving // Geometric Constraint Solving and Applications / Editors B. Bruderlin and D. Roller. Berlin, 1998. - P.211-233.

72. Michelucci D. The Next 100 Papers About Geometric Constraint Solving // Int. Forum isiCAD: Proc / Conf. held at Novosibirsk, Russia, June 2004. -Novosibirsk, 2004. P. 1-11.

73. Michelucci D., Foufou S. Using Cayley-Menger determinants for geometric constraint solving // Ninth ACM Symposium on Solid and Physical Modeling : Proc. / Conf. held at Genoa, Italy. Aire-la-Ville, Switzerland, 2004. - P.285-290.

74. Nahm Y., Ishikawa H. A new 3D-CAD system for set-based parametric design // Int. J. of Advanced Manufacturing Technology. 2006. - Vol. 29. - P. 137150.

75. Owen J. C. Algebraic Solution for Geometry from Geometrical Constraints // First ACM Symposium on Solid modeling foundations and CAD/CAM applications: Proc. / Conf. held at Austin, USA. New York, USA, 1991. -P.397-407.

76. Owen J. C. Constraint on simple geometry in two and three dimensions // Int. J. of Computational Geometry and Applications. 1996. - Vol.6, №4. - P.421-434.

77. Serre P., Ortuzar A., Riviere A. Non-cartesian modelling for analysis of the consistency of a geometric specification for conceptual design // Int. J. of Computational Geometry and Applications. 2006. - Vol.16, №5-6. - P.549-565.

78. Shi Z., Chen L. An angular constraints solving approach for assembly modeling based on spherical geometry // Int. J. of Advanced Manufacturing Technology. -2007.-Vol. 32. -P.366-377.

79. Shimizu S., Numao M. Constraint-based design for 3D shapes // Artificial Intelligence. 1997. - Vol. 91 -P.51-69.

80. Shpitalni M., LipsonH. Automatic Reasoning for Design Under Geometric Constraints // Annals of the CIRP. 1997. - Vol. 46, №1 - P.85-89.

81. Sitharam M., Oung J J., Zhou Y., Arbree A. Geometric constraints with feature hierarhies // Computer-Aided Design. 2006. - Vol. 38 - P.22-38.

82. Sitharam M., Arbree A., Zhou Y., Kohareswaran N. Solution space navigation for geometric constraint systems // ACM Transactions on Graphics 2006. -Vol. 25, №2.-P. 194-213.

83. Telerman V., Preis S., Snytnikov N., Ushakov D. Interval/set based collaborative engineering design // Int. J. of Product Lifecycle Management. -2006.-Vol. 1, №2. -P.150-163.

84. Ushakov D. Adding intelligence to software solutions for PLM: constraint-based approach // Int. J. of Product Lifecycle Management. 2006. - Vol. 1, №2-P.181-193.

85. Van der Meiden H. A., Bronsvoort W. F. A constructive approach to calculate parameter ranges for systems of geometric constraints // Computer-Aided Design. 2006. - Vol. 38. -P.275-283.

86. Veltkamp R. C., Arbabz F. Interactive Geometric Constraint Satisfaction : Technical report; Institute of Information and Computing Sciences, Utrecht University. Utrecht, 1996. - 24 p.

87. Wang Y., Chen L., Huang Z., Wu J., Zhong Y. A History-Independent Modelling-Oriented Approach to Solve Geometric Constraints Between Features in 3D Space // Int. J. of Advanced Manufacturing Technology. 2005. -Vol. 25. -P.334-342.