авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

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

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

Ершов Алексей Геннадьевич Алгоритмы и программные системы для геометрических задач параметрического проектирования Специальность 05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

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

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

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

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

доктор физико-математических наук Лаврентьев Михаил Михайлович кандидат физико-математических наук Кашеварова Тамара Петровна

Ведущая организация: Институт вычислительной математики и математической геофизики СО РАН.

Защита состоится 8 ноября 2007 в 14 ч. 30 мин. на заседании диссертационного совета К003.032.01 в Институте систем информатики имени А.П. Ершова Сибирского отделения РАН по адресу:

630090, Новосибирск, пр. Академика Лаврентьева, 6.

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

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

Ученый секретарь диссертационного совета К003.032.01 к.ф.-м.н. Мурзин Ф.А.

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

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

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

Тем самым, тема работы является актуальной и практически важной.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. На основе предложенных методов разработаны двухмерный геометрический решатель LGS 2D и трехмерный геометрический решатель LGS 3D. Эти решатели являются коммерчески востребованными программными продуктами и были успешно внедрены в несколько САПР, использующихся в отечественной и зарубежной промышленности;



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, Modeling and Computer Graphics» 2004;

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

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

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

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

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

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

• Masterwork, производитель Tecnos G.A. Srl., Италия;

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

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

Кроме того, клиент-серверное веб-приложение FlashLGS, созданное на базе LGS 2D, используется в образовательных целях в Новосибирском Государственном Техническом Университете.

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

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

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

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

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

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

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





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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определение. Общая постановка (на ЭВМ) задачи параметрического проектирования в d -мерном пространстве есть ~~ упорядоченная шестерка Z = (V, E, G, S 0, F, ), где ~ V = (V, P ) – структура объектов, состоящая из множества 1.

объектов V = V V, где V – множество из n d -мерных d * d * геометрических объектов, V – множество q вещественных переменных, и функции числа дополнительных параметров P : V N определяется общее число d P : V N. Через d дополнительных параметров p = P (v ) и функция числа v обобщенных координат C : V : для v V *, C (v ) = 1, для v V d, C (v) = P(v) + C 2d +1 = P(v) + d (d + 1) / 2 ;

~ E = ( E, a, A) – структура ограничений, состоящая из 2.

E U R i R – множества m ограничений над объектами из V, iN a:E функции арности и функции аргументов A : E N V {}. Каждое ограничение e E является вещественнозначной функцией, вычисляющей невязку,.. R ) [0, ) ;

