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

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

УДК 004.9

УПАКОВКА СЛОЖНЫХ ТРЁХМЕРНЫХ ОБЪЕКТОВ В ПРЯМОУГОЛЬНЫЙ КОНТЕЙНЕР НА БАЗЕ ДИСКРЕТНО-ЛОГИЧЕСКОГО

ПРЕДСТАВЛЕНИЯ ИНФОРМАЦИИ

© 2014 М.А. Верхотуров, Г.Н. Верхотурова, К.В. Данилов, Р.Р. Ягудин

Уфимский государственный авиационный технический университет

Поступила в редакцию 17.12.2013

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

1. ВВЕДЕНИЕ

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

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

Верхотуров Михаил Александрович, доктор технических наук, профессор кафедры вычислительной математики и кибернетики. E-mail: verhotur@vmk.ugatu.ac.ru. Верхотурова Галина Николаевна, кандидат технических наук, доцент кафедры вычислительной математики и кибернетики. E-mail: verhoturova.gn@yandex.ru Данилов Константин Витальевич, аспирант кафедры вычислительной математики и кибернетики. E-mail: rjycnl@gmail.com

Ягудин Рустем Расламович, кандидат технических наук. E-mail: gunboxer@gmail.com

2. ПОСТАНОВКА ЗАДАЧИ

Пусть имеется набор трехмерных геометрических объектов (ГО) T= {T1,T2,...,Tn}: Ti СR3,i = 1,n, каждый из которых задан в собственной системе координат.

Область размещения Q с R3 представляет собой прямоугольный параллелепипед с фиксированными длиной L, шириной Wи с переменной высотой H.

Пусть T (ui) геометрический объект Г, смещенный на вектор Ut.

Условия непересечения объектов между собой:

intT U )nintT; [u] ) = 0,\ Vi = 1 n,Vj = 1 n,i ф j,

где intT обозначает внутренние точки объекта T.

Условия нахождения геометрических объектов в зоне размещения:

T U )n Q = T U), Vi = in.

Условия (1) и (2) связывают параметры размещения U = (Ui,U2Ui) объектов множества Г в области Q и являются для них ограничениями.

Обозначим как H(T(U)) высоту зоны Q, необходимую для размещения геометрическихобъ-ектов множества T = {T1, T2,..., Tn} с векторами смещения U = {u1, u2,..., Un} .

Требуется найти такое U, чтобы H(T(U)) ^ min, при этом выполнялись условия взаимного расположения объектов между собой и с зоной размещения (1)-(2).

а) б) в)

Рис. 1. Постановка задачи размещения 3D объектов

3. ПОДХОДЫ К РЕШЕНИЮ ЗАДАЧИ

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

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

В этом случае используются методы "моделирования геометрических преобразований" [1].

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

1. Внешняя (оптимизационная) процедура -операции с приоритетным списком:

• формирование последовательности размещаемых объектов;

• изменение последовательности размещенных объектов.

2. Внутренняя (геометрическая) процедура - операции с объектами, соответствующими номерам в приоритетном списке:

• представление объектов в соответствующем виде (полигональном, воксельном и т.д.);

моделирование движения объектов;

• выбор, согласно некоторому критерию, точки размещения;

• занесение объекта в область (изменение области размещения).

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

Одним из наиболее применяемых методов реализации внутренней процедуры является подход, основанный на моделировании движения

объектов в области размещения с учетом их взаимного непересечения. Он базируется на понятии годографа вектор-функции плотного размещения (ГФПР) [1].

Годографом вектор-функции плотного размещения (ГФПР) G12 или G(T1(0), T2(u2)) подвижного объекта Г2(и2)относительно зафиксированного ^(Оказывается такое множество положений центра объекта Г , при котором он плотно расположен относительно объекта Г1.

Годограф G12подвижного объекта Г2(и2) относительно зафиксированного Г1(0) может быть определен через операции Минковского следующим образом:

С12 = Г/0) © -(Г2(и2)), где А © В = {а + Ь|а£ А, Ь£ В} - сумма Минковского множеств А и В.

3.1. Построение ГФПР размещаемого объекта относительно размещенных объектов и внешности области размещения

Существует несколько вариантов схемы построения ГФПР размещаемого объекта при упаковке [2]:

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

2. Интегральная. ГФПР размещаемого объекта и области рассчитывается с учетом того, что все ранее размещенные объекты считаются ее частью (рис. 2б).

3. Динамическая. Строятся ГФПР размещаемого объекта относительно каждого из уже упакованных и области упаковки. В каждом ГФПР определяется та часть, размещение упаковываемого объекта в которой удовлетворяет условиям упаковки (рис.2в).

а) б) в)

Рис. 2. Схемы построения ГФПР для плоского случая (очередной упаковываемый объект размещается в прямоугольную область, в которой размещены два треугольника): а - "предварительная"; б - интегральная; в - динамическая

круг

Особенности динамической схемы использования ГФПР[3]:

Пусть размещены первые (m - 1) объектов множества {T., T„..... T},

I 1' 2 ' ' n

(m - 1) <n. Выполняется размещение объекта T .

m

- Построение ГФПР объекта T относитель-

m

но зоны размещения и уже упакованных объектов производится в соответствии с приоритетным списком: K={Kn,..., K .}.

1 0 ' ' m-P

K0=Q, {K1 ,..., Km1} является, отсортированным в порядке увеличения высоты размещения, списком уже упакованных объектов {T1, ..., Tm-1}.

- При построении очередного ГФПР Gi(Ki, Tm) его точки {и} сразу же анализируются на допустимость.

Точка и. допустима если: _

ut g int Gj (Kj, Tm ), V j = 0, m - 1, j Ф i , при этом в случае, если параллелепипедные оболочки объектов T (и ) и K. не пересекаются, то

