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

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

Ньи Ньи Хтун

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

Специальность 05.01.01 "Инженерная геометрия и компьютерная графика''

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

2- ПАП ¿014

005549215

Москва - 2014

005549215

Работа выполнена в Московском авиационном институте (национальном исследовательском университете) на кафедре «Инженерная графика»

Научный руководитель:

кандидат технических наук, профессор Маркин Леонид Владимирович

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

Клименко Станислав Владимирович, доктор физико-математических наук, профессор, генеральный директор Института физико-технической информатики, Протвино; профессор кафедры физико-технической информатики МФТИ.

Бодрышев Антон Валерьевич, кандидат технических наук, генеральный директор ООО "ПРОМАИТИ"

Ведущая организация: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Нижегородский государственный архитектурно-строительный университет" (ННГАСУ). 603950, Россия, г. Нижний Новгород, ул. Ильинская, д. 65

Защита состоится « 30 » июня 2014 г. в 11.00 часов на заседании диссертационного совета Д 212.125.13 при ФГБОУ ВПО «Московский авиационный институт (национальный исследовательский университет)» по адресу: 125993, г. Москва, А-80, ГСП-3, Волоколамское шоссе, д.4, главный административный корпус, зал заседаний ученого совета.

С диссертацией можно ознакомиться в научной библиотеке ФГБОУ ВПО «Московский авиационный институт (национальный исследовательский университет)» и на сайте организации http://mai.ru/events/defence/

Автореферат разослан

мая 2014 г.

Ученый секретарь

диссертационного совета Д 212.125.13, доктор технических наук, профессор _

В.И. Бирюков

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

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

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

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

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

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

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

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

1. Разработку геометрических моделей проектирования соединительных трасс как размещаемых объектов среди уже размещенных с учетом дополнительных конструктивных и технологических требований (заданных точек входа и выхода трассы, заданных поперечных сечений или закона их изменения, заданного минимального радиуса кривизны трассы и заданного минимального расстояния прохождения трассы от уже размещенных объектов).

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

3. Исследование и верификацию разработанных геометрических моделей.

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

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

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

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

3. Показана невозможность использования даже лучших известных алгоритмов дискретной трассировки (алгоритма Дейкст-ры и алгоритма А*) для автоматизации трассировки каналовых поверхностей.

4. Разработана геометрическая модель и алгоритм построения главной направляющей линии (ГНЛ) каналовой поверхности для плоской и пространственной трассы, являющийся глубокой модернизацией алгоритма А* и устраняющий основные ограничения прототипа А* - возможность прокладки плавных трасс на заданных расстояниях от областей запрета.

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

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

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

8. Проведена верификация предложенной геометрической модели - оценка точности представления телесной трассы рецептор-ной матрицей и оценка производительности реализации предложенного рецепторного алгоритма.

9. Проведено с помощью предложенного метода трассировки исследование возможности прокладки воздуховода в моторном отсеке легкого самолета "АСА-2". Результаты исследования также

внедрены в учебный процесс кафедры инженерной графики МАИ.

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

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

• Провести исследование, верификацию и тестирование разработанного алгоритмического и программного обеспечения;

• Внедрить разработанное алгоритмическое и программное обеспечение в практику проектных исследований на легком самолета "АСА-2" и в учебный процесс МАИ;

• Наметить пути совершенствования разработанного алгоритмического и программного обеспечения в существующие CAD системы как автономного расчетного модуля.

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

Методологические и теоретические основы исследования основаны на фундаментальных трудах в области:

• общих принципов геометрического моделирования;

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

• общей методики автоматизации проектирования;

• методов автоматизации проектирования авиационной техники;

• методов автоматизированного проектирования трасс простейшей формы между уже скомпонованными объектами;

• методов автоматизации компоновочных работ;

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

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

• методов дискретного моделирования геометрических объектов.

Положения, выносимые на защиту:

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

2. Алгоритм, реализующий геометрическую модель телесной трассировки с использованием дискретной модели пространства (рецепторной модели).

3. Архитектуру и программную реализацию алгоритма телесной трассировки, запрограммированную на языке Microsoft С#, обеспечивающую получение компоновочных решений и их визуализацию.

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

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

