---
id: ASP-overview
title: 'Планирование последовательности сборки'
---

## Введение

Сборка - узкое место в жизненном цикле многих продуктов. Предполагаемое время сборки занимает 20-50 % от общего времени производства, в то время как стоимость сборки составляет около 20-30 % от общей стоимости (Xu et al., 2012). Планирование последовательности сборки имеет решающее значение для обеспечения успеха продукта, особенно для сложных продуктов, таких как автомобили, корабли и аэрокосмическая продукция (Hou et al., 2018).

В данной статье рассмотрены актуальные исследования по автоматическому планированию последовательности сборки (Assembly Sequence Planning, ASP).

## Основные методы

На базе статьи __A review on assembly sequence generation and its automation__ - Bahubalendruni, Biswal (India) 2016

Множества и подмножества сборочных последовательностей:
* __Liaison-based__ - множества, построенные на графах(матрицах смежности для них) отношений(соединений) деталей. В вершинах графа - детали, в рёбрах - наличие соединения и иногда дополнительная информация о соединении (тип соединения и т.д.)
![](img/liaison-graph.jpg)
* __Feasible__ - геометрически доступные множества. Основаны на т.н. `feasible predicate` - условии, при котором выбранная сборка доступна в геометрическом или механическом смысле. Геометрически доступной считается подсборка, все детали которой могут быть соединены без коллизий. К каждой из подсборок liaison-множества применяется некая функция, которая отвечает в формате Да/Нет на вопрос о возможности той или иной сборки. Таким образом из liasion-матрицы формируется interference-матрица, которая отражает наличие или отсутствие коллизий между отдельными деталями.
* __Stable__ - множества устойчивых (не разваливающихся) подсборок. Могут разделяться на нестабильные, частично стабильные, полностью стабильные.
* __Optimal__ - оптимальные по отношению к целевой функции (стоимость, энергоёмкость, смены инструмента, операции). Часто инженеру нужно выбрать между несколькими допустимыми и стабильными последовательностями сборки, поэтому применяется алгоритм оптимизации. Сущестует множество типов алгоритмов оптимизации (ACO: Ant Colony Optimization, GA: Genetic Algorithm, PSO: Particle Swarm Optimization, MA: Memetic Algorithm, IA: Immune Algorithm, NN: Neural Networks, GSA: Genetic Simulated Annealing, FF: Firefly Algorithm, FW: Fireworks, MILP: Mixed Integer Linear Programming, MIP: Mixed Integer Programming), которые применяются в сочетании с различными входными данными (геометрические отношения, ограничения приоритета, информация о приспособлениях и подсборках) и целевыми функциями. Полная таблица исследований приведена в таблице 3 из работы (_Bahubalendruni, Biswal '2016_). Там же приводится статистика самых популярных:
	* входных данных - `Liaison` и `Geometrical feasibility` матрицы
	* алгоритмов оптимизации - Генетические алгоритмы в 40% исследований
	* целевых функций - минимизация стоимости и количества изменений направлений сборки.

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

![](img/assembly-sequence-sets.jpg)

Современные CAD-системы позволяют получать следующие данные:
* liaison data - связи между деталями
* assembly cutsets - наборы разрезов
* questions to generate precedence relations - вопросы для создания отношений приоритета
* interference free matrix/interference data - данные о помехах
* assembly mating conditions - условия сопряжения сборки 
* feasible assembly sequence(s) - геометрически допустимые сборочные последовательности
* optimal/near optimal feasible assembly sequence - оптимальные и близкие к оптимальным последовательности

Большинство методов планирования последовательностей сборки (Assembly Sequence Planning, ASP) основаны на графах. На иллюстрации ниже показаны пример сборки (a) и соответствующие ему `blocking-граф` (b), `AND/OR-граф` или [and-or tree](https://en.wikipedia.org/wiki/And%E2%80%93or_tree) (c), `liaison-граф` (d). Граф Liaison часто применяется как входной в ASP-систем.

![](img/assembly_graph_types.jpg)

## Доступные программные реализации
- Python-скрипты для генерации AND/OR-графа - https://github.com/wzl-muenker/AOG-Generation

## Обзор актуальных исследований


### Гиперграфовый подход в декомпозиции сложных технических систем
__Божко А.Н. (2016-2019 гг.)__

Декомпозиция технической системы на сборочные единицы (СЕ) – одна из важных инженерных задач технической подготовки дискретного производства. На основе выбранной иерархии сборочных единиц формируются многие конструкторские и технологические документы: схема сборки, сборочного состава, разузлования, технологического членения и т.д.
Известно, что с вычислительной точки зрения – это труднорешаемая задача. Даже самая простая ее постановка – разбиение плоской фигуры на связные составные части – является NP-полной. Тем не менее, существуют различные подходы, призванные в той или иной степени упростить и автоматизировать решение данной задачи. 
Одним из таких подходов является применение гиперграфов для декомпозиции сложных технических систем. Данный подход был предложен А.Н. Божко в ряде работ, где он описывает математический аппарат и обосновывает преимущества подхода применительно к задаче. 

Для описания подхода введем необходимые понятия:
Гиперграфом называется пара  $H = (X, E)$, где $X$ – множество вершин, а $E$ – семейство подмножеств $X$, называемых гиперребрами. В общем случае, от обычного графа гиперграф отличается тем, что его гиперребра могут содержать в себе более двух вершин. 

![](img/DataStructureHypergraph.png)

Важным понятием является базирование.

__Базирование__ – это придание заготовке, детали или изделию требуемого положения относительно выбранной системы координат.

__База__ – поверхность или заменяющее ее сочетание поверхностей, ось, точка, принадлежащая заготовке, детали или изделию, которая используется для базирования.

__Конструкторская база__ – база, которая служит для базирования детали или сборочной единицы при сборке изделия. 

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

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

![](img/AsmHypergraph.png)

Чертеж изделия и гиперграф конструкции

Корректной математической моделью механической структуры является __s-гиперграф__,  т.е. гиперграф, который можно преобразовать в точку при помощи последовательности нормальных стягиваний. Нормальным стягиванием называется преобразование гиперграфа, заключающееся в отождествлении двух вершин ребра и удалении этого ребра. 
При этом важно отметить, что поскольку СЕ должна соответствовать требованиям независимой собираемости, механическая структура СЕ описывается s-подграфом s-гиперграфа. 

Божко вводит ряд возможных ограничений, позволяющих формализовать и автоматизировать процесс построения гиперграфа сборки. Перечислим их:
1.	Деталь не может входить в две и более СЕ
2.	Гиперребро (а также ребро) входит в отдельную СЕ или соединяет различные СЕ
3.	Любая СЕ содержит хотя бы одно ребро
4.	Для СЕ должно выполняться линейное соотношение между числом вершин и связей гиперграфа
5.	Если гиперребро (а также ребро) включено в состав СЕ, то все его инцидентные вершины должны войти в данную СЕ. Верно и обратное
6.	Разбиение не может быть тривиальным, должна быть хотя бы одна невырожденная (содержащая более одного элемента) СЕ
При этом, конструктор может налагать ряд дополнительных ограничений исходя из специфики объекта:
1.	Некоторые детали входят в одну СЕ
2.	Некоторая пара деталей не входит в одну СЕ
3.	Запрет на включение детали в конкретную СЕ
4.	Запрет на включение детали в любую СЕ
5.	Числовые ограничения на СЕ, например, по массе, габаритам, составу и тд
Можно формализовать и структурные ограничения на гиперграф -  возможность маскировки гиперребер – замены гиперребер на отдельные вершины в дереве сборки. Для этого маскируемые (схлопываемые) вершины должны принадлежать одной сборочной единице.

Для оптимизации можно задать целевые функции, которые позволят формализовать принятие рациональных решений:
1.	Большинство деталей должны войти в СЕ
2.	Число СЕ должно быть максимальным
3.	Механические связи высокой «валентности» целесообразно реализовывать на начальных этапах сборочного процесса. 
4.	Упрощение сборки сложного изделия путем минимизации числа механических связей на финальных операциях
5.	Минимизировать число необходимых сопряжений для реализации механической связи. 
При этом, в зависимости от специфики процесса, данный список можно дополнить требованиями и ограничениями, учитывающими специфику принятия решений. 

Данные принципы были реализованы в программном комплексе (далее - ПК) AssemBL, работающем в среде САПР Siemens NX 10.0. ( ["Структурный анализ изделия и проектирование сборочных комплексов в программном комплексе AssemBL"](https://cyberleninka.ru/article/n/strukturnyy-analiz-izdeliya-i-proektirovanie-sborochnyh-protsessov-v-programmnom-komplekse-assembl))

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

При этом, данный ПК опирается на ресурсы NX, в частности – команды меню Assemblies (Сборки) и Analysis (Анализ), а так же – на штатные инструменты NX для создания, редактирования и визуализации трехмерных моделей деталей и сборок. 

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

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

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

![Линеаризация и стягивание гиперграфа](img/HypergraphLinearisation.png)

Линеаризация и стягивание гиперграфа

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

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




### 3D Model-Based Assembly Sequence Optimization using Insertionable Properties of Parts - 2020

Kento Tariki, Takuya Kiyokawa, Gustavo Alfonso Garcia Ricardez, Jun Takamatsu, Tsukasa Ogasawara (Japan)

http://dx.doi.org/10.1109/SII46433.2020.9026210

__Исходные данные__: 3D-модель в формате STEP

__Алгоритм__: генетический алгоритм с двумя типами функций оценки (Fitness Functions). Также применяется Insertion Matrix (матрица вставки, IM), где подразделяются детали по признаку папа/мама. Insertion Matrix вычисляется из CAD-модели с помощью функций библиотеки `PythonOCC`:
* Функция `BRepAdaptor_Surface` извлекает информацию о поверхности детали и показывает её тип (плоскость, цилиндр, конус)
* Деталь классифицируется по признаку мама/папа
* В координате центра отверстия детали типа "мама" создаётся маленький куб и если какая-либо деталь имеет с ней общую точку (это вычисляется с помощью функции `BRepAlgoAPI_Common`), то она помещается в IM
* Функция `brepgprop_VolumeProperties` используется, чтобы определить, что общий объём больше нуля. И если она возвращает True, то деталь помещается в IM.

На рисунке ниже показан пример создания IM. Красная деталь типа "мама", зелёный куб находится в координате центра отверстия детали типа "мама", жёлтая деталь типа "папа".
![](img/insertion_matrix_gen.jpg)

__Полевые испытания__: использовались робот COBOTTA и ROS/MoveIt. Для примера использовалась в том числе модель из `World Robot Summit Assembly Challenge 2018`.

### Assembly Sequence Planning for Motion Planning - 2016

Weiwei Wan, Kensuke Harada, Kazuyuki Nagata

https://arxiv.org/pdf/1609.03108.pdf


__Исходные данные__: mesh-модель манипулятора, mesh-модели деталей, относительные позиции между деталями в сборке, целевая позиция сборки

__Алгоритм__: формируются все возможные подсборки и для каждой вычисляются:
* стабильность (stability)
* хватабельность (graspability) - число доступных способов захвата данным приспособлением
* собираемость (assemblability).
![](img/wan_ASP_algorithm.jpg)

Алгоритм позволяет найти некоторые оптимальные порядки и направления сборки, которые
1. Стабильны после окончания каждого этапа сборки
2. Имеют множество доступных захватов и гибки к кинематическим ограничениям роботов
3. Устойчивы к ошибкам сборки.

__Результат__:
* Порядок сборки (Assembly order): Какие детали собирать первыми
* Направление сборки (Assembly direction): Как накладывать или вставлять детали
* Доступные способы захвата (Accessible grasps): Как захватывать объекты в ходе сборки

__Полевые испытания__: собрали промышленный переключатель (switch).

### Optimal assembly sequence based on design for assembly (DFA) rules - 2020

Ine Melckenbeeckb, Sofie Burggraevea, Bart Van Donincka, Jeroen Vancraena, Albert Rosicha (EU)

__Исходные данные__: STEP-модель

__Алгоритм__: совместно применяются `AND/OR` и `liaison` графы в сочетании с практиками `Design for Assembly` (DFA).

Для измерения DFA используется метод оценки локального (_local motion_) и глобального (_global or extended motion_) движения. Локальное движение рассматривает зону физического контакта детали; глобальное движение оценивает также пересечения с деталями, не находящимися в зоне контакта, поэтому более трудоёмкое для вычислений. В алгоритме предложен метод двух-этапной оценки возможностей сборки - сначала оценивается локальное движение, а затем для направлений, в которых гарантируется локальное движение, оценивается глобальное движение.
1. Оценка локальных движений (`S-local` DFA score, %) производится с помощью `функций геометрического ядра CAD`, исходя из геометрических свойств деталей.
2. Оценка глобальных движений (`S-global` DFA score, %) производится с помощью рендеринга в `игровом движке Unity 3D`. Алгоритм получает на входе перечень возможных направлений, выявленных в ходе оценки локального движения.

Из локальной и глобальной возможности сборки выводится оценка для использования при генерации последовательности сборки.
Результатом проверки локального движения является `пространство допустимых направлений`. Объем этого пространства представляет собой количество возможных направлений сборки и, следовательно, является показателем простоты сборки. Чтобы использовать это значение в качестве оценки, нормализованный объем подается в непрерывную функцию оценки так, что невозможные сборки приравниваются к 0%, а неограниченная ничем сборка - 100%. С другой стороны, глобальная возможность сборки равна либо 0, либо 1, в которой 1 является сборкой, а 0 - нет.

Общее значение оценки `C-alg` вычисляется как `1/(S-local * S-global)`.

Порядок определения последовательности сборки:
1. STEP-файл
2. Программно генерируется `liaison`-граф, как пространство вершин разных деталей, расстояние между которыми ниже определённого значения (tolerance value)
3. Частичный AND/OR граф
4. Оценка DFA (возможен возврат к п.3). Для уменьшения количество обращений к DFA, разработаны три специальных ad-hoc правила:
	* Локальная оценка возможности сборки на определённом шаге не меняется, если добавляемая к подсборке деталь или другая подсборка не соприкасаются с ней. К примеру, мы собрали две подсборки вместе, определив для них local score. Далее, если мы добавим к одной из подсборок деталь, которая не имеет соприкосновений с другой подсборкой, то на данном local score это не отразится;
	* Невыполнимый этап сборки никогда не станет выполнимым путем добавления деталей в любой из узлов сборки
	* (инверсия предыдущего правила) Выполнимый этап сборки никогда не станет невыполнимым при удалении деталей из любого узла сборки.
5. Последовательность сборки

Пункты 3-4 формируют т.н. алгоритм поиска оптимальной последовательности.

__Полевые испытания__: не проводились

### A System Architecture for Constraint-Based Robotic Assembly with CAD Information - 2018

Mathias Hauan Arbo, Yudha Pane†, Erwin Aertbeliën† and Wilm Decré (EU)

http://dx.doi.org/10.1109/COASE.2018.8560450

__Исходные данные__: CAD-модель с пользовательскими метаданными, в работе не было задачи автоматизации генерации последовательности сборки

__Архитектура__:
![](img/constrained_based_sequence_planner_architecture.jpg)
* `Application Layer` - для `FreeCAD` создана `Task Library`, где имплементированы классы `Положить`, `Вставить`, `Вкрутить`, которые сопоставляются рёбрам `liaison-графа`
* `Process Layer` - `Tasks` (задачи) сопоставляются с `Skills` (навыками). Навыки делятся на `Composed` и `Atomic`. В итоге каждой детали сопоставляются тип задачи из Application Layer, навык (например, `grasp_and_insert`), набор атомарных навыков (move_cartesian gripper, guarded_cartesian, cylinder_insert) и инструмент (gripper).  В контексте работы Task - это задача, а Skill - это возможность производства.
* `Control Layer` - реализован на базе [eTaSL](https://etasl.pages.gitlab.kuleuven.be/intro.html) - язык спецификации задач для реактивного управления роботами + [Orocos](https://docs.orocos.org/) - [ROS-совместимый](https://github.com/orocos/rtt_ros2_integration) набор инструментов для управления роботами.

__Полевые испытания__: Собран компрессор с помощью 7-DOF KUKA LBR iiwa 14, pneumatic SCHUNK RH940 parallel gripper.

### Flexible Assembly through Integrated Assembly Sequence Planning and Grasp Planning - 2015

Ulrike Thomas, Theodoros Stouraitis, Maximo A. Roa (Germany)

__Исходные данные__: CAD-модель + база данных захватов для каждой детали в сборке
__Алгоритм__:
![](img/integrated_ASP_and_Grasp_Planning.jpg)

Сначала создаются карты для тестирования геометрической осуществимости (maps for the geometric feasibility tests) или `disassembly maps` по методу `Stereographical Projections of C-Space Obstacles` (стереографических проекций пространственных ограничений) автора U.Thomas, изложенному в [статье](https://ieeexplore.ieee.org/document/1217194) и уже применённой в исследовании 2010 года. Далее генерируются три типа графов: connectivity(liaison), force, hierarchy, из которых выводится AND/OR-граф. Далее `Grasp Planner` использует заранее подготовленную __базу данных захватов для каждой отдельной детали__ и фильтрует те вершины и рёбра `AND/OR-графа`, которые отсутствуют в доступных позициях захвата.

__Полевые испытания__: не проводились. Для симуляций применялся фреймворк `OpenRave` и конструкции из профилей.

### A novel Geometric feasibility method to perform assembly sequence planning through oblique orientations - 2021

Gulivindala Anil Kumar, M.V.A.Raju Bahubalendruni, V.S.S. Vara Prasad, Dara Ashok, K. Sankaranarayanasamy (India)

__Исходные данные__: CAD-модель

__Алгоритм__: акцент делается на методе получения матрицы геометрической доступности после liaison и stability матриц. Алгоритм называется `NASPM`:

![](img/geometric-feasibility-method-2012.jpg)

__Полевые испытания__: нет данных


### ASPW-DRL: assembly sequence planning for workpieces via a deep reinforcement learning approach - 2018

Minghui Zhao, Xian Guo, Xuebo Zhang and Yongchun Fang (China)

По мнению авторов часто используемые классы алгоритмов имеют следующие недостатки:
* Graph search - AND/OR - комбинаторный взрыв по мере увеличения количества деталей, специфичны к задаче и плохо обобщаются
* Knowledge-based - Domain/Problem Ontology - чувствительны к качеству базы знаний, плохо обобщаются
* Heuristic intelligent methods - Simulated annealing, Genetic algorithms, Neural nets - плохо обобщаются


__Исходные данные__: Подготовленная сцена в Gazebo

__Алгоритм__:

![](img/ASPW-DRL.jpg)

__Полевые испытания__: нет данных. Игрушечные модели в Gazebo


### Optimizing assembly sequence planning using precedence graph-based assembly subsets prediction method - 2019

Nan Zhang, Zhenyu Liu and Chan Qiu, Weifei Hu, Jianrong Tan (China)

В работе хорошее введение истории решения проблемы со ссылками.

__Исходные данные__: CAD-модель + `precedence graph` (граф приоритета), который как-то составляется инженером и задаёт приоритеты в порядке сборки деталей; подробности о precedence-графах изложены в работе Yong Wang, De Tian "[A weighted assembly precedence graph for assembly sequence planning](https://link.springer.com/article/10.1007/s00170-015-7565-5)"

__Алгоритм__: [Fireworks](https://en.wikipedia.org/wiki/Fireworks_algorithm)

__Полевые испытания__: нет данных. Замер эффективности алгоритма проводился по модели промышленного образца.

### Assembly Planning and Task Planning — Two Prerequisites for Automated Robot Programming - 2010

__Исходные данные__: CAD-модель

__Алгоритм__: Данные САПР сегментируются на примитивы (см. [Формирование графа на основе примитивов поверхностих](https://en.wikipedia.org/wiki/Geometric_primitive)), после чего генерируется граф из топологических контактов между такими поверхностными примитивами - Граф связности, узлами которого являются объекты. Объекты считаются связанными, если расстояние ними меньше заданного порогового значения. После построения этих графов, задача уходит к инженерам проектировщикам, которые в интерфейсе выбирают как объединить детали.

__Полевые испытания__: Операция по установке розетки питания на направляющую цилиндра

### A review on assembly sequence generation and its automation - 2015

Обзор 80 статей по теме планирования последовательности сборки. Подвод статистических исследований в этих статьях. Авторы делят проблему всех этих исследований на две глобальные проблемы:
	1. Ограниченность методов ИИ, который не справляется с локальным поиском. Метод не проверяет все доступные последовательности, а значит что полученная ИИ последовательность является близко оптимальной, а не глобально оптимальной. Также метод достаточно ресурсоёмкий.
	2. Предикаты снижают количество входных данных, но сильно влияют на пространство поиска. И иногда приводят к неверным последовательностям.

### Assemble Them All: Physics-Based Planning for Generalizable Assembly by Disassembly - 2022

YUNSHENG TIAN, MIT CSAIL, JIE XU, MIT CSAIL, YICHEN LI, MIT CSAIL, JIELIANG LUO, Autodesk Research, SHINJIRO SUEDA, Texas A&M University, HUI LI, Autodesk Research,  KARL D.D. WILLIS, Autodesk Research, WOJCIECH MATUSIK, MIT CSAIL

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

__Исходные данные__: CAD-модель
 
__Полевые испытания__: тысячи сборок из набора Fusion360

__Алгоритм__: Формируется граф сборки по принципу сборки-разборки. Для каждой новой детали, которая участвует в подсборке, формируются векторы разборки, основанные на [степенях свободы](https://en.wikipedia.org/wiki/Degrees_of_freedom_(physics_and_chemistry)). Из них получаются вектора разборки, которые реверсируются и из них получаются вектора сборки.

![](img/physics_based_approach_to_finding_vectors.jpg)
 
__Исходный код__: https://github.com/yunshengtian/Assemble-Them-All

### An integration of neural network and rule-based systems for design and planning of mechanical assemblies - 1993

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


### On the generation of robotic assembly sequences based on separability and assembly motion stability - 1994
C.K. Shin and H.S.Cho

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


### A three-stage integrated approach for assembly sequence planning using neural networks - 2008

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

__Исходные данные__:  CAD-модель(несколько моделей электро приборов)

__Полевые испытания__: Несколько моделей электроприборов.


### Using memetic algorithms with controlled local search to solve assembly - 2007
Hwai-En Tseng, Wen-Pai Wang, Hsun-Yi Shih

Сравнение Меметического алгоритма с ГА.
__Алгоритм__: [Меметический алгоритм](https://en.wikipedia.org/wiki/Memetic_algorithm). Генерация графа сборки, основанная на знаниях о соедениях деталей в изделии.

__Полевые испытания__: Нет данных

__Исходные данные__: Заранее подготовленные модели

### A Multi-Agent Evolutionary algorIthm for Connector-Based Assembly Sequence Planning - 2011
Сравнивают Многоагентный эволюционный алгоритм, с други алгоритмами оптимизации.

__Алгоритм__: [Многоагентный эволюционный алгоритм](https://deepai.org/publication/massively-concurrent-agent-based-evolutionary-computing), генерация графа сборки основанная на знаниях о соедениях деталей в изделии.

__Исходные данные__: идеальнее заранее готовые модели

__Полевые испытания__: неизвестно

### Planning Assembly Sequence with Graph Transformer - 2022

Первым шагом является определение направления системы координат. Основное направление сборки ориентируется согласно большинству выступов блоков, поэтому оно определяется как положительное направление оси Z (по вертикали). Второе направление сборки ориентируется по выступам блоков, занимает второе место после основного направления сборки.

![](img/lego_z_direction.jpg)
![](img/icra_asp_algorithm.jpg)

__Алгоритм__: [Метод грубой силы](https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D0%BD%D1%8B%D0%B9_%D0%BF%D0%B5%D1%80%D0%B5%D0%B1%D0%BE%D1%80), формирование ASP из направлений.

__Исходные данные__: LEGO Studio

__Полевые испытания__: собрали 100 моделей животных LEGO, созданных и загруженных отдельными пользователями в LEGO Studio, среди которых самая простая состоит из 3 кубиков, а самая сложная — из 44 кубиков 

__Исходный код__: https://github.com/AIR-DISCOVER/ICRA_ASP


### Assembly sequence planning method based on knowledge and ontostep - 2021
Jiahui Qian,Zhijing Zhang,Chao Shao,Hanqing Gong

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

- Индикатор базы. Индикатор равен количеству ситуаций, когда сборка является базой для других деталей. Чем выше значение, тем выше приоритет сборки.
- Индикатор соседства. Используется для описания количества частей, соединенных с частью объекта. Теоретически, чем больше целевая часть соединена с другими частями, тем раньше она будет собрана. Если к целевой части подключено более 4 частей, индикатор соседа равен 1.
- Индикатор сложности. Время сборки всегда зависит сложности процесса сборки. Сложность сборки самой длинной трудоемкой детали примем равным 1, а показатель сложности остальных деталей оговорим по пропорциональной зависимости времени сборки от самой сложной.
- Индикатор точности. Этот индикатор используется для отображения влияния требований к точности сборки на приоритеты сборки. Как правило, чем выше требуется точность сборки, тем более высокий приоритет имеет деталь. Соотношение между требованием точности и показателем точности 1:4 означает
конкретное требуемое значение точности (мкм).
- Индикатор симметрии. Представляет собой номер объекта сборки, симметричного относительно трех плоскостей симметрии x.y, y.z и x.z. Например, стальной шар всегда легко собрать, потому что он симметричен относительно всех трех плоскостей (x5=3). Наоборот, трудно собрать детали с низкой симметрией, а это значит, что их нужно собирать в первую очередь. 

__Алгоритм__: Генерация графа сборки основанная на индфикаторах о геометрии деталей в изделии.

__Полевые испытания__: Расчет для сборки компонентов военного взрывателя.

__Исходные данные__: STEP-модель

### Generating complete disassembly sequences by utilising two-dimensional views - 2015
Kantha.M

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

__Алгоритм__: Генерация графа сборки основанная на индфикаторах о геометрии деталей в изделии.

__Полевые испытания__: Расчет для сборки компонентов военного взрывателя

__Исходные данные__: 3D модель клапана обратной подачи
 
