• V. M. Batsamut National Academy of the National Guard of Ukraine, Kharkiv, Ukraine, Ukraine
  • S. O. Hodlevsky National Academy of the National Guard of Ukraine, Kharkiv, Ukraine, Ukraine



multi-agent system, group of mobile robots, routing, network object, weighted undirected (directed) graph, extreme paths, optimization criterion, method


Context. The relevance of the article is determined by the need for further development of models of collective behavior of systems with multi-agent structure construction endowed with intelligence that ensures synchronization of the joint efforts of various agents while achieving the goals set for the system. The method proposed in the article solves the problem of competition between different agents of a multi-agent system, which is important while performing search, rescue, and monitoring tasks in crisis areas of various origins.

Objective is to develop a method for determining the sufficient population of a multi-agent system and the optimal routes of movement of its individual elements in a stationary network for the most complete examination of a technological disaster zone (any given zone based on a certain transport network).

Method. We implemented the concept of a dynamic programming to search for all possible edge-simple longest paths connecting the directed subsets of vertices-sources and vertices-sinks in the structure of the model weighted directed graph. To this end, the modified Dijkstra method was applied. The modification comprises representing the weights of the arcs of the modeling directed graph with the negative values, which are further used in calculations according to the Dijkstra method. After finding the next edgesimple longest path, the arcs that make up it are fixed in the memory of the computer system (in the route plan) and removed from the graph structure, and the process is iteratively repeated. The search for paths takes place as long as the transitive closure between the vertices that are part of the specified subsets of source vertices and sink vertices is preserved. The developed method makes it possible to find such a set of traffic routes for the elements of the multi-agent system, which maximizes the area examined by them in a technological disaster zone (or the number of checked objects on the traffic routes) in one “wave” of the search and distributes the elements of a multi-agent system by routes that do not have common areas. A derivative of the application of the developed method is the determination of a sufficient population of a multi-agent system for effective search activities within the defined zone.

Results. 1) A method of routing a group of mobile robots in a stationary network for searching the missing objects in a technological disaster zone has been developed. 2) The working expression of the Dijkstra method for searching in the structure of a network object (in the structure of a model graph) for the longest paths has been formalized. 3) We have suggested a set of indicators for a comprehensive evaluation of route plans of a multi-agent system. 4) The method has been verified on test problems.

Conclusions. Theoretical studies and several experiments confirm the efficiency of the developed method. The solutions made using the developed method are accurate, which allows recommending it for practical use in determining in an automated mode route plans for multi-agent systems, as well as the required number of agents in such systems to perform the required amount of search tasks in a particular crisis area.

Author Biographies

V. M. Batsamut, National Academy of the National Guard of Ukraine, Kharkiv, Ukraine

Dr. Sc., Professor, The Deputy Head of the Scientific Research Center

S. O. Hodlevsky, National Academy of the National Guard of Ukraine, Kharkiv, Ukraine

The Researcher of the Scientific Research Center of the National Academy


Konovalenko O., Brusentsev V. Multi-agent management and decision support systems, Bulletin of the National Technical University “KhPI”. Ser.: Mechanical engineering and CAD, 2019, Vol. 1, pp. 18–27. DOI: 10.20998/20790775.2019.1.03

Kravari K., Bassiliades N. A Survey of Agent Platforms, Journal of Artificial Societies and Social Simulation, 2015, Vol. 18, № 1, pp. 1–18. DOI: 10.18564/jasss.2661

Schurr N., Schurr N., Marecki J. et al. The Future of Disaster Response: Humans Working with Multiagent Teams using DEFACTO, Conference: AI Technologies for Homeland Security : Papers from the 2005 AAAI Spring Symposium, Technical Report SS-05-01. Stanford, California, USA, March 21–23, 2005 : proceedings, Menlo Park, California : The AAAI Press, 2005, pp. 9–16.

Ayanian N. DART: Diversity-enhanced Autonomy in Robot Teams, The International Journal of Robotics Research. – 2018, pp. 1–8. DOI: 10.1177/0278364919839137.

Minieka E. Optimization algorithms on networks and graphs. Moscow, Mir, 1981, 323 p.

