When developing algorithms for real-time robot path planning, the problem of performance limitations of the corresponding classical algorithms arises. This paper considers a method for planning robot movements in a two-dimensional complex conflict environment. For planning in complex environments, a hybrid planning algorithm is proposed, based on a combination and synthesis of the classical cellular decomposition algorithm and a recently proposed algorithm based on the characteristic visibility graph. This algorithm involves a preliminary analysis of the complexity of the obstacle scene, based on the results of which one of the two specified particular algorithms is selected. It is shown that this approach can significantly overcome the limitations of both of these algorithms. A disturbance avoidance method based on the apparatus of characteristic probability functions is described in a compact form, and its relationship with planning methods in complex environments is demonstrated when solving corresponding problems of global optimization of the probability of successful completion of a target trajectory. The developed approach examines the relationship between the probability of successful path completion in a source field and the corresponding risk function. To solve global robot motion planning problems in complex conflict environments, the proposed hybrid algorithm is first proposed for constructing a family of initial curves within the appropriate feasible motion corridors, ignoring sources. A family of local optimization problems is then solved within the feasible motion corridors, taking sources into account. Next, the trajectory with the maximum probability of successful completion or the normalized safe motion function is selected
The article discusses new algorithm to increase the efficiency of the operation of multiplying a matrix Kronecker product (KP) by a vector. It is based on the use of the KP properties. This operation is widely used in solving problems of processing signals, images, cryptography, etc., where the formation of large matrices with specified properties is performed using small size matrices. In this case, matrices with the following properties are used: orthogonal (unitary), invertible, involutive. Multiplying an n × n square matrix by a vector has a computational complexity of O(n2). Therefore, with an increase in the number of elementary matrix factors, the size of the resulting KP matrix and the complexity of multiplying it by a vector grow exponentially. This circumstance significantly increases the time for solving applied problems. The aim of the proposed work is to construct an algorithm that accelerates the processes of forming the KP and multiplyingthe vector by it. It is proposed to combine the process of multiplication with the process of forming the KP. Thus, the KP matrix is not actually calculated explicitly. Instead, the KP factor matrices are iteratively multiplied by the vector components in O(nlog2n) time with linear memory complexity. The computational scheme with the hypercube topology for the possible hardware implementation of the proposed algorithm is presented. It can be easily pipelined. Section 1 presents the definitions and properties of the KP used in the synthesis of the proposed algorithm. Section 2 presents an example with n = 8 illustrating the proposed algorithm, on the basis of which, in Section 3, a hardware-oriented structure of its implementation for arbitrary n is proposed.