Апробация результатов диссертации. Основные положения диссертационной работы докладывались и обсуждались на 8 международных и общероссийских научно-технических и научно-практических конференциях.

Содержание диссертационной работы отражено в 11 печатных работах, в том числе в 3-х периодических изданиях, рекомендованных ВАК.

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

ставляет 178 страниц., включая 95 рисунок и 7 таблиц. Список литературы включает 255 наименований, в том числе 45 на иностранных языках.

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

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

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

б) каналовая поверхность, построенная по нормальным

каналовой поверхности по заданным плоскостям параллелизма (а) и по нормальным сечениям (б)

Рисунок 1 — Проектирование

сечениям

В этой главе был проведен анализ исследований в области геометрического моделирования каналовых поверхностей, выполненных в первую очередь проф. Осиповым В.А. и его учениками -Андреевым В.А., Зелевым В.П., Лелюшенко С.И., Мезенцевым Л.Г., Поликарповым Ю.В., Миролюбовой Т.И., Давыдовым Ю.В., Егоровым Э.В. а так же другими исследователями московской и общероссийской геометрической школы - Александровичем В.П., Дёминой B.Ä., Ивановым Г.С., Кулишом A.C., Хасановым В.Х., Найдышем В.М. и др., а также представителями Киевской научной школы прикладной геометрии - труды Блиока A.B., Василевского О.В., Грибова С.М., Дорошенко Ю.А., Кожушко, Пилипаки С.Ф., Радзивилловича В.В., Обуховой B.C., Скидана И.А. и др. Проведенный анализ показал невозможность прямого использования описанных методов проектирования для решения поставленной задачи.

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

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

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

• Возможность на основе данной модели генерировать алгоритмы рационального размещения объекта в пространстве.

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

В главе 1 проведен анализ трудов отечественных и зарубежных ученых в этой области. Однако даже эти методы проектирования и компьютерного моделирования анализируют лишь существующую конструкцию. Прежде всего это проверка условия непересечения в уже сгенерированной проектантом компоновке внутренними средствами системы геометрического моделирования (СГМ) одной из систем (КОМПАС, SolidWorks, Catia и др.), которые выступают лишь в качестве инструментального средства анализа уже готового технического решения, основанного лишь на опыте и интуиции проектанта.

В главе 1 проанализованы методы и геометрические модели (в том числе эвристические), учитывающие специфику автоматизации решения именно компоновочных задач (как для 2D, так и для 3D случаев), разработанные в фундаментальных трудах отечественных ученых - акад. Рвачева В.Л. и профессоров Гаврилова В.Н., Мухачевой Э.А., Стояна Ю.Г., Гиля H.H., Маркина JI.B. и других, а также зарубежных ученых Bortfeldt A., Cagan J., George J.A., Gilmore P.C., Lim A., Lodi A., Martello S., Pisinger D., Robinson D. F., Saaty T. L., Szykman S., Vigo D. и др. Несмотря на значительное количество исследований в этой области проведенный в главе 1 анализ показал, что решены лишь отдельные, частные задачи автоматизированной компоновки.

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

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

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

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

Имеется прямоугольная область размерами X х 7, в которой расположены области запрета. Задана точка входа А и точка выхода В канала (рисунок 2). Необходимо провести трассу между заданными начальной и конечной точками А и В. Поскольку мы не наложили никаких ограничений на прохождение трассы, возможно достаточно много вариантов ее прохождения. Учитывая нашу транспортную специфику проектирования техники, очевидно, что из всех трасс на рисунке 2а лучше будет та, которая короче, т.к. при прохождении жидкости или газа по каналу неизбежны гидравлические потери или гидравлическое сопротивление — безвозвратные потери удельной энергии, обусловленные наличием вязкого трения.

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

Усложним задачу проектирования. Будем считать, что наша трасса должны быть не бесконечно тонкой, как на рисунке 2а, и иметь вполне конкретные физические размеры, т.е. являться кана-ловым объектом. В простейшем случае это цилиндрический канал постоянного радиуса К (рисунок 26), в более сложном - канал переменного сечения (рисунок 2в).

а) б) в)

