1,720,966 research outputs found
Construction of pursuit strategies with using Lyapunov functions
No full textThis paper is concerned with differential pursuit-evasion games, in which several agents chase one. The time of capture of a target is used as the criterion. The motion of agents is simple one, the velocities are piecewise-continuous. The function that specifies the maximal time of capture of the target for the well-known strategy of parallel approach is described. This function is used as a Lyapunov function for constructing the new chase strategy, which outperforms the strategy of parallel approach in the following sense. Maximal time of pursuit for the new strategy is not more than maximal time of pursuit for the strategy of parallel approach; at the same time there are many games, for which maximal time of pursuit for the new strategy is less than for the strategy of parallel approach. In case of pursuit-evasion game on a plane we find explicit form of Lyapunov function and calculate velocities of pursuers using the gradient of this function. Numerical examples show that such velocities of pursuers reduce the maximal time of pursuit. In case of pursuit-evasion game in a multidimensional Euclidean space, Lyapunov function is equal to an optimal value of an objective function of appropriate linear programming problem. The velocities of pursuers are calculated with using the gradient of this function.Problems in programming 2017; 3: 194-21
Про оптимальне керування в системі "хижак-жертва"
Full text linkWe consider the system of Lotka-Volterra differential equations with two control variables and describe an optimal control, which provides a transition to a stationary point in a minimum time. We also found an optimal control for the limit case, on condition that the phase trajectories are located near a stationary point. Optimal trajectories of motion in the phase space are constructed; they look like spirals.Problems in programming 2020; 2-3: 287-294Рассматривается система дифференциальных уравнений Лотки-Вольтерры с двумя переменными управления. Описано оптимальное управление, обеспечивающее переход к стационарной точке за минимальное время. Найдено также оптимальное управление в предельном случае, при условии, что фазовые траектории расположены вблизи стационарной точки. Построены оптимальные траектории движения в фазовом пространстве, имеющие вид спиралей.Problems in programming 2020; 2-3: 287-294Розглядається система диференціальних рівнянь Лотки-Вольтерри з двома змінними керування. Описано оптимальне керування, яке забезпечує перехід до стаціонарної точки за мінімальний час. Знайдено також оптимальне керування в граничному випадку, за умови, що фазові траєкторії лежать поблизу стаціонарної точки. Побудовано оптимальні траєкторії руху у фазовому просторі, що мають вигляд спіралей.Problems in programming 2020; 2-3: 287-29
Optimal placement of a multi-sensor system
No full textWe consider the mathematical models for underwater acoustic sensors, the algorithm for threat detection by a multisensory system, optimization problems for placement of such systems. The mathematical methods for optimal sensor placement have been developed. The limit theorem on optimality of sensor placement has been proved. Numerical experiments have demonstrated that the algorithm outperformsexisting mathematical method for optimal sensor placement.Problems in programming 2018; 2-3: 140-14
Оптимальне розміщення багатосенсорної системи
Full text linkWe consider the mathematical models for underwater acoustic sensors, the algorithm for threat detection by a multisensory system, optimization problems for placement of such systems. The mathematical methods for optimal sensor placement have been developed. The limit theorem on optimality of sensor placement has been proved. Numerical experiments have demonstrated that the algorithm outperformsexisting mathematical method for optimal sensor placement.Problems in programming 2018; 2-3: 140-148Описан алгоритм детектирования подводной угрозы с помощью системы акустических сенсоров, а также экстремальные задачи размещения сенсоров. Рассмотрены методы решения таких задач, доказана теорема об асимптотической оптимальности построенных планов размещения сенсоров. Из результатов численных экспериментов следует, что построенный метод превосходит известный метод решения задач размещения сенсоров.Problems in programming 2018; 2-3: 140-148Описано алгоритми детектування підводної загрози за допомогою системи акустичних сенсорів, екстремальні задачі розміщування сенсорів. Розглянуто методи розв’язання таких задач та теореми про асимптотичну оптимальність побудованих планів розміщення сенсорів. З результатів числових експериментів випливає, що побудований метод перевершує відомий метод розв’язання задачрозміщування сенсорів.Problems in programming 2018; 2-3: 140-14
About an optimal control for a "predator-prey" system
No full textWe consider the system of Lotka-Volterra differential equations with two control variables and describe an optimal control, which provides a transition to a stationary point in a minimum time. We also found an optimal control for the limit case, on condition that the phase trajectories are located near a stationary point. Optimal trajectories of motion in the phase space are constructed; they look like spirals.Problems in programming 2020; 2-3: 287-29
Simulation of optimal pursuit strategies with simple motion
No full textStrategies for pursuit of a target by one pursuer with simple movement are considered. The criterion is the time to capture the target. The proof of the optimality of the parallel approach strategy and the chas- ing strategy is presented. The strategy of parallel approach consists in the fact that the pursuer, knowing the velocity vector of the target at current moment, considers this vector to be constant and calculates a point on the target’s line of motion at which capture can occur if the pursuer moves at a constant maxi- mum speed. At each instant of time, the pursuer’s velocity vector is directed to the capture point, and the magnitude of the velocity is maximal. If the pursuer moves at maximum speed in the direction of the target, the pursuit strategy is called a chasing strategy. A number of examples of pursuit using the strate- gies of parallel approach and chasing strategy, calculated by the numerical method, are given. The main parameters of the movement of the agents affecting the time of capture are determined: the speed of the target and the pursuer, the coordinates of the target and the pursuer at the time of the beginning of the pursuit, the type and parameters of the target’s movement line; the pursuit task is determined by these para-meters. On the basis of numerical modeling, a sets of problems is outlined for which the parallel approach strategy is better then the chasing strategy or vice versa. The selected movement parameters roughly correspond to the movement parameters of modern combat aircraft and air defense equipment; in numerical experiments, the absolute value of the acceleration of the target does not exceed 10g, where g is the accele-ration of free fall. Since the pursuer’s motion is considered simple, any absolute value of its acceleration is allowed. In the case of applying the parallel approach strategy, this value slightly differs from the absolute value of the target’s acceleration; if a chasing strategy is used, the absolute magnitude of the pursuer’s acceleration can be much larger.Prombles in programming 2022; 3-4: 478-48
Побудова стратегій переслідування з використанням функцій Ляпунова
Full text linkThis paper is concerned with differential pursuit-evasion games, in which several agents chase one. The time of capture of a target is used as the criterion. The motion of agents is simple one, the velocities are piecewise-continuous. The function that specifies the maximal time of capture of the target for the well-known strategy of parallel approach is described. This function is used as a Lyapunov function for constructing the new chase strategy, which outperforms the strategy of parallel approach in the following sense. Maximal time of pursuit for the new strategy is not more than maximal time of pursuit for the strategy of parallel approach; at the same time there are many games, for which maximal time of pursuit for the new strategy is less than for the strategy of parallel approach. In case of pursuit-evasion game on a plane we find explicit form of Lyapunov function and calculate velocities of pursuers using the gradient of this function. Numerical examples show that such velocities of pursuers reduce the maximal time of pursuit. In case of pursuit-evasion game in a multidimensional Euclidean space, Lyapunov function is equal to an optimal value of an objective function of appropriate linear programming problem. The velocities of pursuers are calculated with using the gradient of this function.Problems in programming 2017; 3: 194-211Рассматриваются дифференциальные игры преследования, в которых несколько агентов догоняют одного. Критерием является время захвата цели. Для известной стратегии параллельного сближения описана функция, задающая максимальное время преследования. Эта функция используется как функция Ляпунова для построения новой стратегии преследования, которая превосходит стратегию параллельного сближения в следующем смысле. Максимальное время преследования для построенной стратегии не превосходит максимального времени для стратегии параллельного сближения; вместе с тем существует значительное количество игр, в которых максимальное время преследования для новой стратегии оказывается меньшим, чем для стратегии параллельного сближения.Problems in programming 2017; 3: 194-211 Розглядаються диференційні ігри переслідування, в яких кілька агентів доганяють одного. Критерієм виступає час захоплення цілі. Для відомої стратегії паралельного зближення описана функція, що задає максимальний час переслідування. Ця функція використовується як функція Ляпунова для побудови нової стратегії переслідування, що перевершує стратегію паралельного зближення в наступному сенсі. Максимальний час переслідування для побудованої стратегії не перевищує максимального часу для стратегії паралельного зближення; водночас існує значна кількість ігор, в яких максимальний час переслідування для нової стратегії виявляється меншим, ніж для стратегії паралельного зближення. Problems in programming 2017; 3: 194-21
NP-hardness of collective pursuiting optimization problems
No full textThe differential pursuitevasion games on a plane are considered. A group of pursuers is created for every evader in a game. The optimization problem of group composition has been formulated. The theorems about NP-completeness and NP-hardness of pursuit optimization problems are proved. Numerical methods for solving such optimization problems are constructed. Numerical experiments have demonstrated high efficiency of the methods.Prombles in programming 2014; 2-3: 44-5
NP-трудность задач оптимизации коллективного преследования
Full text linkThe differential pursuitevasion games on a plane are considered. A group of pursuers is created for every evader in a game. The optimization problem of group composition has been formulated. The theorems about NP-completeness and NP-hardness of pursuit optimization problems are proved. Numerical methods for solving such optimization problems are constructed. Numerical experiments have demonstrated high efficiency of the methods.Prombles in programming 2014; 2-3: 44-51Рассмотрены игры преследования на плоскости с простым движением, в которых принимают участие несколько преследователей и убегающих. Для захвата целей множество преследователей разбивается на группы, причем для каждого убегающего создается одна группа. В качестве критерия используется время захвата. Доказаны теоремы о NP-трудности задач оптимизации групп преследования. Приведены результаты численных экспериментов для соответствующих версий метода ветвей и границ и метода случайного поиска с локальной оптимизацией.Prombles in programming 2014; 2-3: 44-5
- …