C ( A ( e,1)) C ( A ( e, a ( e ))) e : (R G = {g1,.., g k } – множество k тел, i, g i V d и =V d, Ug 3. i i{1,.., k } причем i j g i I g j = ;

S 0 = { v1, s1,.., v n, s n }, {v1,.., vn } = V, 4. где si R C ( vi ) vi v j i j,, – начальное означивание объектов;

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

5.

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

6.

Множество положений объектов описывается с помощью набора трансформаций T = ((t1,.., t k ), ( 1,.., p + q )), состоящего из движений t1,.., t k тел задачи и приращений 1,.., p + q R ее переменных и дополнительных параметров объектов. Применение набора трансформаций к означиванию заключается в добавлении приращений к значениям переменных и дополнительных параметров, и выполнении движений тел, то есть применении движений к означиваниям координат содержащихся в телах объектов. Решением называется такой набор трансформаций, что при его применении к начальному означиванию получается означивание, в котором все ограничения имеют невязку, не большую. Оптимальным решением называется решение, конечное означивание которого не дальше от начального означивания в смысле функции F, чем конечные означивания всех других решений. Тем самым формализован основной объект исследования – задача параметрического проектирования.

В параграфе 1.3 вводится понятие число степеней свободы задачи параметрического проектирования с помощью формулы d ( Z ) = d ( g ) + p + q h(e), где p = P (v), q = card (V *), gG eE v h : E N - функция степеней свободы ограничений, d : G N функция количества независимых параметров, необходимых для описания движения тела в пространстве с точностью до автоморфизмов.

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

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

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

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

Вторая глава посвящена подходу к решению задач параметрического проектирования, заключающемуся в алгебраическом моделировании таких задач. Этот подход предполагает два направления исследований: разработку самого метода моделирования, переводящего ограничения в систему нелинейных алгебраических уравнений, и разработку методов решения получаемых систем уравнений. Изложение традиционного способа алгебраического моделирования – 6 параметрического декартова моделирования – дано в параграфе 2.1.

Параграф 2.2 представляет (для случая трехмерного пространства) новый метод остовного моделирования, разработанный на основе декартова моделирования. Параграф 2.3 представляет способ использования методов базиса Гребнера для решения систем полиномиальных уравнений в рамках геометрического решателя.

Новый метод остовного моделирования опирается на способ представления положения трехмерных тел, использующий меньше переменных, чем обычное представление 6-параметрической R t трансформацией T (,,, x, y, z ) =, где R = R o R o R t = ( x, y, z ) - вектор T композиция вращений вокруг координатных осей, смещений. Все положения тела g * относительно другого тела g, если между объектами этих двух тел v, w задано бинарное ограничение, как правило, можно описать формулой производного представления Tv ( p1,.., p m ) = X w o T ( p1,.., p m ) o C o ( X v0 ) 1, где X v0, X w C – положения объектов, – некоторая константная трансформация, называемая каноническим решением, а T ( p1,.., p m ) – параметрическая трансформация, описывающая все движения одного тела относительно другого, не нарушающие заданного ограничения, причем число параметров m меньше 6. С помощью производного представления по некоторому бинарному ограничению можно описать движения тела, не нарушающие этого ограничения, меньшим числом параметров, если:

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

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

• Представление положений параметризируемого тела в виде комбинаций вращений и смещений таково, что оно сводится к фиксированию нескольких параметров в T (,,, 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’ := {g from G | Degree(g)=C}, G* := {} While (G’ is non empty) do loop A g := G’.pop() If (CheckCutting(g,Mapping(g))) then do For each e from Mapping(g) do loop B If (Rem(e)=TRUE) continue Rem(e) := TRUE For each g’ from A(e) do loop C Degree(g’) := Degree(g’)- If (Degree(g’)=C) then do Reform(Mapping(g’),Rem) G'.push(g’) Endif End loop C End loop B G*.push(g) G.pop(g) Endif End loop A В этом псевдокоде, работающем на гиперграфе, вершинами которого являются тела, а гиперребрами – ограничения, используются следующие структуры данных: E – множество гиперребер, G – множество вершин, Rem – булевы пометки гиперребер, Degree – степени вершин, A – массивы инцидентных конкретному гиперребру вершин, Mapping – массивы инцидентных конкретной вершине гиперребер, G’ – стек активных вершин, G* готовая последовательность корректно отделяемых вершин-тел. Константа C C 2 +1, d d равна где – размерность пространства. Функция CheckCutting выполняет проверку соответствия тела корректным V образцам из заранее заданного списка за константное время, общее время работы алгоритма отделяющей декомпозиции линейно, причем его результат (множество G*) не зависит от порядка отделения тел.

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

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

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

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

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

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

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

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

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

В интервалах, на которых колебание f (x) превышает колебание 2.

x f (x), вычисляется разложение Чебышева функции x f (x) ;

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

3.

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

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

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

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

Пятая глава посвящается аспектам программной реализации и практического использования разработанных методов. В параграфе 5. перечисляются программные компоненты, реализованные при работе над диссертацией: LEMO – универсальный решатель задач с недоопределенными данными, LGSEP – решатель систем нелинейных уравнений, LGS 2D и 3D – решатели двух- и трехмерных задач параметрического проектирования, Imath – библиотека вычисления интервальных функций с направленными округлениями. Параграф 5. посвящен архитектуре реализованных под руководством автора геометрических решателей LGS 2D и 3D, в том числе механизму вычислительных ветвей и схеме классификации задач для решения их специализированными методами. Параграф 5.3 излагает аспекты реализации решателя систем нелинейных уравнений LGSEP, а параграф 5.4 – решателя LEMO, в частности, оптимизацию работы метода бисекции. Параграф 5.5 повествует об интеграции решателей LGS в конечно-пользовательские приложения, в т.ч. САПР. Параграф 5. посвящен оценке экспериментальных результатов от реализации предложенных автором теоретических методов.

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

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

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

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

Результаты от внедрения метода остовного моделирования в существующую схему вычислительных ветвей решателя LGS 3D на той же базе:

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

2. Уменьшилось в два раза число не решаемых LGS 3D тестов.

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

1. Общее время решения двухмерных задач уменьшилось в 24.8 раз;

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

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

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

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

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

При внедрении решателя LGS 3D в одну из промышленных САПР было проведено его сравнение с ранее использовавшимся коммерческим решателем. На базе из 3120 индустриальных трехмерных тестов были получены такие результаты:

1. Количество тестов, успешно решаемых LGS 3D, составило 99.29% против 83.17% у ранее используемого решателя;

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

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

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

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

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

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

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

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

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

2. Семенов А. Л., Важев И. В., Кашеварова Т.П., Бревнов Е.В., Ершов А.Г., Клейменов А.Е., Лещенко А.С., Лоенко М.Ю., Петунин Д.В.

Интервальные методы распространения ограничений и их приложения: Cборник научных трудов “Системная Информатика” №9;

Институт систем информатики СО РАН. – Новосибирск, 2004. – С.245-358.

3. Ershov A., Eremchenko A. Two New Decomposition Techniques in 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. Enchancing Techniques for Geometric Constraint Solving // Preprint №3 – Novosibirsk, LEDAS Ltd., 2003. – 40 p.

8. 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.

Ершов А.Г.

АЛГОРИТМЫ И ПРОГРАММНЫЕ СИСТЕМЫ ДЛЯ ГЕОМЕТРИЧЕСКИХ ЗАДАЧ ПАРАМЕТРИЧЕСКОГО ПРОЕКТИРОВАНИЯ Автореферат Подписано в печать 27.09.2007 Объем 1,0 уч.-изд. л.

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

Отпечатано в ЗАО РИЦ «Прайс-курьер» 630090, г. Новосибирск, пр. Ак. Лаврентьева, 6, тел. 330-72- Заказ №

 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.