=Paper=
{{Paper
|id=Vol-3003/short6
|storemode=property
|title=Optimal Spatial Configurations Synthesis Using Visualization of the Decision-Making Process
|pdfUrl=https://ceur-ws.org/Vol-3003/short6.pdf
|volume=Vol-3003
|authors=Sergiy Yakovlev,Oleksii Kartashov,Kyryl Korobchynskyi,Iryna Yakovleva,Olga Yarovaya
|dblpUrl=https://dblp.org/rec/conf/profitai/YakovlevKKYY21
}}
==Optimal Spatial Configurations Synthesis Using Visualization of the Decision-Making Process==
https://ceur-ws.org/Vol-3003/short6.pdf
Optimal Spatial Configurations Synthesis Using Visualization of
the Decision-Making Process
Sergiy Yakovleva, Oleksii Kartashova, Kyryl Korobchynskyia, Iryna Yakovlevab
and Olga Yarovayaa
a
National Aerospace University "Kharkiv Aviation Institute", 17 Chkalova st., 61070, Kharkiv, Ukraine
b
National University of Urban Economy in Kharkiv, 17 Marshala Bazhanova st., 61002, Kharkiv, Ukraine
Abstract
The paper proposes basic models of the problem of optimal synthesis of spatial
configurations of geometric objects. The efficiency of using modern information
technologies is substantiated, which allow automatically creating models of
optimization problems and their subsequent solution using specialized software
packages. It is proposed to use the visualization of geometric information in the decision
process to attract the decision maker. A technology is described that allows you to
change the current configuration of geometric objects in an interactive mode.
Keywords
Geometric object, spatial configuration, information technologies, visualization.
1. Introduction
At present, there is a sharp increase in interest in the development and implementation of information
technologies for support and decision-making, requiring the synthesis of complex technical systems,
taking into account the spatial form of their elements. This task is inextricably linked with the tasks of
geometric design, where the mapping of geometric information about material objects into Euclidean
space is performed. Among such practical areas of application are logistics of transport and warehouse
services, the layout of aerospace objects, the safety of fuel and energy complexes, the development and
improvement of 3D printing technologies, etc. All of them are necessary taking into account the shape
of the corresponding prototypes and the imposition of restrictions on their relative position. The
synthesis of such spatial configurations of material objects includes their processing, transformation
and storage of geometric information about objects. It is based on the construction and use of
information and analytical models of relevant problems, the development and implementation of
modern information technologies. An integral feature of such technologies is the constant visualization
of design solutions, which allows them to be automatically corrected under the guidance of a decision-
maker.
This research is intensively developing all over the world. An example is the Springer Optimization
and Applications series [1], which focuses on models, methods, and information technology for
assembly synthesis in aerospace engineering. Another illustration is the series "Lecture notes on
logistics" [2], devoted to the study of the problems of logistics, transport, warehousing and distribution
services. Important results on mathematical modeling and software development for the problem of
geometric design are presented in [3] - [13]. To solve the problems of synthesizing optimal
configurations of complex spatial objects, it is of interest to develop new information technologies using
the automatic creation of mathematical models. In this case, computer modeling involves visual
transformation of geometric information.
_____________________________________
International Workshop of IT-professionals on Artificial Intelligence (ProfIT AI 2021), September 20-21, 2021, Kharkiv, Ukraine
EMAIL: svsyak7@gmail.com (A. 1), alexeykartashov@gmail.com (A. 2), kirill.korobchinskiy@gmail.com (A. 3),
yakovlevairine@gmail.com (A. 4), helga.yarovaya@gmail.com (A. 5)
ORCID: 0000-0003-1707-843X (A. 1); 0000-0002-6282-553X, (A. 2); 0000-0002-3676-6070 (A. 3); 0000-0001-5204-9779 (A. 4);
0000-0003-4969-1677 (A. 5)
©️ 2021 Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR Workshop Proceedings (CEUR-WS.org)
Thus, the purpose of this article is, first of all, the development and research of information
technologies that allow the formation of an information-analytical model for describing data structures
when creating complex spatial configurations. Second, it is important to consolidate the geometric
information data structures used in the optimization and visualization of spatial configurations. Third,
it is necessary to perform dynamic transformation of data structures in the synthesis and visualization
of spatial configurations of complex objects..
2. General information
Consider a set of material objects of a given geometric shape. Certain restrictions can be imposed
on their relative position, when fulfilled, a certain spatial configuration is formed. Let's introduce the
concept of geometric information g = ( s , m , p ) about an object S, which includes a spatial
shape s of S, metric parameters m = ( m1 ,...,m k ) that specify its sizes, and placement parameters
p = ( p1 ,..., p l ) about the object S position in space [14]. A class of problems associated with such
a display of geometric information are studied in the theory of geometric design. Usually, geometric
objects with the shapes of a sphere, cone, parallelepiped, polygon, as well as complex objects composed
of them are considered. In this case, the metric characteristics of the geometric objects involved are
considered to be fixed. The problem of synthesizing spatial configurations of objects of arbitrary shape
have their own characteristics, which requires the development of new mathematical models, as well as
further development of methods for processing, transforming and storing geometric information about
material objects.
To describe the external structure and type of a set of material objects in papers [14, 15], the concept
of a configuration space of geometric objects is introduced, which is formed on the basis of geometric
information g = ( s , m , p ) . Let the object S has a equation of its boundary
f ( , m ) = 0,
where = ( x, y ) , if S R 2 , and = ( x, y, z ) , if S R 3 underlies determining the components s
and m of geometric information g . Some approaches to setting boundary equations for 2D and 3D
objects are presented in [10].
( )
Consider a coordinate system Oxyz ( Oxy ) in space R 3 R 2 , respectively, further referred to it as
a fixed one. With an object S , we associate their own coordinate system, which origin is called a pole.
A relative position of these coordinate systems characterizes the placement parameters
( )
p = p1 ,..., p = ( v, ) of the object. The general position equation of a geometric object (GO)
relative to a fixed coordinate system can be specified as follows
F ( , m, p ) = f A ( − u ) , p = 0 ,
where A is an orthogonal operator defined through the angular parameters v .
This equation is the basis for the formation of the configuration space of a geometric object and
determines a set of values of geometric variables, which are called generalized coordinates. Generalized
coordinates specify the position of a set of geometric objects in space both relative to each other and
relative to a fixed coordinate system. In what follows, we will assume that the configuration space
( S ) of GO S is induced by the generalized variables g = ( m, p ) .
3. Configuration Space of Geometric Objects
( )
Consider a set of objects = S1 ,..., S n . By S i , we denote a configuration space of an object
( )
S i , which the generalized variables are g i = m i , p i , i J n , where J n = 1,...,n . To each point
( ) ( ) ( )
g i S i , a parameterized object S i g i R 3 R 2 will be associated. Let us form configuration
space
( ) = ( S1 ) ... ( S n )
(
of a set of basic GOs given by the generalized variables g = g 1 ,..., g n . )
A mapping : → ( ) satisfying a given set of constraints determines a spatial configuration
of GOs S i , i J n [14, 15].
Presence of the constraints allows offering a typology of spatial configurations depending on
relations GOs. Note that approaches of formalizing the relations are completely determined by choice
of the generalized variables of CS, by constraints on a mutual location of GOs, and by their
physicomechanical characteristics (see Fig. 1).
For the objects S i , i J n , let us introduce a binary relation of a pairwise non-intersection. We
will use a notation S S if int S int S = , i.e., if objects S and S have no common internal
( ) ( ) for all i, j J n , i j , then the spatial configuration is called a packing
points. If S i g i S j g j
configuration. In most of the packing problems, one more object S 0 called a container is involved. In
this case, all objects S i , i J n must be placed into the container S 0 .
Figure 1: The process of forming spatial configurations of geometrical objects
Now, on the set of GOs, let us introduce one more binary relation – an inclusion relation , where
a denotation S S is used to reflect that int S S .
Assume that an object S 0 has the generalized variables g 0 in configuration space Ξ ( S 0 ) . Let us
form a new configuration space Ξ ( S0 ) = Ξ ( S0 ) Ξ ( ) . Then a set of the generalized variables
( ) S0 ( g 0 ) and Si ( g i ) S j ( g j ) for any i, j J n , i j.
will define a layout configuration, if S j g j
The generalized variables g 0 , g 1 ,..., g n of configuration space Ξ ( S 0 ) may also be subject to
additional constraints. This induces special classes of packing configurations, such as a layout
configuration [15, 16] wnen constraints on the minimum and maximum distances between objects are
given. If the objects S i , i J n are solid bodies with given masses, then a balanced system of such
bodies yields a balanced packing configuration [17]. When the parameters of the models are discrete,
so-called Euclidean combinatorial configurations can be considered [18].
Let a functional : ( S 0 , ) → R 1 be given in configuration space Ξ ( S 0 , ) . Now, we can
formulate a problem of finding an optimal configuration of GOs S i , i J n . So, it is required to find
g * = arg min (g) , (1)
gW ( S 0 , )
where W is a set of admissible configurations satisfying certain constraints .
(
The generalized variables g = g 0 , g 1 ,..., g n ) of configuration space ( S0 , ) take real values
and allow equivalent formulating the problem (1) as a mathematical programming problem. To
formalize constraints on relative positions of GOs, Ф-functions [19] and -functions [20] may be used.
In this study, existing methods for constructing Ф-functions of basic 2D and 3D objects were
summarised and generalized. They concern placement and packing problems with variable metric
parameters of GOs and are utilized when the BaseObjects database was formed.
We propose an object-oriented model of a GO consisting of an abstract class GeometryObjectBase,
which implements a collection of virtual methods with common operations for all geometric objects
(GOs). Examples of such operations are reading information from a file or database, saving data,
visualizing configurations, etc. A GeometryObjectBase class' descendants have two implementations
depending on the GO-dimension – 2D or 3D. Each of these classes contains fields and virtual methods
for affine transformations of the objects' motion in the corresponding space. Such an implementation
allows creating and processing spacial GOs of highly complex shapes.
Based on the peculiarities of the GO-object-oriented model and the specifics of mathematical
modelling of GOs' relations, an information-analytical model of the problem of spatial configurations
synthesis is designed (Fig. 2).
Figure 2: The process of forming information-analytical model
Note that, in the model, analytical and informative components can be singled out. The analytical
component is associated with a choice of the generalized variables in the problem's mathematical model,
as well as with a way of formalization of constraints on the relative position of GOs and present quality
criteria.
The model's information component describes the formation of a spatial objects' data structure and
creating consolidated storage of the spatial configuration data. A choice of a structure of input data is
caused by the specifics of utilizing available optimization solvers and visualization software in the
process of solving the problem. For instance, we focused on the usage of COIN-OR, which is a popular
open-source software package.
Depending on a chose of quality criteria and additional constraints, problems of optimal
configurations' synthesis can be included in different classes of mathematical programming problems.
To find a local extremum, it is sufficient to formalize the objective function, functional constraints,
Jacobian and Hessian. In this case, developing new information technologies for optimal configurations'
synthesis in complex systems requires constructing their information-analytical models in automatic
mode. With this regard, the advantage of our approach is the possibility of implementing methods for
solving such problems disregarding a research domain. Also, note that the approach is applicable for
solving NP-hard problems ignoring their high dimensionality and multiextremality.
4. Information Technology Model for the Synthesis of Spatial Configurations
The information technology of spatial configuration synthesis consists of six interconnected blocks
and is depicted in Figure 3 in the form of an IFEF0 chart. In the figure, it is shown how the system
functional blocks interact with each other. Also, the required steps to obtain a new configuration are
shown.
Figure 3: Information technology for the synthesis of spatial configurations
Block 1 depicts a process of forming the model's analytical component with respect to a quality
criterion and additional constraints.
In Block 2, depending on initial data, a spatial configuration data structure is formed using the
generalized variables and configuration space.
Block 3 is responsible for the synthesis of the locally optimal spatial configurations with respect to
the chosen quality criterion and generalized variables. Then, the designed mathematical model is
analyzed, and a choice of the software COIN-OR is justified. After that, the geometric information data
structure is adapted for utilizing the solver. Finally, limitations on computing resources (memory size
and runtime) are established, and recommendations on a relevant solution accuracy are developed. An
output of the block is a spatial configuration meeting all the constraints.
In Block 5, processing and storage of results of spatial configurations' synthesis in a data warehouse
"Configuration Repository" using DBMS are carried out.
Finally, Block 6 describes the possibilities of involving a decision-maker (DM) in an analysis of the
found spatial configuration. Depending on the quality of a decision found so far, DM can either leave
the decision unchangeable or proceed in order to improve it. In the latter, DM sets the new spatial
configuration's generalized variables and repeat the above process again. Thus, parameters of the
optimization model may be changed at the following iterations. Note the initial spatial configuration
may be infeasible, but, according to the technology proposed, a locally optimal configuration are
automatically synthesized, which satisfy all available constraints.
5. The Software Package Description
In the scope of models and methods of information technologies of layout synthesis of spatial
configurations, a software applications has been developed, including [21]:
✓ software application – a solver for implementation of methods of spatial configurations'
optimization;
✓ repository program – a consolidated repository for storing information on the process of
solving the problems;
✓ software applications for interactive visualization of the solutions obtained.
The software complex has a hierarchical structure and consists of three functional parts. The first
component is the software application (SA) GeneralSolver that integrates a chosen Solver with
necessary computational software components. GeneralSolver is used to dynamically transform the data
structure of geometric information in the process of synthesizing spatial configurations of complex
objects. In turn, this SA is based on the .NET Framework. The program validates the data entered by a
user and verifies their correctness and compliance with the format. If incorrect data are entered, an error
warning with clarification is displayed on the screen. If a critical error occurs while executing a
program, the program automatically terminates.
The second component of the complex is SA for storing results of the GeneralSolver calculations.
In addition to the evaluation results, the repository store full information about spatial configurations
of underlying objects, values of configuration space generalized variables involved in the synthesis, and
information on a mathematical formulation of problems (quality criteria and constraints).
The third component is SA for 2D or 3D visualization. For 3D visualization, one can use different
visualization packages: 3Ds Max Studio, Revit, VRED, Stingray, etc.
The described software package was developed in Visual Studio 2017 using different programming
languages (C #, C ++, and ECMA Script).
6. An Example of Implementing the Results
As an example of implementing the results, consider the following packing problem for spherical
objects. It is required to place a set of spheres of a given radius into a sphere of minimum radius.
Generalized variables in this problem are the coordinates of the centers of spheres (placement
parameters) and radii (metric parameters). The mathematical model as a nonlinear optimization problem
is given in [22-25]. NLP-Solver IPOPT (https://tomopt.com/tomlab/) was used to find local extrema.
The interactive environment 3Ds Max Studio was used to display the results and interact with DM.
First, the format of the initial data of the mathematical model is converted into the form of the Solver
representation. Then the initial values of the generalized variables are set and the optimization process
is carried out using IPOPT. The result (local extremum) is stored in a special format in the consolidated
database and converted to the 3Ds Max Studio data format. As a result of the analysis of solution, the
decision maker can make any changes using the interactive graphical environment and (or) the
associated numeric parameter values. Taking into account the changes made, we get a new starting
point, which is again fed to the Solver. We have an iterative process that is repeated until a solution is
obtained that satisfies the DM.
Below we will illustrate the visualization of the described process. Let's randomly generate the initial
configuration of spherical objects. Note that the initial configuration may not satisfy the constraints of
the problem, that is, the spheres may intersect, be outside the placement area and at large distances from
each other. However, using IPOPT ensures that all the constraints are met, as shown in Fig. 4. The DM
can modified the obtained solution. As a result, using the export script, a new spatial configuration is
formed, which is used as the starting point (Fig. 5). The improved locally optimal configuration is
shown in Fig. 6. Other results of numerical experiments are described in [26, 27]. The results are saved
in text files, which allows you to return to any stage of the calculation at any stage. If the spatial
configuration satisfies the DM, then it is saved in the form of graphic data, files with initial,
intermediate and resulting data.
Figure 4: The locally optimal solution
Figure 5: The decision, modified by the decision-maker
Figure 6: The improved configuration
7. Conclusion
Thus, the paper describes the models and methods for solving the optimization problems of the synthesis
of spatial configurations of geometric objects. It is based on the definition and formalization of
geometric information and the concept of configuration space. This made it possible to propose new
information technologies for interactive problem solving, using both specially developed methods and
modified known approachs. The presented approach is applied to solve a wide class of problems of
geometric design, in particular, problems of packing, layout and coverage.
8. References
[1] Springer optimization and its applications, 2021. URL: https://www.springer.com/series/7393.
[2] Lecture Notes in Logistics, 2021. URL: https://link.springer.com/bookseries/11220.
[3] G. Fasano, A modeling-based approach for non-standard packing problems, Optimized Packings
with Applications 105, pp. 67–85, 2015. doi:10.1007/978-3-319-18899-7_4.
[4] A. Bortfeldt, G. Wascher, Constraints in container loading: a state-of-the-art review, European
Journal of Operational Research 229 (1), pp. 1–20, 2013. doi:10.1016/j.ejor.2012.12.006.
[5] G. Waescher, H. Haussner, H. Schumann, An improved typology of cutting and packing problems,
European Journal of Operational Research 183, pp. 1109–1130, 2007.
doi:10.1016/j.ejor.2005.12.047.
[6] G. M. Fadel, M. M. Wiecek, Packing optimization of free-form objects in engineering design, In:
Fasano, G. and Pintér, J.D. (eds.) Optimized Packings with Applications. pp. 37–66. Springer
International Publishing, Cham, 2015. doi:10.1007/978-3-319-18899-7_3.
[7] Z.-G. Sun, H.-F. Teng, Optimal layout design of a satellite module, Engineering Optimization.
35(5), pp. 513–529, 2003. doi:10.1080/03052150310001602335.
[8] J. Coggan, K. Shimada, S. Yin, A survey of computational approaches to three-dimensional layout
problems, CAD Computer Aided Design 34(8), pp. 597–611, 2002.
doi:/10.1016/S0010-4485(01)00109-9.
[9] T. Tian, W. Zhu, A. Lim, L. Wei, The multiple container loading problem with preference,
European Journal of Operational Research 248 (1), pp. 84–94, 2016.
doi:10.1016/j.ejor.2015.07.002.
[10] A. Drira, H. Pierreval, S. Hajri-Gabouj, Facility layout problems: a survey, Annual Reviews in
Control 31 (2), pp. 255–267, 2007. doi:10.1016/j.arcontrol.2007.04.001.
[11] Y. Stoyan, T. Romanova, Mathematical models of placement optimization: two- and three-
dimensional problems and applications, In: G. Fasano and J. Pintér (eds.) Modeling and
Optimization in Space Engineering 73, pp. 363–388. Springer, New York, 2013.
doi:10.1007/978-1-4614-4469-5.
[12] O. Blyuss, L. Koriashkina, E. Kiseleva, R. Molchanov, Optimal placement of irradiation sources
in the planning of radiotherapy, Mathematical Models and Methods of Solving. Computational and
Mathematical Methods in Medicine, 2015. doi:10.1155/2015/142987.
[13] E. M. Kiseleva, The emergence and formation of the theory of optimal set partitioning for sets of
the n-dimensional Euclidean space, Theory and application. Journal of Automation and
Information Sciences, 50 (9), pp. 1–24, 2018. doi:10.1615/JAutomatInfScien.v50.i9.10.
[14] Y. G. Stoyan, S. V. Yakovlev, Configuration space of geometric objects, Cybernetics and Systems
Analysis 54(5), pp. 716–726, 2018. doi:10.1007/s10559-018-0073-5.
[15] S. V. Yakovlev, On some classes of spatial configurations of geometric objects and their
formalization, Journal of Automation and Information Sciences, 50(9), pp. 38–50, 2018.
doi: 10.1615 / JAutomatInfScien.v50.i9.30.
[16] Yu. G. Stoyan, V. V. Semkin, A. M. Chugay, Optimization of 3D objects layout into a multiply
connected domain with account for shortest distances, Cybernetics and Systems Analysis 50(3),
pp. 374–385, 2014. doi:10.1007/s10559-014-9626-4.
[17] Yu. Stoyan, T. Romanova, A. Pankratov, A. Kovalenko, P. Stetsyuk, Balance layout problems:
mathematical modeling and nonlinear optimization, Space Engineering. Modeling and
Optimization with Case Studies 114, pp. 369–400, 2016. doi:10.1007/s10559-015-9746-5.
[18] Yu. G. Stoyan, S. V. Yakovlev, Theory and methods of Euclidian combinatorial optimization:
Current status and prospects, Cybernetics and Systems Analysis 56(3), pp. 366–379, 2020. doi:
10.1007/s10559-020-00253-6.
[19] G. Scheithauer, Yu. Stoyan, T. Romanova, Mathematical modeling of interactions of primary
geometric 3D objects, Cybernetics and Systems Analysis 41(3), pp. 332–342, 2005.
doi:10.1007/s10559-005-0067-y.
[20] S. V. Yakovlev, Formalizing spatial configuration optimization problems with the use of a special
function class, Cybernetics and Systems Analysis 55(4), pp. 581–589 (2019).
doi:10.1007/s10559-019-00167-y.
[21] S. Yakovlev, O. Kartashov, K. Korobchynskyi, The informational analytical technologies of
synthesis of optimal spatial configuration, In: IEEE 13th International Scientific and Technical
Conference on Computer Sciences and Information Technologies 1, pp. 140–143, 2018.
[22] S. M. Hifi, R. M’Hallah, A literature review on circle and sphere packing problems: models and
methodologies, Advances in Operation Research 7, pp. 1–22 (2009) doi:10.1155/2009/150624.
[23] Yu. Stoyan, G. Scheithauer, G. Yaskov, Packing unequal spheres into various containers,
Cybernetics and Systems Analysis 52(3), pp. 419–426, 2016. doi: 10.1007/s10559-016-9842-1.
[24] A. Sutou, Y. Day, Global optimization approach to unequal sphere packing problems in 3D.
Journal of Optimization Theory and Applications 114, pp. 671–694, 2002.
[25] Y. Stoyan, , G. Yaskov, T. Romanova, et al., Optimized packing multidimensional hyperspheres:
A unified approach, Mathematical Biosciences and Engineering 17(6), pp. 6601–6630, 2020.
doi:10.3934 / mbe.2020344.
[26] S. Yakovlev, O. Kartashov, K. Korobchynskyi, B. Skripka, Numerical results of variable radii
method in the unequal circles packing problem, In: 2019 15th International Conference on the
Experience of Designing and Application of CAD Systems, CADSM 2019 – Proceedings, pp. 1–
4, 2019. doi:443.webvpn.fjmu.edu.cn/10.1109/CADSM.2019.8779288.
[27] O. Kartashov, K. Korobchynskyi, I. Yakovleva, et al., Synthesis of spherical object
configurations, Models and information technologies. CEUR Workshop Proceedings 2864,
pp. 287–298, 2021.