Все выпуски

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

Computer-aided assembly planning for complex products is an important engineering and scientific problem. The assembly sequence and content of assembly operations largely depend on the mechanical structure and geometric properties of a product. An overview of geometric modeling methods that are used in modern computer-aided design systems is provided. Modeling geometric obstacles in assembly using collision detection, motion planning, and virtual reality is very computationally intensive. Combinatorial methods provide only weak necessary conditions for geometric reasoning. The important problem of minimizing the number of geometric tests during the synthesis of assembly operations and processes is considered. A formalization of this problem is based on a hypergraph model of the mechanical structure of the product. This model provides a correct mathematical description of coherent and sequential assembly operations. The key concept of the geometric situation is introduced. This is a configuration of product parts that requires analysis for freedom from obstacles and this analysis gives interpretable results. A mathematical description of geometric heredity during the assembly of complex products is proposed. Two axioms of heredity allow us to extend the results of testing one geometric situation to many other situations. The problem of minimizing the number of geometric tests is posed as a non-antagonistic game between decision maker and nature, in which it is required to color the vertices of an ordered set in two colors. The vertices represent geometric situations, and the color is a metaphor for the result of a collision-free test. The decision maker’s move is to select an uncolored vertex; nature’s answer is its color. The game requires you to color an ordered set in a minimum number of moves by decision maker. The project situation in which the decision maker makes a decision under risk conditions is discussed. A method for calculating the probabilities of coloring the vertices of an ordered set is proposed. The basic pure strategies of rational behavior in this game are described. An original synthetic criterion for making rational decisions under risk conditions has been developed. Two heuristics are proposed that can be used to color ordered sets of high cardinality and complex structure.

В данной работе исследуется влияние пространственного разрешения дискретизированного (решеточного) представления рабочего пространства на эффективность и корректность поиска оптимального пути в сложных условиях. Рассматриваются сценарии, характеризующиеся возможным наличием узких проходов, неоднородным распределением препятствий и зонами повышенных требований к безопасности в непосредственной окрестности от препятствий. Несмотря на широкое применение решеточных представлений рабочего пространства в робототехнике благодаря их совместимости с сенсорными данными и поддержке классических алгоритмов планирования траекторий, разрешение этих решеток оказывает существенное влияние как на достижимость цели, так и на показатели оптимального пути. Предлагается алгоритм, сочетающий анализ связности пространства, оптимизацию траектории и геометрическое уточнение безопасности. На первом этапе с помощью обобщения алгоритма Лиса (Leath) оценивается достижимость целевой точки путем выявления связной компоненты, содержащей стартовую позицию. При подтверждении достижимости целевой точки на втором этапе алгоритм A* применяется к узлам данной компоненты для построения пути, минимизирующего одновременно как длину пути, так и риск столкновения. На третьем этапе для узлов, расположенных в зонах безопасности, осуществляется уточненная оценка расстояния до препятствий с помощью комбинации алгоритмов Гилберта – Джонсона – Кирти (GJK) и расширяющегося многогранника (EPA). Экспериментальный анализ позволил выявить нелинейную зависимость вероятности существования и эффективности оптимального пути от параметров решетки. В частности, снижение пространственного разрешения решетки повышает вероятность потери связности и недостижимости цели, а увеличение ее пространственного разрешения влечет рост вычислительной сложности без пропорционального улучшения характеристик оптимального пути.

This paper examines the impact of the spatial resolution of a discretized (lattice) representation of the environment on the efficiency and correctness of optimal pathfinding in complex environments. Scenarios are considered that may include bottlenecks, non-uniform obstacle distributions, and areas of increased safety requirements in the immediate vicinity of obstacles. Despite the widespread use of lattice representations of the environment in robotics due to their compatibility with sensor data and support for classical trajectory planning algorithms, the resolution of these lattices has a significant impact on both goal reachability and optimal path performance. An algorithm is proposed that combines environmental connectivity analysis, trajectory optimization, and geometric safety refinement. In the first stage, the Leath algorithm is used to estimate the reachability of the target point by identifying a connected component containing the starting position. Upon confirmation of the target point’s reachability, the A* algorithm is applied to the nodes of this component in the second stage to construct a path that simultaneously minimizes both the path length and the risk of collision. In the third stage, a refined obstacle distance estimate is performed for nodes located in safety zones using a combination of the Gilbert – Johnson –Keerthi (GJK) and expanding polyhedron (EPA) algorithms. Experimental analysis revealed a nonlinear relationship between the probability of the existence and effectiveness of an optimal path and the lattice parameters. Specifically, reducing the spatial resolution of the lattice increases the likelihood of connectivity loss and target unreachability, while increasing its spatial resolution increases computational complexity without a proportional improvement in the optimal path’s performance.