Applied tasks of multiagent routing problems

M. S. Germanchuk

Taurida Journal of Computer Science Theory and Mathematics, no. 4 (2021), pp. 13-25

Résumé

Applied network tasks of multiagent routing or $mTSP$ arise in many application areas and lead to various models of pseudo-Boolean optimization. Such problems, as a rule, are $NP$-hard, for them exact algorithms are applicable only in the case of a small dimension of the original network (graph). Multiagency can be contained in the initial formulation or arise as a result of simplifying and reducing the dimension of the problem (decomposition, clustering). Models of such tasks in the author's works arose when planning multi-day tourist routes to attractions; choosing routes by agents in emergency situations (when the infrastructure network may change); when using unmanned aerial vehicles, drones $mTSP$ to build routes; in tasks of traversing clusters (bypassing communities social networks). Depending on the class of applied tasks, the scenarios of their research are specified. The following scenario is typical: 1. Formalization of models of applied multiagent routing problems in the form of single- or multi-criteria pseudo-Boolean optimization problems. Building a hierarchy of simplified models. Accounting for specifics $mTSP$. 2. Analysis of the original complex network taking into account $NP$-complexity $mTSP$ on this network. With the help of polynomial algorithms, the network structure is specified: metric and statistical characteristics of the network are found; bridges, points of articulation, bottlenecks (minimal cuts); histograms of the distribution of weight coefficients of arcs of the network graph, etc. 3. A simpler network (projection onto a plane; overflight, monitoring network) is matched to the source network, or the clustering of the network is performed in accordance with $mTSP$. 4. Exact and approximate algorithms on clusters are used; compositions of algorithms (heuristics, metaheuristics, genetic algorithms, etc.). 5. Iterative refinement of the solution $mTSP$ is performed based on individual solutions of agents. The elements of the scenario are given in the work. The results of network clustering consistent with $mTSP$, a comparative analysis of algorithm compositions are shown. It is important in the research process to take into account all available information, facts, knowledge, and precedents both for building a hierarchy of models and for developing practical algorithms for solving them. In addition to these approaches, it is promising to use a class of polynomial solvable $mTSP$ in the form of pseudo-Boolean optimization models with separable objective functions and constraints in the form of disjunctive normal form (DNF) having a limited constant length. Despite the fact that in the general case the reduction of $mTSP$ with DNF constraints is exponential, it is necessary to distinguish a class of problems that are relatively easily reduced to the form with DNF constraints. Synthesis of a model with DNF constraints on the initial data can be carried out approximately. In this case, the complexity of such an approximation turns out to be polynomial. The number of conjunctions in the extracted DNF does not exceed the number of examples in the original case information. The proposed research scenario $mTSP$ may be promising for the development of intelligent multiagent systems of applied routing.

Détail

Keywords: multiagent traveling salesman problems ($mTSP$), applied routing algorithms, $TSP$ clustering.