Все выпуски

Рассматривается линейная нестационарная дифференциальная игра преследования группы убегающих группой преследователей. Цель преследователей - поймать всех убегающих, цель убегающих - хотя бы одному уклониться от встречи. Все игроки обладают равными динамическими возможностями, геометрические ограничения на управление - строго выпуклый компакт с гладкой границей.

Рассматривается вопрос о минимальном количестве убегающих, достаточном для уклонения от заданного числа преследователей из любых начальных позиций. Для оценки сверху этого количества используются достаточные условия разрешимости глобальной задачи уклонения. В предположении, что для поимки одного убегающего достаточно принадлежности начальной позиции убегающего внутренности выпуклой оболочки начальных позиций преследователей, строится оценка снизу.

Полученная двухсторонняя оценка числа убегающих, достаточного для уклонения от встречи из любой начальной позиции от заданного числа преследователей, иллюстрируется примерами.

A linear non-stationary differential pursuit game with a group of pursuers and a group of evaders is considered. The pursuers' goal is to catch all evaders and the evaders' goal is at least for one of them to avoid contact with pursuers.

All players have equal dynamic capabilities, geometric constraints on the control are strictly convex compact set with smooth boundary. The point in question is the minimum number of evaders that is sufficient to evade a given number of pursuers from any initial position. Sufficient conditions for the solvability of the global problem of evasion are used as an upper estimate of this minimum. We assume that to capture one evader it suffices that the initial position of this evader lie in the interior of convex hull of initial positions of pursuers. Using this assumption we find a lower estimate of this minimum.

The obtained two-sided estimate of the number of evaders sufficient to avoid contact with a given number of pursuers from any initial position is illustrated by examples.

Работа посвящена исследованию равновесия по Нэшу в неантагонистической детерминированной дифференциальной игре двух лиц в классе рандомизированных стратегий. Предполагается, что игроки информированы об управлении своего партнера, реализовавшегося к текущему времени. Поэтому игра формализуется в классе рандомизированных квазистратегий. В работе получена характеризация множества выигрышей (пар ожидаемых выигрышей игроков) в ситуациях равновесия по Нэшу с использованием вспомогательных антагонистических игр. Показано, что множество выигрышей в ситуациях рандомизированного равновесия по Нэшу является выпуклой оболочкой множества выигрышей в классе детерминированных стратегий. Приведен пример, показывающий дополнительные возможности, которые возникают при переходе к рандомизированным стратегиям.

The paper is concerned with the randomized Nash equilibrium for a nonzero-sum deterministic differential game of two players. We assume that each player is informed about the control of the partner realized up to the current moment. Therefore, the game is formalized in the class of randomized non-anticipative strategies. The main result of the paper is the characterization of a set of Nash values considered as pairs of expected players' outcomes. The characterization involves the value functions of the auxiliary zero-sum games. As a corollary we get that the set of Nash values in the case when the players use randomized strategies is a convex hull of the set of Nash values in the class of deterministic strategies. Additionally, we present an example showing that the randomized strategies can enhance the outcome of the players.

Для динамической системы, подверженной воздействиям управления и помехи и содержащей последействие в управляющих силах, рассматривается задача об управлении с оптимальным гарантированным результатом для показателя качества, представляющего собой евклидову норму совокупности отклонений движения системы в заданные моменты времени от заданных целей. На основе функциональной трактовки, опирающейся на своеобразный прогноз движений, исходная задача сводится к вспомогательной дифференциальной игре для системы без запаздывания и с терминальной платой. Функция цены этой игры вычисляется на базе конструкции выпуклых сверху оболочек вспомогательных функций из метода стохастического программного синтеза, оптимальные стратегии строятся методом экстремального сдвига на сопутствующие точки. Рассматриваются иллюстрирующие примеры, приводятся результаты численных экспериментов.