Held M., Karp R. The Travelling-Salesman Problem and Minimum Spanning Trees: Part II, Math. Programming, 1971, Vol. 1, pp. 6–25. DOI:10.1007/BF01584070

Bellman R. On a Routing Problem, Quarterly of Applied Mathematics, 1958, Vol. 16 (1), pp. 87–90. DOI: 10.1090/qam/102435

Hadjiconstantinou E., Christofides N., Mingozzi A. A new exact algorithm for the vehicle routing problem based on qpaths and k-shortest paths relaxations, Annals of Operations Research, 1995, Vol. 61, pp. 21–43. DOI:10.1007/BF02098280

Christofides N., Mingozzi A., Toth P. Exact algorithm for the Vehicle Routing Problem Based on Spanning Tree and Shortest Paths Relaxations, Mathematical Programming, 1981, Vol. 20, No. 1, pp. 255–282. DOI:10.1007/BF01589353

Christofides N. Theory of graphs. Algorithmic approach. Moscow, Mir, 1978, 432 p.

Karger D. Motwani R., Ramkumar G.D.S. On approximating the longest path in a graph, Algorithmica, 1997, Vol. 18, pp. 82–98. DOI: 10.1007/BF02523689

Feder T., Motwani R. Finding large cycles in Hamiltonian graphs, 16th annual ACM-SIAM Symp. on Discrete Algorithms (SODA), Vancouver, 23–25 January 2005 : proceedings. Philadelphia, United States, Society for Industrial and Applied Mathematics, 2005, pp. 166–175. DOI: 10.5555/1070432

Gabow H. N. Finding paths and cycles of super polylogarithmic length, 36th annual ACM Symp. on Theory of Computing (STOC), Chicago, 13–16 June 2004 : proceedings. New York, United States : Association for Computing Machinery, 2004, pp. 407–416. DOI: 10.1145/1007352.1007418

Gabow H. N., Nie S. Finding long paths, cycles, and circuits, 19th annual International Symp. on Algorithms and Computation (ISAAC), Gold Coast, Australia, December 2008 : proceedings. Berlin, Springer-Verlag, 2008, pp. 752– 763. DOI: 10.1007/978-3-540-92182-0_66

Vishwanathan S. An approximation algorithm for finding a long path in Hamiltonian graphs, 11th annual ACM-SIAM Symp. on Discrete Algorithms (SODA), San Francisco, 9–11 January 2000 : proceedings. Philadelphia, United States : Society for Industrial and Applied Mathematics, 2000, pp. 680–685. DOI: 10.5555/338219

Zhang Z., Li H. Algorithms for long paths in graphs, Theoretical Computer Science, 2007. Vol. 377, Issue 1–3. pp. 25–34. DOI: 10.1016/j.tcs.2007.02.012

Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-completeness. New York, W.H. Freeman, 1979, 340 p.

Garey M. R., Johnson D. S., Tarjan R. E. The planar Hamiltonian circuit problem is NP-complete, SIAM J. Computing, 1976. Vol. 5, pp. 704–714. DOI: 10.1137/0205049

Golumbic M. C. Algorithmic Graph Theory and Perfect Graphs, Vol. 57 : Annals of Discrete Mathematics. 2nd Edition. Amsterdam, North-Holland Publishing Co., 2004, 592 p. ISBN: 9780080526966

Müller H. Hamiltonian circuits in chordal bipartite graphs, Discrete Math., 1996, Vol. 156, pp. 291–298. DOI: 10.1016/0012-365X(95)00057-4

Narasimhan G. A note on the Hamiltonian circuit problem on directed path graphs, Information Processing Letters, 1989, Vol. 32, pp. 167–170. DOI: 10.1016/00200190(89)90038-0

Damaschke P. The Hamiltonian circuit problem for circle graphs is NP-complete, Information Processing Letters. – 1989, Vol. 32, pp. 1–2. DOI: 10.1016/0020-0190(89)900598

Itai A., Papadimitriou C. H., Szwarcfiter J. L. Hamiltonian paths in grid graphs, SIAM J. Computing, 1982, Vol. 11, pp. 676–686. DOI: 10.1137/0211056

