Method of defining region of allowed configurations in multidimensional space of generalized coordinates using hypercube graph

The work is devoted to the development of a knowledge base on possible positions of an android arm mechanism with allowance for the position of the previously known forbidden zone. The knowledge base is used for intelligent control of the arm movement of an android robot that functions autonomously in an organized space without human-operator assistance. The specified knowledge base is determined by the region of allowed configurations in the multidimensional space of generalized coordinates. Based on the methods of geometrical modeling, a representation method of the allowable configuration region with the use of hypercube graph is proposed.


Introduction
A large number of studies are devoted to the problem of creating intelligent robots [1,2]. In solving this problem, computer virtual simulation of mechatronic object movements in organized environments is an important tool for analyzing and verifying the efficiency of the proposed algorithms for automatic control of manipulator mechanisms. One of the problems in developing intelligent control systems is to meet the requirements when collisions of the manipulator mechanism with the environment are absent [3][4][5][6]. These requirements are determined by the specified safe distance to the forbidden zones when a manipulator mechanism moves. This paper presents the results of studies on the determination of the set of allowed android arm configurations that meet the specified requirements. For this purpose, the varieties of points designated by the region Λ of the multidimensional space of generalized coordinates are determined, these points assigning configurations that satisfy the limit values of the generalised coordinates and the conditions of nonintersection with the forbidden zones. The robot control system should contain knowledge base about regions Λ for various forbidden zones that are known in advance. First it is necessary to create this base of knowledge that characterizes the property of maneuverability of the arm mechanism with allowance for forbidden zones, and then it may be used in synthesis of movements in the velocity vector in organized environment [7][8][9][10]. Defining the regions Λ is necessary for searching configurations that do not intersect forbidden zones. The creation of this knowledge base is quite a time-consuming task, as it is obtained as a result of processing a large array of points in a multidimensional space of generalised coordinates, taking into account the kinematic and geometric parameters of the investigated robot mechanism and the parameters of the shape and position of forbidden zones.

Problem Statement
In this paper a method for specifying the region Λ and on its basis the knowledge base of the robot using a graph of hypercubes is proposed. Figure1shows the kinematic diagram of the arm mechanism of the android robot AR-600E and the position of the forbidden zone P. The height of the base point A of the forbidden zone for the considered example in the coordinate system O o is equal to z op = 400 mm, the minimum safe offset of the manipulator base plate from the obstacle is equal to x op = 450 mm (Fig.  1).

Figure 1. Kinematic diagram of the android arm mechanism AR-600Е
The parameter z p = 100 mm determines the height of the forbidden zone (tool rack). Geometric parameters of the arm mechanism are specified in [7]. In the figure, the generalised coordinates are indicated by q i . The points O 1 -O 12 assign the coordinate origins used for specifying the kinematic chain model of the android arm mechanism. In order to determine the region of allowed configurations , taking into account the position of the forbidden zone P, in the work [7] a set of two-dimensional sections of the specified region in the four-dimensional generalised coordinate space is constructed. Particular positions of the arm mechanism links are investigated when q 1 = 0. The forbidden zone P, assigned by two horizontal and one profile planes of level Δ, Δ / and  (Fig. 2), defines in the space of generalized coordinates L q a certain region of the allowed configurations (RAC) Λ. A method for calculating the cross-section points of RAC to create a knowledge base about the past experience of motion synthesis in relation to the manipulator mechanism of a mobile robot was previously proposed in [8 -10]. In the work [7], a cross section representation method of the region Λ using a set of triangles is developed. However, the accuracy of the Λ region representation by this method requires further research in this field.
The operation of the manipulator mechanism takes place within a limited region  (four-dimensional space of generalised coordinates L q at q 1 = 0). Region  in a general case specified by hyperparallelepiped is that for any value of the vector q (q 2 , ..., q 5 ), specifying a point of the hypercube, the inequalities are satisfied: where min i q max i q are the lower and upper limits of generalised coordinates values. For this example, if q 1 = 0, the values of the parameter i satisfy the conditions 2 ≥ I ≥ 5. The values q i min and q i max for the mechanism of the android robot are respectively assumed to be equal to q i min (0 о , -25 о , -120 о , -120 о ) and q i max (120 о , 120 о , 120 о , 120 о ).

