Dynamic asymmetric assignment problem in open multi-agent systems

The purpose of the work is to develop models and algorithms for optimizing matching in dynamically generated graphs of asymmetric relations in coordinated open systems of interacting agents with centralized and collective control. The dynamic asymmetric matching optimization problem arises here as a result of a compromise approximation of the mapping of the dynamic programming method onto a stream of known open assignment problems or several traveling salesmen. However, the branching alternatives presented in this way for independent tasks do not take into account the interdependence of real relationships between agents and their tasks, including their relationship to time. Ignoring the dependence of branching alternatives leads to a delay in the moment or to a loss in the quality of assignment of tasks to coordinated agents. The main idea of the proposed implementation of the principle known for effective control is to postpone the moment the final decision is made to the latest moment, taking into account the susceptibility of the system to local changes in state variables. The interdependence of states is revealed on the basis of the analysis of the correspondence of the graph of the current matching with the optimal solution on the subgraph of perfect matching. The transition between states is implemented by the incremental version of the reoptimization algorithm for solving linear problems of assigning the shortest replenishing path using the method. The space of search states is a dynamically generated bipartite sparse graph of alternatives for a combination of agents and tasks, represented by a list of arcs. To highlight the sets of changed arcs, it is proposed to supplement the weight of the arcs with the boundaries of the stability intervals of the solution, optionally formed in the background. By default, the weight of the modified arc matches the boundary of the stability interval. On each correction cycle of the lists of agents, tasks, and their associations, subsets of elements are selected for which reconsideration of matching is required. An enhanced condition for the selection of such elements is to go beyond the boundaries of the stability interval. In this case, the asymmetry of the assignment problem is taken into account by choosing the adjacency structure for the fraction of the graph with a minimum of vertices. As a result, the reaction time of procedures for solving the assignment problem is reduced by an order of magnitude.

1. Korsah G.A., Stentz A., Dias M.B. A comprehensive taxonomy for multi-robot task allocation. The International Journal of Robotics Research. 2013;12(32):1495-1512.

2. Spivey M.Z., Powel W.B. The Dynamic Assignment Problem. Transportation science.2004;38(4):399-419.

3. Pentico D.W. Assignment problems: A golden anniversary survey. European Journal of Operational Research. 2007;176(2):774-793.

4. Bijsterbosch J., Volgenant A. Solving the Rectangular assignment problem and applications. Annals of Operations Research. 2010;181(1):443-462.

5. Revotjuk M.P., Batura P.M., Polonevich A.M. [Reoptimization of the linear assignment problem]. Doklady BGUIR=Doklady BSUIR. 2011;1(55):55-62. (In Russ.)

6. Toroslu I.H., Üçoluk G. Incremental assignment problem. Information Science. 2007;177:1523-1529.

7. Revotjuk M.P., Qaraleh M.K., Batura P.M. [Implementation the branch and bound method for solving the traveling salesman problem with sparse matrix]. Doklady BGUIR = Doklady BSUIR. 2013;7(77):25-31. (In Russ.)

8. Revotjuk M.P., Qaraleh M.K., Batura P.M. [Quick evaluation of the interval stability of the linear assignment problem solutions]. Doklady BGUIR = Doklady BSUIR. 2013;5(75):30-36. (In Russ.)