mv V ] Г

можно утверждать, что ut g int G (K , Tm ) без построения ГФПР G(K, T ).

] ] m/

- Если определено, что параметр размещения

и является допустимым, то для объектов {K}:

г ]

minZ(K]) >maxZ(Tm(u.)) ГФПР не строится.

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

Моделирование плотного движения упаковываемого объекта путём построения ГФПР зависит от выбранного пространства-объектного (непрерывного) или дискретного (аналог пространства изображения), при этом дискретно-логическое представление информации (ДЛПИ) позволяет строить ГФПР с различной точностью -R[1].

На базе дискретно-логического представления информации возможны различные варианты построения ГФПР, которые зависят от следующих характеристик^]:

• связность границ ГО (6-ти, 18-ти и 26-ти связные для З-О объектов);

• касание границ ГО и области упаковки ("плотное" и "неплотное");

• выбор направления движения ГО.

В данной работе для построения ГФПР было использовано дискретно-логическое представление объектов в виде 6-связных кодов и "неплотное" касание границ ГО и области упаковки.

3.2. Выбор направления движения ГО при построении ГФПР

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

• Метод анализа точек касания [1], при котором на каждом шаге определяется, каким образом размещаемый объект соприкасается с областью размещения и в зависимости от ситуаций выбирается направление движения. Данный метод подходит для непрерывного пространства, где объекты представлены в виде примитивов (полигоны, ребра, и т.д.), а также для случая "плотного" касания при дискретно-логическом способе представления информации.

• Правило "правой руки" - метод выбора направления движения при построении годографа в двухмерном пространстве. ГО движется вдоль границы (области размещенияили уже упакованных ГО) так, чтобы граница постоянно была с правой стороны. Таким образом, ГО никогда не отрывается от границы (все время с ней соприкасается). Этот метод применим для "неплотного" касания в дискретно-логическом пространстве.

Из рассмотренныхподходов был выбран метод "правой руки", который модифицирован для построения ГФПР в З-О пространстве (рис. 3).

УпаьлвываеыыЁ объект

Рис. 3. Построение ГФПР размещаемого объекта с использованием ДЛПИ

4. РЕЗУЛЬТАТЫ ВЫЧИСЛИТЕЛЬНОГО ЭКСПЕРИМЕНТА

Для оценки эффективности разработанного подхода были использованы наборы входных данных из статей Стояна Ю.Г.[4] и Ягудина Р.Р.[3]

Примеры №1-4. Задан набор из 20, 30, 40 и 50 многогранников соответственно, по 2 каждого типа. Основание зоны упаковки имеет ширину 30 и длину 35. Сравнение производилось по двум параметрам: время упаковки Т[с.] и ее плотность С[%].Результат - рис. 4.

Рис. 4. Сравнение эффективности алгоритмов для примеров №1-4

На рисунке видно, что практически во всех примерах плотность упаковки наилучшая у метода "Первый подходящий с упорядочиванием + ЛП" и "GRASP с ЛП" из [3]. Плотность упаковки объектов, полученная с помощью подхода, разработанного в данной работе, несколько ниже, т.к. была использована простейшая реализация "внешней" процедуры (оптимизации), однако при определенных параметрах точности он позволяет упаковать объекты быстрее.

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

На рис. 5 представлен пример карты упаковки деталей пистолета "Liberator", изготавливаемых на 3_Опринтере (было размещено два комплекта деталей).

5. ЗАКЛЮЧЕНИЕ

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

СПИСОК ЛИТЕРАТУРЫ

1. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя-упаковки геометрических объектов. Уфа. УГАТУ. 1998. 216 с.

2. Верхотурова Г.Н., Верхотуров М.А., Ягудин Р.Р. Об одном решении задачи плотной упаковки выпуклых многогранников на основе годографа функции плотного размещения / / Информационные системы и технологии. Серия Математическое и компьютерное моделирование. Орел: Изд-во ОрелГТу.

2012. № 4.С. 31-39.

3. Ягудин P.P. Решение задачи оптимизации упаковки многогранников в параллелепипедную область на основе построения годографа вектор-функции плотного размещения // Научно-технические ведомости. Санкт-Петербургский государственный политехнический университет. Системный анализ и управление. 2012. №5 (157). С.58-63.

4. Stoyan Yu, GilM., Scheithauer G., Pankratov A. Packing non-convex polytopes into a parallelepiped. TU Dresden, 2004. 32с.

THE 3D OBJECTS DENSE PACKING PROBLEM INTO A PARALLELEPIPED CONTAINER ON BASEDISKRETE-LOGICAL REPRESANTATION

© 2014 M.A. Verkhoturov, G.N. Verkhoturova, K.V. Danilov, R.R. Yagudin

Ufa State Aviation Technical University

The current work considers the problem of dense packing ofcomplex objects into a minimal height parallelepiped container. The no-fit polyhedron based algorithm is proposed to solve described task. This algorithm is based on discrete-logical represantation. Some examples and computational results are also given for public input data.

Keywords: packing, nesting, hodograph of dense allocation function, no-fit polyhedron, self-non-intersection conditions of polyhedrons, 3-D palletization problem, dense packing of three-dimensional objects.

Mikhail Verkhoturov, Doctor of Technics, Professor at the Computer Mathematics and Cybernetics Department. E-mail: verhotur@vmk.ugatu.ac.ru

Galina Verkhoturova, Candidate of Technics, Associate Professor at the Computer Mathematics and Cybernetics Department. E-mail: verhoturova.gn@yandex.ru Konstantin Danilov, Post-Graduate Student at the Computer Mathematics and Cybernetics Department. E-mail: rjycnl@gmail.com Rustem Yagudin, Candidate of Technics. E-mail: gunboxer@gmail.com