Все выпуски

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

A differential game of the group of persecutors and one escapee is considered at equal dynamic opportunities of all participants. Necessary and sufficient conditions for capture are received in the case where the escapee is constrained by phase restrictions.

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

A differential game of the group of persecutors and two evaders is considered at equal dynamic opportunities of all participants and under equal phase restrictions imposed on the states of evaders. Sufficient solvability conditions are derived proceeding on the assumption that the evaders use the same control.

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

The questions of constructing admissible controls in a problem of optimal control of a nonlinear dynamic system under constraints on its current phase state are discussed. The dynamic system under consideration describes the controlled motion of a carrier rocket from the launching point to the time when the carrier rocket enters a given elliptic earth orbit. The problem consists in designing a program control for the carrier rocket that provides the maximal value of the payload mass led to the given orbit and the fulfillment of a number of additional restrictions on the current phase state of the dynamic system. The additional restrictions are due to the need to take into account the values of the dynamic velocity pressure, the attack and slip angles when the carrier rocket moves in dense layers of the atmosphere. In addition it is required to provide the fall of detachable parts of the rocket into specified regions on the earth surface. For carrier rockets of some classes, such a problem is equivalent to a nonlinear time-optimal problem with phase constraints. Two algorithms for constructing admissible controls ensuring the fulfillment of additional phase constraints are suggested. The numerical analysis of these algorithms is performed. The methodological basis of one algorithm is the application of some predictive control, which is constructed without taking into account the constraints above. Another algorithm is based on special control modes. The results of numerical modeling are presented.

Рассматривается линейная задача преследования группой преследователей двух убегающих при равных динамических возможностях всех участников и с фазовыми ограничениями на состояния убегающих в предположении, что убегающие используют одно и то же управление. Движение каждого участника имеет вид $\dot z+a(t)z=w.$ Геометрические ограничения на управления - строго выпуклый компакт с гладкой границей, терминальные множества - начало координат. Предполагается, что убегающие в процессе игры не покидают пределы выпуклого конуса. Целью преследователей является поимка двух убегающих, цель группы убегающих противоположна. Говорят, что в задаче преследования происходит поимка, если существуют два преследователя, из заданной группы преследователей, которые ловят убегающих, при этом моменты поимки могут не совпадать. В терминах начальных позиций получены достаточные условия поимки двух убегающих. Приведены примеры, иллюстрирующие полученные результаты.

We consider a linear problem of pursuing two evaders by a group of persecutors in case of equal dynamic opportunities of all participants and under phase restrictions imposed on the states of evaders. We assume that the evaders use the same control. The movement of each participant has the form $ \dot z + a (t) z = w. $ Geometric constraints on the control are strictly convex compact set with smooth boundary, and terminal sets are the origin of coordinates. It is assumed that the evaders do not leave the convex cone. The aim of a group of pursuers is to capture two evaders; the aim of a group of evaders is opposite. We say that a capture holds in the problem of pursuing two evaders if among the specified number of pursuers there are two of them who catch the evaders, possibly at different times. We obtain sufficient conditions for capturing two evaders in terms of initial positions. The results obtained are illustrated by examples.

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

For a dynamical system controlled under conditions of disturbances, a problem of optimizing the guaranteed result is considered. A feature of the problem is the presence of functional constraints on disturbances, under which, in general, the set of admissible disturbances is not closed with respect to the operation of “gluing up” of two of its elements. This circumstance does not allow to apply directly the methods developed within the differential games theory for studying the problem and, thus, leads to the necessity of modifying them appropriately. The paper provides a new notion of a non-anticipative control strategy. It is proved that the corresponding functional of the optimal guaranteed result satisfies the dynamic programming principle. As a consequence, so-called properties of $u$- and $v$-stability of this functional are established, which may allow, in the future, to obtain a constructive solution of the problem in the form of feedback (positional) controls.

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

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.