Рисунок 2 — Иллюстрация физической постановки задачи исследования: а -нахождение рационального пути между двумя конечными точками А и В в 2Б постановке; б - канал постоянного сечения; в - канал переменного сечения

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

Пусть имеется N компонуемых объектов Г, 0=1, ... , Ы) и область размещения Г2. Требуется разместить эти объекты с учетом заданных ограничений в области О таким образом, чтобы функция цели компоновки Ф (X) достигала экстремума, т.е. определить

Ех1г Ф (X) при X с: О

где X -некоторая переменная, определяющая параметры размещения.

Таким образом, математическая постановка задачи размещения включает 3 компонента:

1) Выбор функции цели Ф (X).

2) Выбор переменной X.

3) Выбор и формализация ограничений.

Очевидно, что в геометрическом плане основным критерием оптимизации размещения является оптимизация коэффициента заполнения пространства Ку . Коэффициент Ку (иногда его называют коэффициентом плотности компоновки) представляет собой

12

отношение

п

Ку = Z-V KMJ V отс п г=!

rneSF К.О. - сумма объемов п скомпонованных объектов,

л/ /=l

у отс,- объем отсека, в котором производится компоновка.

Условие максимальной плотности компоновки записывается в виде выражения

Extr. Ф (X) при Хс Q (1)

L,£—>min

Kv-> 1

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

- обеспечивала бы условия взаимного непересечения с уже скомпонованными объектами и другими областями запрета;

- имела бы минимально возможную в данных условиях суммарную протяженность трассы Lz (что снизит ее гидравлическое сопротивление и массу);

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

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

Такие задачи трассировки решены в работах проф. Ю.Г.Стояна и его учеников - Смелякова C.B., Аристовой И.В. Однако в этих работах задача трассировки может быть сведена к задаче поиска минимального пути трассы по манхеттеновой метри-

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

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

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

Г 1, если рецептор возбужден, 10, если рецептор не возбужден

Рецептор считается невозбужденным, если через него не проходит граница объекта и он не принадлежит внутренней области (рисунок 3а). Трехмерные объекты описываются трехмерной матрицей А = {а^к} размерностью тхпхр (рисунок 36).

т

а) б)

Рисунок 3 - Рецепторная модель 2Б-тела (а) и SD-тела (б)

Такой метод геометрического моделирования был предложен в начале 70-х годов прошлого века белорусским ученым Зо-зулевичем Д.М., но в те он годы не получил распространения из ограниченных возможностей ЭВМ по памяти и быстродействию. В дальнейшем, в связи с развитием производительности вычислительной техники, рецепторные геометрические модели нашли свое практическое применение. Исследование и разработка рецептор-ных геометрических моделей для различных случаев применения была проведена в работах отечественных ученых Горелика А.Г., Герасименко Е.П., Клишина В.В., Корн Г.В., Рогозы Ю.А., Пащенко О.Б., Толока A.B., Ситу Лина, а также ряда иностранных авторов - Гаргантини И. (Gargantini I.), Реквишы А.А.Г., (Requcha A.A.G. ) и ряда других. Здесь же следует отметить очень близкие по идеологии исследования Наджарова K.M., Роткова С.И. и др., в которых в качестве элементарного объекта формы выступает не классический рецептор в виде куба или параллелепипеда, а более сложные фигуры - например гексоэксаэдр.

Большим преимуществом рецепторного подхода является легкость обнаружения препятствия по коду рецептора (0 или 1). Наипростейшим подходом к проблеме обхода препятствия является игнорирование этого препятствий до столкновения с ними. Такой алгоритм проектирования трассы будет выглядеть так: выбрать направление для движения к цели и двигаться по нему, пока цель не достигнута и направление свободно для движения (рисунок 4).

Особенностью подхода к разработке методов и алгоритмов проектирования трасс с использованием рецепторных моделей в

данной диссертации является то, что проектирование трассы рассматривается как задача искусственного интеллекта (ИИ).

Структура выбора направления движения определяется правилом: двигаться туда иначе

выбрать другое направление в соответствии со стратегией обхода.

