Littérature scientifique sur le sujet « Deadlock minimization »

In this paper we consider a system of multiple mobile robots (MMRS) and the process of their concurrent motion in a shared two-dimensional workspace. The goal is to plan the robot movement along given fixed paths so as to minimize the completion time of all the robots while ensuring that they never collide. Thus, the considered problem combines the problems of robot schedule optimization with collision and deadlock avoidance. The problem formulation is presented and its equivalent reformulation that does not depend explicitly on the geometry of the robot paths is proposed. An event-based solution representation is proposed, allowing for a discrete optimization approach. Two types of possible deadlocks are identified and deadlock avoidance procedures are discussed. We proposed two types of solving methods. First, we implemented two metaheuristics: the local-search-based taboo search as well as the population-based artificial bee colony. Next, we implemented 14 simple constructive algorithms, employing dispatch rules such as first-in first-out, shortest distance remaining first, and longest distance remaining first, among others. A set of problem instances for different numbers of robots is created and provided as a benchmark. The effectiveness of the solving methods is then evaluated by simulation using the generated instances. Both deterministic and lognormal-distributed uncertain robot travel times are considered. The results prove that the taboo search metaheuristic obtained the best results for both deterministic and uncertain cases, with only artificial bee colony and a few constructive algorithms managing to remain competitive. Detailed results as well as ideas to further improve proposed methods are discussed.

The paper proposes a method that allows the modernization of the methodology for constructing manipulator movements according to the velocity vector, which makes it possible to exclude the occurrence of deadlocks in the process of computer simulation of movements. The developed algorithm is based on the use of a database characterizing the values of kinematic parameters that set the permissible instantaneous states of the manipulator mechanism at its various positions. A graphical representation of the hypersurface reflecting the relationship of these kinematic parameters from the values of generalized coordinates is performed. Based on this a method for determining kinematic parameters in the synthesis of movements of manipulator mechanisms in organized environments is proposed, which reduces the calculation time of intermediate configurations on a given trajectory of the output link and partially eliminates the occurrence of deadlocks. The results of the computer simulation of the movement of the arm and torso of the android robot on the criterion of minimization of the volume of movement, as well as movement taking into account the position of the forbidden zone with the overcoming of the deadlock situation are presented. The conducted studies can be used in the development of information and control complexes of mobile objects, in particular in the development of intelligent control systems for autonomously functioning robots in organized environments.

The further development of the analytical method for minimizing Boolean functions (BF) in the class of disjunctive normal forms by the numbers of sets of argument values, called -minimization, is proposed. Such an approach allows to reduce the process of minimizing the BF to the use of an exclusively analytical description of all its steps using functions of the number of the set of the BF argument values. In general, the idea is to develop such a toolkit that allows at all stages of the minimization process to operate only with numerical objects – Boolean vectors, not involve a visual analysis of the results of the intermediate steps, and not resort to attracting letter objects. In the future, the implementation of this idea at the software level for computers is assumed. The article consists of two parts. The first part is about calculating the Hamming distance between two Boolean vectors. Its equality to unity is a necessary and sufficient condition for gluing together the constituents of unity (zero) or elementary conjunctions (disjunctions). The Hamming distance between two sets of variable values was calculated using the Zhegalkin operation (inversion of equivalence), the distance matrix was compiled, and the abbreviated disjunctive normal form (DNF) was determined from it. From the abbreviated DNF deadlock form, and among them the minimal ones, were obtained by sorting out subsets of the set of units of the distance matrix. Deadlock forms are found by the units to which the implicants, covering all units of the set of BF values, correspond. The final result is presented, of course, in letter form. The second part of the article is devoted to the formulation and solution of the problem of minimizing BF as a problem of linear integer mathematical programming. The goal function is the arithmetic sum of all implicants of the abbreviated DNF. The system of restrictions is based on the fact that among the set of simple implicants, it is necessary to choose the smallest number of them so that all constituents of the unit of the original BF are covered. Restrictions are based on how much the constituent of a unit is covered by one or another implicant, and they are written in the form of linear inequalities through the symbol "greater than or equal to" with the right-hand sides equal to unity. The solution of the mathematical programming problem requires the use of a distance matrix. Examples of -minimization of BF are given.