For a dynamical system under control and disturbances, and with delay in control, the problem of control with the optimal guaranteed result is considered for a quality index which is the Euclidean norm of the set of deviations of a system motion at the given instants from the given targets. On the basis of a functional treatment basing on a proper prediction of the motion the problem is reduced to an auxiliary differential game for a system without delay and with a terminal quality index. The value of this game is calculated from the construction of upper convex hulls of auxiliary functions from the method of stochastic program synthesis, optimal strategies are formed by the method of an extremal shift to the corresponding points. Illustrating examples and results of numerical experiments are presented.

Рассматривается задача построения вершинного описания выпуклого полиэдра, заданного как множество решений некоторой системы линейных неравенств, коэффициенты которой являются алгебраическими числами. Обратная задача эквивалентна (двойственна) исходной. Предлагаются программные реализации нескольких модификаций хорошо известного метода двойного описания (метода Моцкина-Бургера), решающего поставленную задачу. Рассматривается два случая: 1) элементы системы неравенств - произвольные алгебраические числа, при этом каждое такое число задается минимальным многочленом и локализующим интервалом; 2) элементы системы неравенств принадлежат заданному конечному расширению ${\mathbb Q} (\alpha)$ поля ${\mathbb Q}$, при этом для $\alpha$ задаются минимальный многочлен и локализующий интервал, а все элементы исходной системы, конечные и промежуточные результаты представлены как многочлены от $\alpha$. Как и ожидалось, программная реализация для второго варианта значительно превосходит реализацию для первого варианта по производительности. Для большего ускорения во втором случае предлагается использовать булевы матрицы вместо матриц невязок. Результаты вычислительного эксперимента показывают, что программные реализации вполне пригодны для решения задач умеренных размеров.

We consider the problem of constructing the dual representation of a convex polyhedron defined as a set of solutions to a system of linear inequalities with coefficients which are algebraic numbers. The inverse problem is equivalent (dual) to the initial problem. We propose program implementations of several variations of the well-known double description method (Motzkin-Burger method) solving this problem. The following two cases are considered: 1) the elements of the system of inequalities are arbitrary algebraic numbers, and each such number is represented by its minimal polynomial and a localizing interval; 2) the elements of the system belong to a given extension ${\mathbb Q} (\alpha)$ of ${\mathbb Q}$, and the minimal polynomial and the localizing interval are given only for $\alpha$, all elements of the system, intermediate and final results are represented as polynomials of $\alpha$. As expected, the program implementation for the second case significantly outperforms the implementation for the first one in terms of speed. In the second case, for greater acceleration, we suggest using a Boolean matrix instead of the discrepancy matrix. The results of a computational experiment show that the program is quite suitable for solving medium-scale problems.

Рассматривается антагонистическая линейно-выпуклая дифференциальная игра с показателем качества, оценивающим совокупность отклонений траектории движения в наперед заданные моменты времени от заданных целевых точек. Исследуется случай, когда не выполняется условие седловой точки в маленькой игре, также известное как условие Айзекса. Игра формализуется в классах смешанных стратегий управления игроков. Описывается численный метод для приближенного вычисления цены игры и построения оптимальных стратегий. Метод основывается на попятном построении выпуклых сверху оболочек вспомогательных программных функций. Приводятся результаты численных экспериментов на модельных примерах.

A zero-sum linear-convex differential game with a quality index that estimates a set of deviations of a motion trajectory at given instants of time from given target points is considered. A case when the saddle point condition in a small game, also known as Isaac's condition, does not hold, is studied. The game is formalized in classes of mixed control strategies of players. A numerical method for approximate computation of the game value and optimal strategies is elaborated. The method is based on the recurrent construction of upper convex hulls of auxiliary program functions. The results of numerical experiments in model examples are given.