Рассматриваются две задачи нелинейного гарантированного оценивания фазовых состояний динамических систем. Предполагается, что неизвестные измеримые по $t$ возмущения линейно входят в уравнение движения и аддитивно — в уравнения измерения. Эти возмущения стеснены нелинейными интегральными функционалами, один из которых является аналогом функционала обобщенной работы. Исследуемая задача состоит в построении информационных множеств по данным измерения, содержащих истинное положение траектории. Используется подход динамического программирования. Если для первого функционала требуется решить нелинейное уравнение в частных производных первого порядка, что не всегда возможно, то для функционала обобщенной работы достаточно найти решение линейного уравнения Ляпунова первого порядка, что существенно упрощает задачу. Тем не менее, даже в этом случае приходится налагать дополнительные условия на параметры системы для того, чтобы траектория системы, соответствующая наблюдаемому сигналу, существовала. Если уравнение движения линейно по фазовой переменной, то многие предположения выполняются автоматически. Для этого случая обсуждается вопрос о взаимной оценке сверху и снизу информационных множеств по включению для разных функционалов. В заключение рассмотрен наиболее прозрачный линейно-квадратичный случай. Изложение иллюстрируется примерами.

Two problems of nonlinear guaranteed estimation for states of dynamical systems are considered. It is supposed that unknown measurable in $t$ disturbances are linearly included in the equation of motion and are additive in the measurement equations. These disturbances are constrained by nonlinear integral functionals, one of which is analog of functional of the generalized work. The studied problem consists in creation of the information sets according to measurement data containing the true position of the trajectory. The dynamic programming approach is used. If the first functional requires solving a nonlinear equation in partial derivatives of the first order which is not always possible, then for functional of the generalized work it is enough to find a solution of the linear Lyapunov equation of the first order that significantly simplifies the problem. Nevertheless, even in this case it is necessary to impose additional conditions on the system parameters in order for the system trajectory of the observed signal to exist. If the motion equation is linear in state variable, then many assumptions are carried out automatically. For this case the issue of mutual approximation of information sets via inclusion for different functionals is discussed. In conclusion, the most transparent linear quadratic case is considered. The statement is illustrated by examples.

В статье рассматривается экстремальная задача маршрутизации с ограничениями. В общей формулировке предполагается, что объектами посещения являются любые непустые конечные множества — мегаполисы. Основной прикладной задачей, рассматриваемой в данном исследовании, является задача оптимизации траектории движения инструмента для станков листовой резки с ЧПУ, известная как проблема пути резания. Эта проблема возникает на этапе разработки управляющих программ для станков с ЧПУ. Возможны и другие приложения. В частности, результаты исследования могут быть использованы в задаче минимизация дозы облучения при демонтаже системы радиационно-опасных элементов после аварий на АЭС и в транспортных проблемах. В качестве ограничений исследуются ограничения предшествования. Они могут быть использованы для уменьшения вычислительной сложности. В качестве основного метода исследования использовалось широко понимаемое динамическое программирование. Предлагаемая реализация метода учитывает ограничения предшествования и зависимость целевых функций от списка задач. Последняя относится к классу очень сложных состояний, которые определяют допустимость маршрута на каждом шаге маршрутизации, в зависимости от уже выполненных или, наоборот, еще не завершенных задач. Применительно к задаче резки зависимость целевой функции от списка задач позволяет уменьшать термические деформации материала при резке. В работе математическая формализация экстремальной задачи маршрутизации с дополнительными ограничениями, описание метода и полученный с его помощью точный алгоритм. Оптимизации подлежат порядок выполнения задач, конкретная траектория процесса, и его начальная точка.