Arikati S. R., Pandu Rangan C. Linear algorithm for optimal path cover problem on interval graphs, Information Processing Letters, 1990, Vol. 35, pp. 149–153. DOI: 10.1016/0020-0190(90)90064-5

Bertossi A. A. Finding Hamiltonian circuits in proper interval graphs, Information Processing Letters, 1983, Vol. 17, pp. 97–101. DOI: 10.1016/0020-0190(83)90078-9

Chang M. S., Peng S. L., Liaw J. L. Deferred-query: An efficient approach for some problems on interval graphs, Networks, 1999, Vol. 34, Issue 1, pp. 1–10. DOI: 10.1002/(sici)1097-0037(199908)34:1<1::aid-net1>

Damaschke P. Paths in interval graphs and circular arc graphs, Discrete Math., 1993, Vol. 112, pp. 49–64. DOI: 10.1016/0012-365X(93)90223-G

Asdre K., Nikolopoulos S. D. The 1-fixed-endpoint path cover problem is polynomial on interval graphs, Algorithmica, 2009, Vol. 58, pp. 679–710. DOI: 10.1007/s00453-009-9292-5

Damaschke P., Deogun J. S., Kratsch D. et al. Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm, Order, 1992, Vol. 8, pp. 383–391. DOI: 10.1007/bf00571188

Bulterman R., Sommen F. van der, Zwaan G. et al. On computing a longest path in a tee, Information Processing Letters, 2002, Vol. 81, pp. 93–96. DOI: 10.1016/S00200190(01)00198-3

Uehara R., Uno Y. Efficient algorithms for the longest path problem, 15th annual International Symp. on Algorithms and Computation (ISAAC), Hong Kong, December 2004 : proceedings. Berlin, Springer-Verlag, 2004, pp. 871–883. DOI:10.1007/978-3-540-30551-4_74

Uehara R., Valiente G. Linear structure of bipartite permutation graphs and the longest path problem, Information Processing Letters, 2007, Vol. 103, pp. 71–77. DOI: 10.1016/j.ipl.2007.02.010

Takahara Y., Teramoto S., Uehara R. Longest path problems on ptolemaic graphs, IEICE Trans. Inf. and Syst., 2008, Vol. 91-D, pp. 170–177. DOI: 10.1093/ietisy/e91-d.2.170

Ioannidou K., Mertzios G., Nikolopoulos S. The Longest Path Problem has a Polynomial Solution on Interval Graphs, Algorithmica, 2011, Vol. 61, pp. 320–341. DOI: 10.1007/s00453-010-9411-3

Mertzios G. B., Corneil D. G. A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs, SIAM Journal on Discrete Mathematics, 2012, Vol. 26, Issue 3, pp. 940–963. DOI: 10.1137/100793529

Floyd R. Algorithm 97: Shortest Path, Communications of the ACM, 1961, Vol. 5 (6), pp. 344–348. DOI: 10.1145/367766.368168

Hougardy S. The Floyd-Warshall algorithm on graphs with negative cycles, Information Processing Letters, 2010, Vol. 110 (8–9), pp. 279–281. DOI: 10.1016/j.ipe.2010.02.001

Warshall S. Algorithm on Boolean matrices, Journal of the ACM, 1962, Vol. 9 (1), pp. 11–12. DOI: 10.1145/321105.321107

Shimbel A. Structural parameters of communication networks, Bulletin of Mathematical Biophysics, 1953, Vol. 15 (4), pp. 501–507. DOI: 10.1007/BF02476438

Dijkstra E. W. A note on two problems in connexion with graphs, Numerische Mathematik, 1959, Vol. 1, Issue 1, pp. 269–271. DOI:10.1007/BF01386390

Lipskyy V. Combinatory for programmers, Moscow, Mir Press., 1988, 213 p.

Batsamut V., Manzura S., Kosiak O. et al. Fast Algorithm for Calculating Transitive Closures of Binary Relations in the Structure of a Network Object, International Journal of Computing, 2021, Vol. 20(4), pp. 560–566. DOI: 10.47839/ijc.20.4.2444




How to Cite




Control in technical systems