Все выпуски

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

Изучаются свойства дискретной вариационной задачи динамической аппроксимации в комплексном евклидовом (L + 1)-мерном пространстве E. Она обобщает известные задачи среднеквадратической полиномиальной аппроксимации функций, заданных своими отсчетами в конечном интервале. В рассматриваемой задаче аппроксимация последовательности y = {y_i}_L⁰ отсчетов функции y(t) ∈ L²[0, T], T = Lh на сетке I_h осуществляется решениями однородных линейных дифференциальных или разностных уравнений заданного порядка n с постоянными, но, возможно, неизвестными коэффициентами. Тем самым показано, что в последнем случае задача аппроксимации включает в себя и задачу идентификации. Анализ ее особенностей - основная тема статьи. Ставится задача нахождения вектора коэффициентов  разностного уравнения Σ_n⁰ ŷ_i+k α_i = 0, где k = 0,L − n. Оптимизируются коэффициенты  и начальные условия переходного процесса y этого уравнения. Цель оптимизации - наилучшая аппроксимация исследуемого динамического процесса y ∈ E. Критерий аппроксимации  минимум величины ||y − ŷ||²_E. Показано, что изучаемая вариационная задача сводится к задачам проектирования в E вектора y на ядра разностных операторов с неизвестными коэффициентами α ∈ ω ⊂ S ⊂ Eⁿ⁺¹. Здесь α - направление, S - сфера или гиперплоскость. Показана связь изучаемой задачи с задачами дискретизации и идентифицируемости. Тогда координаты вектора y ∈ E есть точное решение дифференциального уравнения на сетке I_h и y = ŷ. Дано сравнение изучаемой задачи вариационной идентификации с алгебраическими методами идентификации. Показано, что ортогональные дополнения к ядрам разностных операторов всегда имеют теплицев базис. Это приводит к быстрым проекционным алгоритмам вычислений. Показано, что задача нахождения оптимального вектора α сводится к задаче безусловной минимизации функционала идентификации, зависящего от направления  в Eⁿ⁺¹. Предложена итерационная процедура его минимизации на сфере с широкой областью и высокой скоростью сходимости. Изучаемую вариационную задачу можно применять при математическом моделировании в управлении и научных исследованиях. При этом на конечных интервалах может использоваться, в частности, возможность кусочно-линейной динамической аппроксимации сложных динамических процессов разностными и дифференциальными уравнениями указанного типа.

Some properties of the discrete variational problem of the dynamic approximation in the complex Euclidean (L + 1)-dimensional space are studied here. It generalizes familiar problems of the mean square polynomial approximation of the functions given on the finite interval in accordance with their references. In the problem under consideration sequence approximation y = {y_i}_L⁰ of the references of the function y(t) ∈ L²[0, T], T = Lh on the lattice I_h is achieved by solving homogeneous linear differential equations or difference equations of the given order n with constant but possibly unknown coefficients. Thus, it is shown that in the latter case the approximation problem also includes the identification problem. The analysis of its properties is the main subject of the article. The problem is set to find vector of coefficients  of difference equation Σ_n⁰ ŷ_i+k α_i = 0, where k = 0,L − n. Coefficients  and initial conditions of the transient process by of this equation are optimized. The optimization purpose is to achieve the best approximation of the dynamic process y ∈ E being considered here. The approximation criterion is a minimum of the quantity ||y − ŷ||²_E. The variational problem under study is shown to be reduced to the problem of projecting vector y in E on the kernels of the difference operators with unknown coefficients  α ∈ ω ⊂ S ⊂ Eⁿ⁺¹, where  is a direction, S is a sphere or a hyperplane. The problem under study is shown to be related to the problems of the discretization and identifiability. In this case vector coordinates y ∈ E is an exact solution of differential equation on the lattice I_h and y = ŷ. The problem of the variational identification is compared with algebraic methods of identification. The orthogonal complement to the kernels of the difference operators are shown to always have Toeplitz basis. This results in fast projecting algorithms of computation. The problem of finding optimal vector α is shown to be reduced to the problem of the absolute minimization of the identification functional depending on the direction  in Eⁿ⁺¹. The iterative procedure of its minimization on a sphere with wide domain and high speed of convergence is presented here. The variational problem considered here can be applied in mathematical modeling for control problem and research purposes. On the finite intervals, for example, it is possible to use piecewise-linear dynamic approximations of the complex dynamic processes with difference and differential equations of the specified type.

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

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

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.

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

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

This paper examines the following problem: a linear autonomous differential-difference system of neutral type with delay in state requires ensuring its complete calming by feedback. To solve this problem linear autonomous dynamic differential-difference controller with state feedback is proposed; this controller does not exclude a closed system from the original class of linear autonomous systems of neutral type. Sufficient condition for the existence of such a controller coincides with the criterion of complete controllability. In addition, the closed system has a finite spectrum, which simplifies greatly the problem of calculating the current state during the technical implementation of the controller. The basic idea of research is to select parameters for the controller so that the closed system becomes point-degenerated in directions corresponding to phase components of the original (open) system. To do this, the original system is first converted via feedback to the single-input system of retarded type. Further, for the resulting object the dynamic controller that provides the degeneracy of the corresponding phase components is constructed.