An original approach to analytic canonical minimization of switching (Boolean) functions, which is based on the representation of Boolean functions (BF) as a function of one variable – the number of the set í of values of its arguments, is proposed. For this, using the Antje function, the dependence (in the form of formulas) of the values of each of n variables on the number í is established. To construct a minimal disjunctive or conjunctive normal form of the BF are repelled from the corresponding perfect forms. In this connection the need to describe the sequence of numbers of sets, on which the variables take the values 1 and 0, arises. The common terms of such sequences can be obtained using the formula for the common term of a numerical sequence in a representation through the finite differences of its members. Further the connection between the sum of the values of atoms (term) ó(í) and the numbers of their values is established. With the help of the values of ó(í) , the question of gluing the constituents of the unit or zero is solved. Threedimensional and four-dimensional cubes whose vertices are labeled with sigmas are depicted for a function of three and four variables, respectively. Since the necessary condition for gluing the constituents – the modulus of the difference between sigmas is equal to one – is not sufficient, the gluing criterion is used: the constituents of a unit or zero are glued if and only if the Gamming distance between two values of ó(í) is equal to one. The general order for gluing the constituent of a unit or zero on the basis of the described means is obtained. A matrix of size m× n , where m is the number of simple implicant or implicent, n is the number of sets, on which the BF unit or zero values takes, is used to build deadlock forms; they are not represented by letters, but by sets of ones and zeros that correspond to them. The proposed approach to minimizing BF is called the í -minimization method. An example of minimizing of BF of five variables, given by the numbers of the sets í of values of its arguments, on which it takes values equal to one, that is – with the property f = 1, is given. The possibility of using the í -minimization of BF in bases other than the basis (∧, ∨, ￣ ), and in the future – an application to the minimization of BF of integer mathematical programming is discussed.

As the future of nuclear power is uncertain, only choosing one development objective for the coming decades can be risky; while trying to achieve several possible objectives at the same time may lead to a deadlock due to contradiction among them. In this work, we study a simple scenario to illustrate the newly developed method of robustness study, which considers possible change of objectives. Starting from the current French fleet, two objectives are considered regarding the possible political choices for the future of nuclear power: A. Complete substitution of Pressurized Water Reactors by Sodium-cooled Fast Reactors in 2180; B. Minimization of all potential nuclear wastes without SFR deployment in 2180. To study the robustness of strategies, the disruption of objective is considered: the objective to be pursued is possibly changed abruptly from A into B at unknown time. To minimize the consequence of such uncertainty, the first option is to identify a robust static strategy, which shows the best performance for both objectives A and B in the predisruption situation. The second option is to adapt a trajectory which pursues initially objective A, for objective B in case of the disruption. To identify and to analyze the adaptively robust strategies, outcomes of possible adaptations upon a given trajectory are compared with the robust static optimum. The temporality of adaptive robustness is analyzed by investigating different adaptation times.

ABSTRACT Now a days, Mobile computing networks revolutionize the way computers are used. Mobile hosts have small memory, a relatively slow processor and low power batteries, and communicate over low bandwidth wireless communication links. Distributed dynamic channel allocation in mobile cellular networks and other similar structures is a fundamental resource management problem. It has aroma of distributed mutual exclusion but is not exactly mutual exclusion problem because a channel must be reused in different cells. Existing mutual exclusion algorithms for cellular systems are not suitable to mobile systems due to above limitations. Here, the exact relation being established between the both algorithms. Specifically, we describe the procedure of relaxed mutual exclusion to modularize the problem of distributed channel allocation. A geographical area is divided into hexagonal cells, every cell uses the same bandwidth, which is divided into channels. Cell phone must use one channel to make a call. Cells have different traffic usage of channels such that every cell could need different quantity of channels. Allocation algorithm should dynamically allocate channels (resources) to cells, to get the most efficient usage of available bandwidth using relaxed mutual exclusion. We propose a general algorithm that guarantees relaxed mutual exclusion for a single resource, prove a necessary and sufficient condition for the information structure, and address the issues that arise in relaxed mutual exclusion, including deadlock resolution, dealing with multiple resources, and design of efficient information structure. Here, improvement based on mutual exclusion solution, such as deadlock minimization and broken cells serving extended to multiple channel case is described to an extent to use the bandwidth efficiently. Keywords : Relaxed Mutual Exclusion, channel allocation, deadlock minimization, broken cell serving, TSDP(Two-Step Dynamic-Priority), borrowing scheme