The RUDN University scientist compared the performance of several algorithms to solve the optimal control problems that arise all over, from economics to cosmonautics. The results are published in the journal Applied Sciences.
Systems of several objects with an assigned sequence of actions are described with what is called an optimal control problem. They arise, for example, in the control of a spacecraft or the management of a country’s tax system. Mathematically, this means minimizing or maximizing certain parameters of the system (for example, minimizing time or maximizing employment). There is no generally accepted universal way to digitally analyze such systems, but there are many approaches and algorithms. Researchers from RUDN University and the Federal Research Center “Computing and Control” of the Russian Academy of Sciences have proposed two approaches based on several modern computer algorithms to solve the problem of optimal control of a group of robots.
“A group of robots must go from given initial states to terminal states while avoiding obstacles in the shortest possible time. The problem belongs to the class of optimization in infinite dimension. There are two approaches to solve it numerically. A direct approach is based on a discretization of the control function and a reduction to finite dimensional optimization. An indirect approach is based on the principle of the Pontryagin maximum for the transition to the limit value problem and its numerical solution, ”said Sergey Konstantinov, lecturer at the department of mechanics and control at RUDN University.
Scientists have proposed two approaches to solve the optimal control problem based on direct methods. In a test, the robots must move from the starting point to the end point and not collide with obstacles and other robots. In the first approach, a group of robots was considered as a single object. In this case, the optimal control problem is reduced to a nonlinear programming problem. This means that it cannot be reduced to a system of linear equations, which complicates the problem. In the second approach, they first find attractors for each robot – special points on the plane, which “tell” the robot how to avoid obstacles on the way. The results obtained were then used to solve the whole of the initial problem. Calculations based on two approaches have been implemented using evolutionary algorithms and the random search method. The researchers performed 10 tests for each of the four evolutionary algorithms and the random search method and compared their performance.
The efficiency of two approaches and 5 algorithms (the random search method and 4 evolutionary algorithms: genetic algorithm, particle swarm optimization, bee algorithm and gray wolf optimizer) was evaluated. based on the value of the objective function – the function that is to be minimized in the optimal control problem. The smaller it is, the better the algorithm is executed. For the first approach, all evolutionary algorithms have been shown to be more efficient than the random search method. Optimization of the particle swarm gave the best results, with an average value of 5.5 for the objective function. For the random search method, this value was almost three times as high – 15.83. For the second approach, the random search method was also found to be the least efficient. Evolutionary algorithms worked about as efficiently. In one of the tests, the gray wolf optimizer gave the minimum value of the objective function – 2.49.
“Currently, there are no universal numerical methods for solving optimal control problems. We plan to continue the study of evolutionary algorithms and consider other new evolutionary algorithms, including hybrid algorithms,” said Sergey Konstantinov, lecturer in the department of mechanics and mechatronics of RUDN University.