The proposed procedure for constructing the control action is based on the algebraic properties of shift operator and does not involve calculating the roots of characteristic quasipolynomial of the original system. It can be used to provide full calming as well as exponential stability to a closed system. However, in the latter case it is necessary to use dynamic controller with state feedback of integral type.

Получены достаточные условия разрешимости линейной задачи уклонения в нестационарной дифференциальной игре со многими участниками.

The paper deals with the linear non-stationary problem of disputed interaction of operated objects with participation of n pursuers and of m evaders with dynamic opportunities of all participants being equal. Suffcient conditions of resolvability of the global problem of evasion have been 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.

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

We consider a routing problem with constraints and complicated cost functions. The visited objects are assumed to be clusters, or megalopolises (nonempty finite sets), and the visit to each of them entails certain tasks, which we call interior jobs. The order of visits is subject to precedence constraints. The costs of movements depend on the set of pending tasks (not yet complete at the time of the movement), which is also referred to as “sequence dependence”, “position dependence”, and “state dependence”. Such a dependence arises, in particular, in routing problems concerning emergencies at nuclear power plants, similar to the Chernobyl and Fukushima Daiichi incidents. For example, one could consider a disaster recovery problem concerned with sequential dismantlement of radiation sources; in this case, the crew conducting the dismantlement is exposed to radiation from the sources that have not yet been dealt with. This gives rise to dependence on pending tasks in the cost functions that measure the crew's radiation exposure. The latter dependence reflects the “shutdown” operations for the corresponding radiation sources. This paper sets forth an approach to a parallel solution for this problem, which was implemented and run on the URAN supercomputer.

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

We study the problem of small motions of a viscous stratified fluid partially filling a container that uniformly rotates around an axis co-directed by gravity. The problem is studied on the basis of an approach related to the application of the so-called operator matrix theory. To this end, we introduce Hilbert spaces and some their subspaces, as well as auxiliary boundary value problems. The original initial-boundary value problem is reduced to the Cauchy problem for a first-order differential equation in some Hilbert space. After a detailed study of the properties of the operator coefficients corresponding to the resulting system of equations, we prove a theorem on the solvability of the Cauchy problem. On this basis, we find sufficient conditions for the existence of a solution of the original initial-boundary value problem describing the evolution of the hydro-system.

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

The “additive” problem of sequentially visiting megalopolises (nonempty finite sets) is considered; some tasks are executed as the megalopolises are visited. Permutations and operations are evaluated by cost functions that admit a dependence on the list of tasks. There are restrictions of different types, which include precedence conditions used in the “positive direction” (to reduce the complexity of calculations). In addition, this conception involves dynamical restrictions that are formed in the process of task execution. This conception is oriented to engineering applications associated with sheet cutting on CNC machines. An approach to constructing optimal solutions based on a nonstandard version of dynamic programming (DP) is investigated. This approach takes into account restrictions of different types, including dynamic constraints which naturally arise in sheet cutting applications (in particular, it takes into account heat tolerances related to diffusion of heat in the vicinities of tie-in points). In this regard, a combination of “direct” interdictions of movements and cutting and a system of penalties is allowed; in the latter case, cost functions with a dependence on the list of tasks arise. The variant of DP that is used allows one to optimize the selection of a starting point, the route, which is identified with a permutation of the indexes, and the trajectory corresponding to the above-mentioned route. An economical variant of DP is used at the stage of construction of the Bellman function. This conception allows avoiding calculation of the whole array of values of this function; instead, only the system of its layers is defined (in the case of using the precedence conditions, which are typical of the problem of sheet cutting, this conception results in a considerable reduction of calculation costs). An optimal DP-based algorithm is constructed and realized on PC, and the results of the computational experiment are presented.

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

The work is devoted to the validation of the model of adaptive control of the movement of pedestrian flows in a dynamic environment of limited space, which can be a building. An important case is considered in which the rates of change in the characteristics of the movement of a pedestrian flow and the state of the environment are close in magnitude. The concept of topological complexity is introduced to describe the inherent properties of a digital building model. Topological complexity characterizes the building from the position of connectedness of its elements. Validation is based on comparing the results of the evacuation of people from buildings obtained in the course of training fire alarms with the results of modeling the movement of pedestrian flows. When comparing, the time intervals for the release of buildings are compared. The experimental results are statistically significantly approximated by the regression model, which is used in validation. Validation made it possible to obtain a refinement coefficient of the digital model of the building, in which the results of modeling the movement of pedestrian flows correspond to the results of field observations. Validation of the model of controlled movement of pedestrian flows in a changing environment of limited space made it possible to use the model in a software and hardware complex for managing pedestrian flows, which operates in real-time advance mode.