Все выпуски

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

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

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

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.

Рассматривается задача уклонения убегающего от группы преследователей в конечномерном евклидовом пространстве. Движение описывается линейной системой дробного порядка вида $$\left({}^C D^{\alpha}_{0+}z_i\right)=A z_i+u_i-v,$$ где ${}^C D^{\alpha}_{0+}f$ - производная по Капуто порядка $\alpha\in(0,1)$ функции $f$, $A$ - простая матрица. В начальный момент времени заданы начальные условия. Управления игроков ограничены одним и тем же выпуклым компактом. Убегающий дополнительно стеснен фазовыми ограничениями - выпуклым многогранным множеством c непустой внутренностью. В терминах начальных позиций и параметров игры получены достаточные условия разрешимости задачи уклонения.

The paper deals with the problem of avoiding a group of pursuers in the finite-dimensional Euclidean space. The motion is described by the linear system of fractional order $$\left({}^C D^{\alpha}_{0+}z_i\right)=A z_i+u_i-v,$$ where ${}^C D^{\alpha}_{0+}f$ is the Caputo derivative of order $\alpha\in(0,1)$ of the function $f$ and $A$ is a simple matrix. The initial positions are given at the initial time. The set of admissible controls of all players is a convex compact. It is further assumed that the evader does not leave the convex polyhedron with nonempty interior. In terms of the initial positions and the parameters of the game, sufficient conditions for the solvability of the evasion problem are obtained.

Рассматриваются структурные, аппроксимативные и спектральные свойства нётеровых операторов индекса n и (−n), действующих между банаховыми пространствами B и D, где D изоморфно прямой сумме пространства B и конечномерного пространства E размерности n. Раскрыта роль теоремы С.М. Никольского о фредгольмовом операторе в изучении указанных свойств, а также в вопросе разрешимости уравнений с краевыми неравенствами. В случае сепарабельного гильбертова пространства B для однозначно разрешимых краевых задач предлагается основанная на разложении Э. Шмидта компактного оператора схема дискретизации, которая позволяет применить абстрактный вариант теоремы Рябенького–Филиппова о связи аппроксимации, устойчивости и сходимости.

There are considered the structural, approximated and spectral properties of Fredholm operators of index n and (−n), acting between Banach spaces B and D, where D is isomorphic to the direct sum of B and finite–dimensional space E of dimension n. There is demonstrated the role of S.M. Nikol’skii theorem on Fredholm operator in the study of these properties as well as in the issue of solvability equations with boundary inequalities. For boundary value problems which are uniquely solvable, in the case of a separable Hilbert space B, based on Schmidt decomposition for a compact operator a scheme of discretization is proposed, and it allows application of an abstract version of Ryaben’kii–Filippov theorem on the relationship of approximation, stability and convergence.

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

A controlled parabolic system that describes the heating of a given number of rods is considered. The density functions of the internal heat sources of the rods are not known exactly, and only the segments of their change are given. At the ends of the rods there are controlled heat sources and disturbances. The goal of the choice of control is to lead the vector of average temperatures of the rods at a fixed time to a given compact for any admissible functions of the density of internal heat sources and any admissible realizations of disturbances. After replacing variables, the problem of controlling a system of ordinary differential equations in the presence of uncertainty is obtained. Using a numerical method, a solvability set is constructed for this problem. Model calculations are carried out.

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

The paper is devoted to elaboration of polyhedral techniques for solving two control problems for linear discrete-time systems with uncertainties under state constraints, namely, the terminal approach problem and the terminal evasion one. Such problems arise in systems with two controls, where the aim of the first is to steer the trajectory onto a given terminal set at a given instant without violating the state constraints, the aim of the other is opposite. It is assumed that the terminal set is a parallelepiped, the controls are bounded by parallelotope-valued constraints, and the state constraints are given in the form of so-called zones. We present techniques for solving both problems basing on polyhedral (parallelotope-valued or parallelepiped-valued) tubes. The techniques for solving the approach problem were proposed by the author earlier, but here additional properties of them are investigated. In particular, for the case without state constraints, guaranteed estimates are found for the trajectory that ensure that it is inside the tube. Convenient sufficient conditions are given to guarantee the obtaining of nondegenerate cross-sections during the calculations. For the evasion problem, a common solution scheme is considered, and then polyhedral techniques are proposed. The whole parametric families of external and internal polyhedral estimates for the solvability tubes for both problems are presented and compared. An illustrative example is given.

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

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

