Все выпуски

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

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.

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

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.

Рассматривается линейная дифференциальная игра с заданным моментом окончания $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.

В конечномерном евклидовом пространстве рассматривается задача преследования группой преследователей одного убегающего, описываемая системой вида $$\dot z_i = a_i(t) u_i - v,\quad u_i\in U_i,\quad v\in V,$$ где функции $a_i(t)$ равны 1 при всех $t$, за исключением некоторого отрезка заданной длины, на котором они равны нулю (для каждого преследователя свой отрезок). Этот факт можно трактовать так, что у каждого из преследователей возможен отказ в работе управляющего устройства в любой заранее неизвестный момент времени, а длина промежутка времени, необходимого на устранение поломки, задана, при этом в процессе устранения поломки преследователи не имеют возможности осуществлять поимку. Целевые множества — выпуклые компакты, убегающий не покидает пределы выпуклого многогранного множества. Получены достаточные условия разрешимости задачи преследования.

In finite-dimensional Euclidian space, we treat the problem of pursuit of one evader by a group of pursuers, which is described by a system of the form $$\dot z_i = a_i(t) u_i - v, \quad u_i\in U_i, \quad v\in V,$$ where the functions $\alpha_i(t)$ are equal to 1 for all $t$, except for a certain interval of a given length, on which they are equal to zero (to each pursuer there corresponds its own interval). This fact can be interpreted in such a way that each of the pursuers has a possible failure of the control device at any previously unknown moment in time, and the length of the time interval needed to fix the failure is given, while in the process of fixing the failure the pursuers have no possibility to carry out a capture. The target sets are convex compact sets, and the evader does not leave the bounds of the convex polyhedral set. We obtain sufficient conditions for solvability of the pursuit problem.

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

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

The problem of the optimization of a guaranteed result for the control system, described by an ordinary differential equation, and a continuous payoff functional, is considered. At every moment the values of the control and of the disturbance are in the given compact sets. The disturbances as functions of time are subject to functional constraints belonging to a given family of constraints. The actions of control are formed by the strategies with full memory.

It is demonstrated, that optimal guaranteed result in this problem is equal to the value of the lower game. For the effectiveness of implemented control algorithm additional conditions on the system and appropriate ways of constructing an optimal strategy are specified.

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

The maximin game problem under sequential weakening of moment constraints is considered. The extension in the class of finitely additive measures realizing the asymptotic of maximin is constructed. The effectively verifiable sufficient conditions of stability «by maximin» is established.

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

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

The problem of sequential circuit of megalopolises with precedence conditions and cost functions that permit a dependence on tasks list is considered. Such problems can arise, in particular, in atomic energetic while investigating the questions connected with lowering of workers irradiation under permutations in radiative fields for realization of services connected with division of radiating elements. Another application of the developed methods is connected with important engineering problem of routing the instrument movements under the leaf cutting on numerically controlled machines. This problem has sufficiently large dimensionality and many precedence conditions: if a detail has not only exterior but at least one interior contours (the simplest example is a washer) then the interior contours must be cut before the cutting of exterior contour (finite sets located near corresponding contours are used as megalopolises). In this case the possible dependence of cost functions on tasks list can reflect various technological conditions. We note that perceptible dimensionality characterized by all contours in total leads to necessity of heuristics employment. Therefore, questions concerning at least local improvement of solutions appear sufficiently important for the investigation.

The basic attention in the article is devoted to the construction of optimizing insertions in complicated conditions: it is required to reduce the fragment of precedence conditions and to transform the corresponding cost functions; in the last case, it is important to preserve the dependence on tasks list. Both above-mentioned moments are taken into account under the procedure construction having the sense of algorithm on functional level.

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

A complicated variant of the “bottleneck problem” is considered, namely: the problem of sequential visiting of megalopolises with preceding constraints. It is supposed that costs functions and “current” constraints with respect to displacements selection depend on the tasks list which is not completed at the moment. The variant of widely understood dynamic programming is proposed, it doesn't foresee (with preceding conditions) construction of the whole array of the Bellman function values; the special layers of this function realizing in its totality the partial array of its values are constructed (it helps to decrease the calculation complexity). An algorithm of the problem value (global extremum) calculation is proposed, the computer realization of which implies the existence of only one layer of the Bellman function in a memory of computer; the obtained value may be used for the heuristics testing. The optimal algorithm of “complete” solving of the route problem is constructed, within which all layers of the Bellman function are used at the route and trace constructing.