Это позволяет утверждать, что в этих алгоритмах заложены элементы искусственного интеллекта (ИИ), так как решение выбирается по предикативному принципу "Если" - "То". В работах Дейкстры (Dijkstra, Е. W.), Дональда Эрвина Кнута (Donald Ervin Knuth), Томаса Кормена (Thomas H. Cormen), Чарльза Лейзерсона (Charles Leiserson) и др. проанализированы различные стратегии обхода препятствий (эвристики), основанные как на случайном поиске, так и на алгоритмах искусственного интеллекта. Каждый из них имеет как свои ограничения, так и области предпочтительного применения.

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

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

Рисунок 4 — Принцип обхода препятствий при построении канало-вой поверхности рецепторным методом

2. Нет способов, позволяющих строить прохождение трассы на заданном расстоянии от областей запрета (т.е. соблюдения д -окрестности).

3. В настоящем виде алгоритмы Дейкстры и А* не способны учитывать заданные изменения площади или объема трассы по мере движения по ней.

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

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

Разработанный нами алгоритм трассировки сглаженного пути является глубокой модифицикацией алгоритма А* и предусматривает выполнение следующих основных действий:

- Ввод параметров трассы для обеспечения заданной цели -телесной трассировки.

- Улучшение алгоритма А* вводом в него дополнительно разработанного нами компонента - «Штрафов за смену направления». В этом компоненте стоимость пути возрастает всякий раз, когда путь меняет направление, то есть образуется угол. В результате, если путь найден, он будет более гладким, так как исключаются «зигзаги» и трасса становится более плавной. Недостатком применения этого метода является то, что время расчета увеличивается, так как приходится искать дополнительные узлы.

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

сглаживания манхеттеновой траектории (для наглядности в 20) показан на рисунке 5.

Другим важнейшим вопросом, определяющим эффективность функционирование нашего алгоритма, является выбор направления поиска, также определяемый эвристическими методами. Обычно алгоритмы поиска пути ведут поиск в 4 и 8 направлениях (в 2Э или ЗО случаях). В нашем же алго-Рисунок 5 - Сглаживание манхет- ритме для поиска пути в ЗЭ теновой траектории с учетом за- используется МНогонаправ-данного ктш с использованием раз- _

работанного алгоритма ленный выбор направления,

показанный на рисунке 6а. Иллюстрация этих направлений поиска в рецепторной матрице в пространственном изображении приведена на рисунке 66.

а) б)

Рисунок 6 - Поиск пути в рецепторном поле в ЗВ изображении: а - по 26-и смежным вершинам; г - проектирование прохождения каналовой поверхности

Существенной проблемой при проектировании каналовой поверхности рецепторным методом является переход от нахождения главной направляющей линии (ГНЛ) в плоскости к простран-

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

1. Вычисляются первые и вторые производные по параметру длины Р вдоль ГНЛ s: xf, х", у', у", z\ z".

2. Вычисляется кривизна К по формуле:

3. Определяются направляющие косинусы касательной t :

cos ai-x'; cos fii=y'; cos yi—z'.

4. Определяются направляющие косинусы главной нормали

1 » 1 „ 1 »

cosor2 =—х; cos/?2 = —у; cos/2 = — z.

Вычисленные таким образом направляющие косинусы позволяют определить положение плоскостей ГНЛ прохождения канала. Эта задача несколько упрощается тем, алгоритм построения 3D трассы основан на чередовании прямых и дуг, расположенных в плоскостях, положение которых в пространстве вычисляется ранее описанными методами.

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

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

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

что минимально необходимое количество оперативной памяти составляет 13 байт для каждого рецептора. Потребное количество оперативной памяти приведено в таблице 1.

Рисунок 7 - Структура компонентов основного алгоритма проектирования трассы

Таблица 1 — Необходимое количество оперативной памяти для 20 и ЗО

№ Количество рецепторов Размер оперативной памяти (при расчете рецепторов в 2Б матрице) Размер оперативной памяти (при расчете рецепторов в ЗБ матрице)

1 1024x1024 13 Мб 953.67 Мб

2 512x512 3.2 Мб 128 Мб

3 256x256 832 Кб 16 Мб

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