The paper deals with an extremal routing problem with constraints. In the general formulation, it is assumed that the objects of visiting are any non-empty finite sets — megalopolises. The main applied problem considered in this study is the tool path optimization problem for CNC sheet-cutting machines, known as the Cutting Path Problem. This problem arises at the stage of developing control programs for CNC machines. Other applications are also possible. In particular, the results obtained in the chapter can be used in the problem of minimizing the radiation dose when dismantling a system of radiation-hazardous elements after accidents at nuclear power plants and in transport problems. Among tasks constraints, the precedence constraints are investigated. These constraints can be used to reduce computational complexity. As the main method, the study used broadly understood dynamic programming. The offered realization of the method takes into account the precedence constraints and the dependence of the objective functions on the task list. This dependence belongs to the class of very complex conditions that determine the route admissibility at each routing step, depending on the tasks already completed or, on the contrary, not yet completed. As applied to the Cutting Path Problem, the dependence of the objective function on the task list makes it possible to reduce thermal deformations of the material during cutting. The chapter provides a mathematical formalization of an extremal routing problem with additional constraints, a description of the method, and the exact algorithm obtained with its help. The order of task execution, the specific trajectory of the process, and the starting point are optimized.

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

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

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.

Рассматривается модель эксплуатируемой однородной популяции, заданная разностным уравнением, зависящим от случайных параметров. При отсутствии эксплуатации развитие популяции описывается уравнением $$X(k+1)=f\bigl(X(k)\bigr), \quad k=1,2,\ldots,$$ где $X(k)$ — размер популяции или количество биоресурса в момент времени $k,$ $f(x)$ — вещественная дифференцируемая функция, заданная на отрезке $I=[0,a],$ такая, что $f(I)\subseteq I.$ В моменты времени $k=1,2,\ldots$ из популяции извлекается случайная доля ресурса $\omega(k)\in\Omega\subseteq[0,1]$. Процесс сбора может быть остановлен, когда доля собранного ресурса превысит некоторое значение $u(k)\in[0,1)$, чтобы сохранить по возможности большую часть популяции. Тогда доля добываемого ресурса будет равна $\ell(k)=\min (\omega(k),u(k)).$ Средняя временная выгода $H_*$ от извлечения ресурса равна пределу среднего арифметического от количества добываемого ресурса $X(k)\ell(k)$ в моменты времени $1,2,\ldots,k$ при $k\to\infty.$ Решается задача выбора управления процессом промыслового изъятия, при котором значение $H_*$ можно оценить снизу с вероятностью единица по возможности наибольшим числом. Оценки средней временной выгоды существенно зависят от свойств функции $f(x),$ определяющей динамику популяции; данные оценки получены для трех классов уравнений с функциями $f(x),$ обладающими определенными свойствами. Результаты работы проиллюстрированы численными примерами, построенными методом динамического программирования на основании того, что исследуемый процесс эксплуатации популяции является марковским процессом принятия решений.

We consider a model of an exploited homogeneous population given by a difference equation depending on random parameters. In the absence of exploitation, the development of the population is described by the equation $$X(k+1)=f\bigl(X(k)\bigr), \quad k=1,2,\ldots,$$ where $X(k)$ is the population size or the amount of bioresources at time $k,$ $f(x)$ is a real differentiable function defined on $I=[0,a]$ such that $f(I)\subseteq I.$ At moments $k=1,2,\ldots$, a random fraction of the resource $\omega(k)\in\omega\subseteq[0,1]$ is extracted from the population. The harvesting process can be stopped when the share of the harvested resource exceeds a certain value of $u(k)\in[0,1)$ to keep as much of the population as possible. Then the share of the extracted resource will be equal to $\ell(k)=\min (\omega(k),u(k)).$ The average temporary benefit $H_*$ from the extraction of the resource is equal to the limit of the arithmetic mean from the amount of extracted resource $X(k)\ell(k)$ at moments $1,2,\ldots,k$ when $k\to\infty.$ We solve the problem of choosing the control of the harvesting process, in which the value of $H_*$ can be estimated from below with probability one, as large a number as possible. Estimates of the average time benefit depend on the properties of the function $f(x)$, determining the dynamics of the population; these estimates are obtained for three classes of equations with $f(x)$, having certain properties. The results of the work are illustrated, by numerical examples using dynamic programming based on, that the process of population exploitation is a Markov decision process.