The article is concerned with the procedure of insertion of optimizable fragments of route solutions into the global solutions of the «big» problem defined by heuristic algorithms. Setting of the route problem takes into account some singularities of the engineering problem about the sequential cutting of details each having one exterior and probably several interior contours. The latter ones must be subjected to cutting previously in comparison with the exterior contour, which leads to a great number of given preceding conditions. These conditions are actively used to decrease the computational complexity. Nevertheless, the problem dimensionality remains sufficiently large that does not permit to use “global’’ dynamic programming and forces heuristic algorithms to be used (the problem under investigation is a hard-solvable problem in the traditional sense). Therefore, it is interesting to develop the methods for correction of solutions based on the above-mentioned algorithms. In the present investigation, such correction is realized by the replacement of fragments (of the above-mentioned solutions) having a moderate dimensionality by optimal “blocks’’ constructed by dynamic programming with local preceding conditions which are compatible with the constraints of the initial “big’’ problem. The proposed replacement does not deteriorate, but, in typical cases, improves the quality of the initial heuristic solution. This is verified by the computing experiment on multi-core computer.

The proposed algorithm is realized in the iterated regime: the solution (in the form of “route-trace’’) obtained after the first insertion on the basis of dynamic programming is taken as an initial solution for which the insertion is constructed again. In addition, the beginning of the new insertion is chosen randomly in the bounds defined by the possibilities of formation of a sliding “window’’ of the appreciable dimensionality which is in fact sufficient for the employment of the economical version of dynamic programming. Further, the procedure is repeated. The operation of the iterated algorithm is illustrated by solution of model problems including the versions with sufficiently dense “packing’’ of parts on a sheet, which is typical for the engineering production.

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

In this paper, a class of linear functional differential systems with aftereffect, continuous and discrete times, and impulses (impulse hybrid systems) is considered. The focus of attention is on the structure of the Cauchy operator to the hybrid system under consideration and the representation of their components. Those allow one to give the representation of all trajectories of the hybrid system and to formulate conditions of the solvability for control problems in various classes of controls, to obtain estimates of the attainability sets under constrained control, and to study general linear boundary value problems for the solvability. A detailed description of all components to the Cauchy operator is given and their properties are studied. For the components with continuous time, some conditions of the continuity with respect to the second argument are obtained which is related to deciding on a class of controls. The main results are based on constructions of the Cauchy matrices to systems with continuous time and difference systems.

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

The problem of simple pursuit of one evader by the group of pursuers is studied, provided that among the pursuers there are both members, the maximum speeds of which coincide with the maximum speed of the evader, and participants whose maximum speeds are strictly less than the maximum speed of the evader, while the evader does not leave a convex polyhedral set. The conditions under which the pursuers with fewer capabilities do not affect the solvability of problem of evasion are obtained.

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

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.

В конечномерном евклидовом пространстве рассматривается задача преследования группой преследователей одного убегающего, описываемая системой вида $$D^{(\alpha)}z_i = a z_i + u_i - v,$$ где $D^{(\alpha)}f$ - производная по Капуто порядка $\alpha \in (0, 1)$ функции $f$. Дополнительно предполагается, что убегающий в процессе игры не покидает пределы выпуклого многогранного множества с непустой внутренностью. Убегающий использует кусочно-программные стратегии, преследователи - кусочно-программные контрстратегии. Множество допустимых управлений - выпуклый компакт, целевые множества - начало координат, $a$ - вещественное число. В терминах начальных позиций и параметров игры получены достаточные условия разрешимости задачи преследования.

In the finite-dimensional Euclidean space, we consider the problem of persecution of one evader by the group of pursuers, which is described by the system $$D^{(\alpha)}z_i = a z_i + u_i - v,$$ where $D^{(\alpha)}f$ is the Caputo derivative of order $\alpha \in (0, 1)$ of the function $f$. It is further assumed that the evader does not leave the convex polyhedron with nonempty interior. The evader uses piecewise-program strategies, and the pursuers use piecewise-program counterstrategies. The set of admissible controls is a convex compact, the target sets are the origin of coordinates, and $a$ is a real number. In terms of the initial positions and the parameters of the game, sufficient conditions for the solvability of the pursuit problem are obtained.