В главе 4 описаны главные улучшения, внесенные нами в известный алгоритм трассировки:

1. Генерация переключателя выбора направления поиска;

2. Штраф за смену направления;

3. Пересмотр закрытых узлов;

4. Новая эвристика;

5. Изменение размера рецептора.

Для реализации предложенного алгоритма трассировки была написана программа Advanced Pathfinder System (APS) в Microsoft Visual Studio 2010, используя язык программирования C#. На рисунке 8а показан интерфейс разработанной нами программы Advanced Pathfinder System (APS), которую можно использовать на двух языках - английском и русском. На рисунке 8б показан пример построения плавной телесной трассы.

а) б)

Рисунок 8 - Интерфейс разработанной нами программы Advanced Pathfinder System (APS) {а), пример построения плавной пространственной телесной трассы (б)

В этой же главе проведено исследование и верификация алгоритма и программы телесной трассировки. В частности, проведен сравнительный анализ характеристик разработанного алгоритма с наиболее близким по используемым приемам рецептор-ным алгоритмом А* Масамото Канехары, разработанным для формирования рациональных движений робота-манипулятора.

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

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

а 3,0

2,0

1.0

\ 1 1 \ Время вычислений VIII

Погрешность модели 41 1

г^Ч Т.......* ^.......J

1,0 2,0 3,0 4,0 Размер рецептора мм

б)

Рисунок 9 - Результаты теста погрешности (а) и скорости (б)для конкретного примера компоновки

Анализ результатов этого исследования показывает, что точность описания геометрической формы ожидаемо зависит от размера рецептора й, т. е. с увеличением д погрешность описания формы растет по примерно линейной зависимости и ее математической ожидание составляет примерно 0,9 й ±0,28^ при доверительном интервале ±Зо.

Примеры практического использования предложенного алгоритма и программного обеспечения при разработке проектных решений модификации легкого самолета "АСА-2" приведены на рисунках 10а. Для оценки эффективности разработанной в рамках диссертации геометрической модели также использовался метод имитационного моделирования определенной тестовой компоновочной ситуации в рецепторной матрице размерностью 1 м х 1 м х 1 м. В сцене, в которой были размещены несколько уже вроде бы скомпонованных объектов, подготовленному пользователю предлагалось с использованием конкретной САЭ-системы (использовалась ЗоНбХУогкв 2012) смоделировать трассу заданного сечения между двумя точками (начальной и конечной) с заданными коор-

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

10,0 8,0 6,0

х

5

| 4,0

А СО

¡2,0

* Обход трассой 10 объектов ■

• Обход трассой 10 объектов •

■ Обход трассой 5 абьектов

_ Обход трассой 20 объектов .

Обход трассой 10 объектоо

Обход трассой 5 объектов

- 1*,!*: Ф

0,2 074 03 Размер рецептора с^ь^ixd

О^В

1,0

а) б)

Рисунок 10 — Использование предложенного метода при компоновке легкого самолета "АСА-2" (а) и результаты имитационного моделирования затрат времени на построение трассы пользователем в интерактивном режиме и алгоритмом в автоматическом (б)

Результаты данного исследования также использованы в учебном процессе МАИ в курсе для Центра повышения квалификации преподавателей и курса для аспирантов.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ ПО РАБОТЕ

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

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

3. Показана невозможность использования даже лучших известных алгоритмов дискретной трассировки (алгоритма Дейкстры и алгоритма Масатомо Канехары А*) для автоматизации трассировки каналовых поверхностей.

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

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

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

7. Модификации предложенного алгоритма трассировки и оптимизация его информационной структуры позволила увеличить быстродействие программы по сравнению с ближайшими аналогами (алгоритмами Дейкстры и А*) в 300 -1200 раз.

8. Проведенная оценка точности представления телесной трассы рецепторной матрицей показала на тестовых примерах, что погрешность представления зависит от размера рецептора d и составляет примерно 0,9й? ± 0,28d при доверительном интервале ±3ст.

9. Проведенная оценка производительности реализации предложенного рецепторного алгоритма показала, что процессорное время расчета компоновки возрастает примерно по параболической зависимости от количества рецепторов на единице длины рецепторной матрицы и в тестовых примерах составляет от 0,05 до 1.8 секунды.

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

