Все выпуски

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

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.

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

The paper is concerned with the approximation of the value function of the zero-sum differential game with the minimal cost, i.e., the differential game with the payoff functional determined by the minimization of some quantity along the trajectory by the solutions of continuous-time stochastic games with the stopping governed by one player. Notice that the value function of the auxiliary continuous-time stochastic game is described by the Isaacs–Bellman equation with additional inequality constraints. The Isaacs–Bellman equation is a parabolic PDE for the case of stochastic differential game and it takes a form of system of ODEs for the case of continuous-time Markov game. The approximation developed in the paper is based on the concept of the stochastic guide first proposed by Krasovskii and Kotelnikova.

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

The abstract problem of control and its relaxations connected with a weakening of constraints on the choice of programmed strategies are considered. Relations connecting the sets of admissible elements of the initial problem and its extension are investigated. Conditions sufficient for the stability of the initial attainable set (with the exactness until a closure) are obtained.

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

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 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.

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

Issues related to solving the additive problem of sequential traversal of sets with precedence restrictions and cost functions that allow dependence on the list of tasks are considered. The basic method is a broadly understood dynamic programming (DP), supplemented in the case of problems of appreciable dimension by decompositions of the family of tasks and transformation of the parameters of the original problem. Possible applications are related, in particular, to the problem of tool control in figured sheet cutting of parts on CNC machines. In this problem, an important circumstance is taking into account the precedence conditions, which have, in particular, the following meaning: in the case of a part with holes, cutting of each of the internal contours (corresponding to the holes) should precede cutting of the external contour. The quality criterion itself in this problem, as a rule, is additive. Another type of constraints concerns avoiding thermal deformations of parts. When using the approach with penalties for violating the conditions associated with effective heat dissipation during cutting, cost functions arise that allow dependence on the list of tasks completed to date. Note that in another applied problem, namely, in the problem of dismantling radiation hazardous objects, cost functions arise with dependence on the list of tasks that have not been completed at the moment (and, consequently, concern the objects that have not been dismantled). As a result, we arrive at a very general problem with precedence constraints and cost functions with dependence on the list of tasks. The decomposition applied in the case of a noticeable dimensionality with subsequent implementation of the DP requires, on the one hand, the development of clustering methods, and, on the other, the construction of an adequate structure for distributing global precedence conditions among clusters. In the theoretical part of the work, the case of two clusters is discussed, which makes it possible to cover with a single scheme a number of practically interesting problems of a range (in terms of dimensionality) type. An algorithm for constructing a composite solution is indicated, including a stage of clustering training based on a greedy algorithm. This “composite” algorithm is implemented on a PC; a computational experiment was carried out.

В работе рассматривается задача о движении колесного экипажа на плоскости в случае, когда одна из колесных пар фиксирована, а также случай движения колесного экипажа на плоскости в случае двух свободных колесных пар. Указан способ получения уравнений движения для экипажа с произвольной геометрией. Определены возможные виды движения экипажа с фиксированной колесной парой.

The paper deals with the problem of motion of a wheeled carriage on a plane in the case where one of the wheeled pairs is fixed. In addition, the case of motion of a wheeled carriage on a plane in the case of two free wheeled pairs is considered.

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

Theorems on solvability, estimates of solutions, and well-posed solvability of equations with covering mappings in the product of metric spaces are formulated. Conditions for the Nemytskii operator to be a covering operator in functional spaces are considered. Statements about covering mappings are applied to studying the controlled systems described by ordinary differential equations unsolved for the derivative. For controlled differential systems with mixed constraints on control and an additional constraint on the solution's derivative, conditions of solvability are received as well as solutions' estimates, the question of continuous dependence of solutions on parameters is investigated.

Рассматривается линейная дифференциальная игра с заданным моментом окончания $p$. Множества достижимости игроков являются $n$-мерными шарами. Терминальное множество в игре определяется условием принадлежности нормы фазового вектора отрезку с положительными концами. Множество, определяемое данным условием, названо в работе кольцом. Тот факт, что терминальное множество не является выпуклым, потребовал привлечения дополнительной теории, позволяющей находить сумму и разность Минковского для кольца и шара в $n$-мерном пространстве. На выбор управления первого игрока накладывается импульсное ограничение. Возможности первого игрока определяются запасом ресурсов, который он может использовать при формировании своего управления. В отдельные моменты времени возможно отделение части запаса ресурсов, что может привести к «мгновенному» изменению фазового вектора, тем самым усложняя задачу. Управление второго игрока стеснено геометрическими ограничениями. Цель первого игрока заключается в том, чтобы в заданный момент времени привести фазовый вектор на терминальное множество. Цель второго игрока противоположна. Построен максимальный стабильный мост, ведущий в заданный момент времени на терминальное множество. Стабильный мост определяется функциями внешнего и внутреннего радиусов, которые вычислены в явном виде.

We consider a linear differential game with the fixed end time $p$. Attainability domains of players are $n$-dimensional balls. The terminal set of a game is determined by a condition for assigning the norm of a phase vector to a segment with positive ends. A set defined by this condition is named in the article as ring. The fact that the terminal set is not convex required an additional theory allowing us to calculate Minkowski sum and difference for a ring and a ball in $n$-dimensional space. Control of the first player has a pulse constraint. Abilities of the first player are determined by the stock of resources that can be used by the player at formation of his control. At certain moments of time the separation of a part of the resources stock is possible, which may implicate an “instantaneous” change of a phase vector, thereby complicating the problem. Control of the second player has geometrical constraints. The aim of the first player is to lead a phase vector to the terminal set at fixed time. The aim of the second player is opposite. The maximal stable bridge leading at fixed time to the terminal set has been constructed. A stable bridge is determined by the functions of internal and external radii, which are calculated explicitly.