The paper discusses the models and methods of information technology for the synthesis of optimal configurations of spatial objects. Models are based on the concept of geometric information and the formation of the configuration space of geometric objects. Information technologies carry out the transformation of geometric information in the process of synthesis of optimal configurations, the formation of an appropriate database structure, its consolidation and the organization of automatic exchange of information between the original software components and specialized software. An informationanalytical model for the synthesis of optimal configurations has been built. The problem of forming a data structure and creating a data storage is considered.
Currently, most publications are devoted to problems of mathematical modeling of systems with objects of a given spatial form and the development of special nonlinear optimization methods. The issues of information support, analysis of the data structure and methods of transformation of geometric information in the optimization process are not fully covered.
The purpose of this paper is to present the concept of creating information technology for the synthesis of spatial configurations of objects of a given shape and arbitrary metric characteristics. The use of such information technology allows to solve the following tasks:
• organize automatic exchange of information between the original software components and specialized software systems used to obtain local solutions and display the results of the solution in a convenient and multifunctional form; • parallelize the search for local minima at the global search stage, which significantly reduces the time spent on solving the problem; • visualize both final and intermediate solution results • carry out an interactive search for solutions, which allows you to get better results in a shorter time.
The present paper continues the research [1] related to the use of information technologies for the synthesis of spatial configurations of various classes of geometric objects. 2
Object - Oriented Model and Configuration Space of
Geometric Objects The papers [2,3] introduced the configuration space of geometric objects (GO), which is based on the formalization of the concept of geometric information. Geometric information g s ,m , p about the object S includes a spatial form s as an equivalence class of point sets in space R 3( R 2 ) ; metric parameters m ( m1 , ..., mk ) of the form, specifying the dimensions of the object; placement parameters p ( p1 , ..., pl ) , that determine the position of an object in space. On a plurality of geometric information, the linear space of canonical informations and the general information space are constructed. In accordance with the general concept of constructing such spaces, we define their structure in the following way.
To specify the components s and m of the geometric information g of the object S we use the equation of its boundary f ( ξ , m ) 0, where ξ ( x, y ) , if S R 2 , and ξ ( x, y, z ), if S R 3 . Let the variables m ( m1 , ..., mk ) have an admissible domain of values D R k , and the function f ( ξ , m ) is such that for any fixed m D f ( ξ , m ) = 0 , if fr S( m ) ; f( ξ , m ) > 0 , if int S( m ) ; f( ξ, m ) < 0 , if ξ c( cl S( m )) , where c , fr, int, cl are operators of topological complement, frontier, interior and closure respectively.
We put the equation of the boundary of an object in a space of corresponding dimension in the basis of the creation of its object-oriented model (see Fig. 1).
In the papers [4,5], classes of so-called basic 2D and 3D objects were identified. Circles, ellipses, rectangles, convex polygons, as well as their closed additions to the whole space are offered as basic 2D-objects. The main three-dimensional objects are spheres, rectangular parallelepipeds, straight circular cylinders, circular cones, convex polyhedra and closures of additions of these objects in space R 3 .
We propose to generalize the indicated results and form classical basic objects using the equations f c (x, y, m ) = 0 and c ( x, y, z, m ) 0 of their boundaries in the corresponding spaces R 2 ( R 3 ) (see Fig. 1). To construct an equation of the complex object boundaries, can be used the theory of R-functions [6].
Let us choose a system of coordinates in space R 3( R 2 ) , which we will call stationary, and we will associate with an object S their own (moving) coordinate system, the beginning of which is called a pole. The mutual position of the specified coordinate systems characterizes the placement parameters p = (p1 , ..., p β ) = ( v , θ ) , where v - the coordinate vector of the pole of the object in a fixed coordinate system, and θ - the vector of the angle parameters that determine the mutual position of the axes of the eigen and fixed coordinate systems. For S R 3 we have p = (p1 , ..., p β ) = ( v, θ ) . In the general case 6 , v = (v1 , v2 , v3 ) θ = (θ1 , θ2 , θ3 ) . For S R 2 we put p = ( v, θ ) = (v1 , v2 , θ) .
A position of the GO with respect to a stationary coordinate system may be given by the equation of its general position
F( , m, p ) f A( u ), p 0,
(
The equation (
Let us consider a set of objects = S1 , ..., S n . Denote Ξ( Si ) the configuration space of an object Si with generalized variables g i m i , pi , i J n , where we use the notation J n { 1, ..., n } . Each point g i Ξ( Si ) corresponds to a parameterized object Si ( g i ) R 3( R 2 ) . We will form the configuration space of a set of geometric basic objects Ξ( ) Ξ( S1 ) ... Ξ( S n ) with generalized variables g = ( g 1 , ..., g n ) .
Definition. The mapping : ( ) of a set = S1 , ..., S n in the configuration space Ξ( ) Ξ( S1 ) ... Ξ( S n ) , that satisfies a given set of constraints , specifies the spatial configuration of objects.
Thus, the spatial configuration defines a set of parameterized GOs Si ( g i ), i J n , which together totality form a complex object of a particular structure. Let us form a complex GO
S B=B S1 , ..., S n , where the operator B defines the structure Si , i J n of the object system. A complicated object S B in the configuration space Ξ( ) corresponds to a parameterized GO
S B ( g 1 , ..., g n )=B S1( g 1 ), ..., S n ( g n ) ,
(
Si , i J n of the given structure. For fixed generalized variables g i gˆ i , i J n the point gˆ ( gˆ 1 , ..., gˆ n ) Ξ( ) defines an image of a complex object S B ( gˆ 1 , ..., gˆ n ) B S1( gˆ 1 ), ..., S n ( gˆ n ) .
On the basis of the above typology, taking into account equation (
For example, for a 3D object, such fields will have three coordinates of the translation vector and three turning angles. The descendants, implementing complex objects form the next level. Each of them contains information about the metric parameters of this type of object and implements the necessary methods. The complex object will contain information about the set of objects of the corresponding space and the implementation of the methods that will be applied to each element of this set.
In general, the spatial configuration of a GO must satisfy a system of constraints that allow us to distinguish the corresponding class of spatial configurations. Such restrictions are due to the fact that the objects that make up the spatial configuration are different. Methods of formalizing such relationships depend on the choice of generalized variables of the configuration space, on the relative position restrictions of the GO and their physic mechanical properties (see Fig. 3).
Usually an additional object S0 is used, called a container. In this case, all objects Si , i J n must belong to the container S0 . We introduce on the set of objects the binary relation of inclusion . We will assume that S S , if int S S .
Let the object S0 in the configuration space Ξ( S0 ) have generalized variables g 0 . We form the configuration space Ξ( S0 ) Ξ( ) . Then the set of generalized variables ( g 0 , g 1 , ..., g n ) Ξ( S0 ) Ξ( ) specifies the packing configuration, if S j ( g j ) S0 ( g 0 ) , Si ( g i ) S j ( g j ) for any i, j J n , i j . Note that in this case, the pole and its own coordinate system of the object S0 coincides with the beginning and the axes of the fixed coordinate system, and the placement parameters of the container are p 0 ( 0, ...,0 ) .
Generalized configuration variables g 0 , g 1 , ..., g n of the configuration space Ξ( S0 ) Ξ( ) may be subject to additional constraints that create special classes of packing configurations, including layout configuration, in the case of restrictions on the minimum and the maximum admissible distances between objects. In the case of objects representing solids Si , i J n , of given masses qi , i J n , a balanced system of such bodies defines a configuration of the balanced packing configuration. If the poles of the objects Si , i J n coincide with the centers of their masses, balanced packing takes place under condition
In accordance with (
S B ( g 1 , ..., g n )= i1 n
Si ( g i ) in configuration space Ξ( ) .
Then the set of generalized variables ( g 0 , g 1 , ..., g n ) Ξ( S0 ) Ξ( ) specifies the covering configuration, if S0 ( g 0 ) S B ( g 1 , ..., g n ) . Objects S0 , Si , i J n are called the coverage domain and covering objects, respectively.
We note some papers devoted to the study of spatial configurations of packing [4, 5, 7–11], layout [12–16], balanced packing [17,18] and covering [19–21]. In the case when both metrical and placement parameters of GO take discrete values, we have a class of combinatorial configurations. Since, in this case, combinatorial objects are characterized by the vector of their generalized variables, when they are mapped into Euclidean space, so-called Euclidean combinatorial configurations are formed, the properties of which are described in [22-24].
To formalize constraints in packing and layout problems with fixed sizes and shapes of objects, Yu.G. Stoyan developed the theory of Φ-functions. The study of spatial configurations and the corresponding configuration spaces allows generalization of the Φ-function concept to the case of variable metric parameters GO. The analysis of existing methods for constructing the Φ-function for basic 2D and 3D objects allowed us to naturally transfer known results to the class of packing and layout problems with variable metric parameters of objects. For an analytical description of the coverage conditions, a special class of -functions was proposed in [25]. 3
Informational and Analytical Models Synthesis of Optimal Configurations Taking into account the object-oriented model of GO and methods of their relationships modeling, an information-analytical model of the process of spatial configurations synthesis is presented (see Fig. 4).
Depending on the quality criteria and the choice of specific constraints that form the set of admissible spatial configurations, the task of finding optimal configurations can be attributed to the corresponding class of mathematical programming problems.The corresponding process of synthesis of optimal configurations is presented in Fig. 5.
On the one hand, methods of solving such problems can be implemented independently of the subject area. From the mathematical point of view, it is enough to formalize the target function, functional constraints, Jacobi and Hesse matrices to find local extremum. In this case, the development of modern information technology for the synthesis of optimal configurations of complex systems requires the construction of their information-analytical models in the automatic mode. On the other hand, the considered problems belong to the class of NP-complete, with a high dimension are multyextremes. Thus, the synthesis of optimal configurations is a creative intellectual process that makes it possible for the decision maker to be involved.
The practice of using existing software packages to solve optimization tasks requires the construction of information-analytical models in a certain format with the help of external methods developed by the user. The available software leaves stage of the model construction the non-automated, which makes it urgent to search for new computer technologies for modeling problems in various technical fields and to develop information technologies for the transformation and visualization of geometric information in the process of synthesizing optimal configurations of complex systems.
3D visualizing of the solution process on each iteration is an important and rather difficult task, so it makes sense to use special software packages for this. For each iteration, excluding display intermediate solutions, the user according to the given parameters can influence the optimization process itself by changing the generalized variables of the model. Such changes may make the spatial configuratiothe inadmissible. However, in accordance with the proposed technology, a locally optimal configuration is automatically synthesized that satisfies all the requirements. Data exchange in the implementation of this technology using a special consolidated data warehouse is shown in Fig. 6.
The process of synthesis of spatial configurations is accompanied by multiple transformations of data of GO. In the analysis of the obtained results, detection, processing and transformation of suitable for use of the formed GO, formalized constraints and object function are performed. When using traditional tools, redundant data volumes arise and it need significant resources to perform their transformation.
Conclusions The spatial configurations synthesis problem is so complex that it cannot be solved automatically and requires integration of different information technologies, including those involving the decision maker. This combination of different technologies is impossible without the use of information technologies related to the storage and transformation of data in different formats. To successful use of information technologies the paper formalizes the concept of geometric information and obtained its structure.
The configuration space of geometrical object was built generated by the
parameters of geometric information. Depending on the type of geometric objects, the type of
constraints and the function of the target, various spatial configurations were
identified and analyzed. Their features were taken into account when implementing the
method of solving a problem based on the use of information technologies. A general
solution scheme was proposed and a consolidated database was developed, which
allows combining various existing software packages and original elements in the
process of solution. It is shown information technology using for exchanging of
information between the original software components and specialized software
systems, visualization both final and intermediate solution results, carrying out an
interactive search for solutions.
11. Yakovlev, S.V.: Тhe method of artificial space dilation in problems of optimal packing of
geometric objects. Cybernetics and Systems Analysis, vol. 53 no. 5, pp. 725-732 (2017).
12. Sun, Z.-G., Teng, H.-F.: Optimal layout design of a satellite module. Engineering
Optimization, vol. 35(
European Journal of Operational Research, vol. 248 (
Energomashinostroenie, no. 2, pp. 4–5 (1982).
19. Stoyan, Yu.G., Patsuk, V.M.: Covering a convex 3D polytope by a minimal number of
congruent spheres. International Journal of Computer Mathematics, vol. 91(
Hungarica, vol. 53(
Springer Optimization and its Applications, vol. 130, pp. 567-584 (2017).
23. Yakovlev, S.V., Pichugina, O.S.: Properties of combinatorial optimiztion problems over
polyhedral-spherical sets. Cybernetics and Systems Analysis, vol. 54(