на расчетном этапе скорость проектирования каналовой поверхности по сравнению с использованием CAD-системы в интерактивном режиме в десятки и сотни раз (в зависимости от заданной точности), обеспечивая при этом заданные параметры проектирования.

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

Работы автора по теме диссертации

В изданиях, рекомендованных ВАК РФ:

1. Хтун Н. Н., Ситу JI., Маркин JI. В. Рецепторные геометрические модели в задачах автоматизированной компоновки технического отсека легкого самолета // Труды МАИ, электр. журнал (http://www.mai.ru), вып. №47,2011 г.

URL: http://www.mai.ru/ science/trudy/published.php

2. Хтун Н. Н., Тайк Ч., Маркин JI. В. Исследование алгоритмов использования рецепторных геометрических моделей в задачах телесной трассировки авиационной техники // Труды МАИ, электр. журнал (http://www.mai.ru), вып. №69, 2013 г.

URL: http://www.mai.ru/science/trudy/published.php

3.Хтун Н. Н., Маркин Л. В., Соседко A.A. Применение рецепторных геометрических моделей в задачах автоматизированной компоновки авиационной техники // Труды МАИ, электр. журнал (http://www.mai.ru), вып. №72, 2014 г.

URL: http://www.mai.ru/science/trudy/published.php

В других изданиях:

1.Ньи Ньи Хтун. Улучшенный алгоритм трассировки пути, основанный на рецепторном методе // В сб.: Тез. докл научно -практическая конференция студентов и молодых учёных МАИ «Инновации в авиации и космонавтике — 2010 ». Тезисы докладов. - М.: Изд-во МАИ. - 2010. - С.108.

2. Ньи Ньи Хтун. Использование рецепторных моделей в задачах трассировки // В сб.: Тез. докл. «Технологии Microsoft в теории и практике программирования: труды VII Всероссийской конференции студентов, аспирантов и молодых учёных». - М.: Изд-во Вузовская книга - МАИ. - 2010. - С.85 -86.

3.Ньи Ньи Хтун. Алгоритмы задач трассировки на основе рецепторных геометрических моделей // В сб.: Тез. докл. 9-я Международная конференция «Авиация и космонавтика - 2010 ». - М.: Изд-во МАИ. - 2010 . - С.314-315.

4. Ньи Ньи Хтун. Дискретные моделей телесной трассировки // В сб.: Тез. докл (Научно-практическая конференция студентов и молодых учёных МАИ «Инновации в авиации и космонавтике -2011 ») . -М.: Изд-во МЭЙЛЕР. С.190-191

5. Ньи Ньи Хтун. Использование рецепторного метода для проектирования каналовых поверхностей // в сб.: Тез. докл научно

- практическая конференция студентов и молодых учёных МАИ «Инновации в авиации и космонавтике - 2012 ». Тезисы докладов.

- М.: Изд-во МАИ. - 2012. - С.256.

6. Ньи Ньи Хтун. Исследование рецепторного метода проектирования каналовых поверхностей в задачах компоновки авиатехники // В сб.: Тез. докл. 11-я Международная конференция «Авиация и космонавтика - 2012 ». - М.: Изд-во МАИ. - 2012 . - С.298-299.

7.Nyi Nyi Htun. Finding the shortest smooth path in variable size using improved A* algorithm on grid-based receptor model // В сб.: Тез. докл. 11-я Международная конференция ICCA 2013 (http://www.ucsy.edu.mm/ucsy/635558k.do) « 11th International Conference On Computer Applications - 2013, Yangon, Myanmar ». - M.: Изд-во UCSY. - 2013 . - С.255-260.

8. Ньи Ньи Хтун. Использование рецепторных геометрических моделей в задачах телесной трассировки // В сб.: Тез. докл. «Международного конкурса научных работ по приоритетным направлениям развития науки, технологий и техники в Российской Федерации., МГТУ им. Н.Э.Баумана». -М.: Изд-во НИИ , 2012. С.146 -147.

Множительный центр МАИ (НИУ) Заказ otö5" O5"201'V г. Тираж jOChкз.