METHOD OF ROUTING A GROUP OF MOBILE ROBOTS IN A FIXED NETWORK FOR SEARCHING THE MISSING OBJECTS IN A TECHNOLOGICAL DISASTER ZONE
DOI:
https://doi.org/10.15588/1607-3274-2023-1-13Keywords:
multi-agent system, group of mobile robots, routing, network object, weighted undirected (directed) graph, extreme paths, optimization criterion, methodAbstract
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.
References
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>3.0.co
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
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 V. M. Batsamut, S. O. Hodlevsky
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