Theoretical Basis
The graph shown in figure 3 is used to assign the region Λ. Each node of this graph, which assigns hypercubes 1 1 at certain levels, allows specifying only such configurations of the android robot arm that satisfy the specified conditions of non-intersection with the forbidden zones. The advantages of the presented method of assigning the sets Λ compared with the known ones, are as follows: as a result of representation of the generalized coordinates space by elementary cells, it is possible to work not only with convex, but also with non-convex and composite geometric objects that define the region Λ; the method of studying the multidimensional space of generalized coordinates for the membership of arbitrary points in the regions Λ can significantly speed up the procedure for determining the conditions of non-intersection of the mechanism and the forbidden zones.
Let us note the main stages in the operation of this algorithm, in which the representation of the regions Λ of the multidimensional space L q is performed using a hypercube graph.
At the first step, the volume of the investigated multidimensional space L q is specified by a pdimensional hypercube. The side dimension of the hypercube (Fig. 4) is determined based on the ratio P p = 2q i max , where the parameter q i max is assigned in accordance with the specified limit values of the generalized coordinates q i max and q i min . The points Q p (φ 1k , φ 2k , ..., φ nk ) calculated according to a certain mesh step and belonging to a specified hypercube P p are checked for the condition of belonging to the set Λ. The values of the parameters q i , which specify points Q Λ , are found on the ratios q it = q it -1+q i maх , where q it are the values of the parameters q i at the current step t of the calculation, q it -1 is the value of the parameter q i at the previous step of the calculation, q i max is the maximum, originally adopted, increment of the parameters q i (Fig. 4). For the considered example q i max = 240•.
If one of the points Q Λ , represented in figure 4 by circles, turns out to belong to the set Λ (i.e. this point satisfies the conditions of non-intersection with forbidden zones), the space of the hypercube P p is divided into 2p p-dimensional hypercubes. The dimensions of new hypercubes P p /2 in this case are decreased, respectively, by a factor of two (Fig. 4)  The partition into hypercubes Р р /2 and examination of their points for membership to the set Λ occur as long as q max /2 > q min . Whereq min is specified initially. The parameter Δq min specifies the minimum mesh step in the study of points Q Λ , which is assumed to be Δq min = 20 o in this work.
Next, the hypercubes connection graph containing points Q p Λ is constructed (in general, the point O q , which defines coordinate origins of the space L q , may not belong to the region Λ). Note that if the points located on the boundaries of hypercubes belong to the set Λ, then the points of the boundary hypercubes are also investigated. The minimization of the computational time is achieved by excluding from the next calculation step those hypercubes describing the regions of the L q space in which the Q p  Λ points were not found at the current calculation step. In this context, this method of calculation allows us to study the region Λ at relatively small values of the parameter Δq min in less time.
The set of points Q p  Λ, which satisfies the conditions of non-intersection of configurations and forbidden zones, will determine the region Λ (Fig. 2). Defining the regions Λ is necessary for searching android arm configurations that do not intersect the forbidden zones. The found region Λ contains all possible values of the vector of generalized coordinates that meet the requirements of nonintersection of the arm mechanism with the forbidden zone.

Experimental Results
The set of sections of the allowed configurations region and their analytical assignment in the form of a hypercube graph is determined in advance based on the known forbidden zone position (for example, tool racks) and geometric and kinematic parameters of the arm mechanism. The region Λ defines the knowledge base and the model of the working environment. Based on the use of the Λ region, it is possible to create an algorithm to predict the development of events when the robot arm performs motor tasks. The algorithm for calculating the trajectory of the mechanism in the space of generalized coordinates using the construction of movements in the velocity vector and the region Λ is presented in [9]. The method of calculating the increments vector of generalized coordinates (the method of movement synthesis in the velocity vector) based on the use of matrices of partial gear ratios is described in [10]. The prediction of various situations when the manipulator moves is solved in paper [9] through the use of the mapping scale of the increment vector of the generalized coordinates, and the analysis of the trajectory position relative to the region Λ. Figure

Results Discussion
A more efficient way of finding the values of the generalized coordinate vector in the multidimensional space of generalized coordinates by traversing the nodes of a hypercube graph is proposed. Selection of nodes of this graph that define hypercubes 1 1 (Fig. 3) allows one to specify only such configurations of the android robot arm that do not intersect the forbidden zones.
The advantages of the presented method of assigning the regions Λ compared with the known ones, are as follows: as a result of description of the generalized coordinates space by elementary cells, it is possible to work not only with convex, but also with non-convex and separate regions Λ; the method of investigation of the multidimensional space of generalized velocities allows one to significantly speed up the procedure for determining the membership of an arbitrary point of the multidimensional space of generalized coordinates to the region Λ.
The region Λ for the android arm performing the movement in the specified velocity vector of OL is defined. It is proved that Λ regions can consist of separate subregions containing points Q  .