Для игровой задачи удержания траекторий абстрактной динамической системы в заданном множестве исследуются соотношения метода программных итераций и конструкций, связанных с построением операторно выпуклой оболочки множества посредством предоболочки. В рамках данных соотношений процедура построения упомянутой оболочки реализуется в форме, двойственной по отношению к процедуре на основе метода программных итераций. Решение задачи удержания определяется в классе многозначных квазистратегий (неупреждающих откликов на реализации неопределенных факторов процесса). Показано, что множество успешной разрешимости задачи удержания определяется в виде предела итерационной процедуры на пространстве множеств, элементами которых являются позиции игры, а также установлена структура разрешающих квазистратегий.

For an abstract dynamic system the game problem of trajectories retention in a given set is considered. The relations of the method of programmed iterations and the constructions associated with the generation of the operator convex hull with the help of prehull are investigated. Within these relations the procedure of constructing the hull is realized in the form dual to the procedure based on the method of programmed iterations. The retention problem solution is determined in the class of multi-valued quasistrategies (nonanticipating responses to the realization of uncertain factors of the process). It is shown that the set of successful solvability of the retention problem is defined as the limit of the iterative procedure in the space of sets, elements of which are positions of the game; the structure of resolving quasistrategies is also provided.

Рассматривается конфликтное взаимодействие групп управляемых объектов. Цель группы преследователей - поймать, а группы убегающих - избежать поимки. Все игроки обладают равными динамическими возможностями. Движение игроков задается дифференциальным уравнением третьего порядка. Все убегающие используют одинаковое управление, поэтому о них можно говорить как о жестко скоординированных инерционных объектах. Доказано, что если выпуклые оболочки, натянутые на начальные ускорения группы преследователей и группы убегающих, не пересекаются, то происходит уклонение от встречи.

A conflict interaction of groups of controlled objects is considered. The pursuers' goal is to catch, and the evaders' goal is to avoid contact with pursuers. All players have equal dynamic capabilities. Players' motion is defined by a third order differential equation. All evaders have equal control, therefore they can be considered as rigidly coordinated inertial objects. It is proved that if the convex hull spanned by pursuers' initial acceleration vector is not intersected with the convex hull spanned by evaders' initial acceleration vector, then the evasion is possible.

Приводится понятие $\alpha$-множества в конечномерном евклидовом пространстве, являющееся одним из обобщений понятия выпуклого множества. Возникновение этого понятия связано с изучением свойств множеств достижимости нелинейных управляемых систем. В работе определяется числовая характеристика степени невыпуклости множества, на основе которой осуществляется классификация множеств. Вводятся в рассмотрение аналоги базовых понятий из выпуклого анализа и изучаются их свойства. Формулируются и доказываются утверждения в духе таких теорем из выпуклого анализа, как теорема о существовании опорной гиперплоскости к выпуклому множеству и теоремы об отделимости выпуклых множеств в евклидовом пространстве. Изучается понятие мажорируемости невыпуклых множеств. Свойство мажорируемости является достаточным условием для представления замкнутого невыпуклого множества в виде пересечения полупространств в смысле введенных в работе определений. Полученные результаты теории отделимости невыпуклых множеств распространяются на случай подграфиков и надграфиков скалярных функций, удовлетворяющих условию Липшица.

The concept of $\alpha$-set in a finite-dimensional Euclidean space, which is one of generalizations of the notion of a convex set, is introduced. The emergence of this concept is connected with the study of properties of attainability sets of nonlinear controlled systems. The numerical characteristic of nonconvexity degree of a set on the basis of which a classification of sets is carried out is defined in the paper. Analogs of basic concepts from the convex analysis are introduced into consideration and their properties are studied. Statements in the spirit of such theorems from the convex analysis as the theorem of existence of basic hyperplane to a convex set and theorems of separability of convex sets in Euclidean space are formulated and proved. The concept of magoriums of nonconvex sets is studied. Property of a magoriums is a sufficient condition for representation of a closed nonconvex set in the form of crossing of half-spaces in the sense of definitions entered in this work. The obtained results of the theory of separability of nonconvex sets can be extended on a case of hypograph and epigraph of the scalar functions with Lipschitz condition.