Hungarian and wave algorithms realization in the StateFlow program

Authors: Rostov E.E.
Published in issue: #3(92)/2024
DOI:
Category: Mechanical Engineering and Machine Science | Chapter: Robots, Mechatronics, and Robotic Systems
Keywords: StateFlow, MATLAB, target allocation algorithms, Hungarian algorithm, routing algorithms, wave algorithm, group robotics
Published: 28.07.2024

The paper describes the process of transferring the Hungarian target allocation algorithm, as well as the discrete space wave routing algorithm, to the StateFlow block-programming environment, which is a toolkit in the MATLAB development environment. It lists main steps in constructing a Hungarian algorithm and provides its mathematical model, objective function, and operation flowchart. The paper presents the wave algorithm and its operation description, as well as the algorithm objective function. StateFlow program blocks identifying the algorithms operation are shown. A conclusion is made on application of the selected routing and target allocation algorithms in the group robotics.

References

[1] Pshikhopov V.Kh. Group control of moving objects in uncertain environments. Moscow, Fizmatlit, 2015, 305 p. (In Russ.).

[2] Kalyaev I.A., Gaiduk A.R., Kapustyan S.G. Models and algorithms for collective control in groups of robots. Moscow, Fizmatlit, 2009, 280 p. (In Russ.).

[3] Mikhailov B.B., Nazarova A.V., Yushchenko A.S. Autonomous mobile robots - navigation and control. Bulletin of SFedU. Technical sciences, 2016, No. 2 (175), pp. 48-67. (In Russ.).

[4] Uspensky V.A. What is non-standard analysis? Moscow, Science. Main editorial office of physical and mathematical literature, 1987, 128 p. (In Russ.).

[5] Bellman R. On a Routing Problem. Quarterly of Applied Mathematics, 1958, vol. 16, no. 1, pp. 87–90.

[6] Dijkstra E.W. A note on two problems in connection with graphs. Numer. Math, 1959, vol.1, iss.1, pp.269–271.

[7] Ford L.R. Jr., Fulkerson D.R. Flows in Networks. Princeton, Princeton University Press, 1962.

[8] Hart P. E., Nilsson N. J., Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 1968, no. 2, pp. 100–107. https://doi.org/10.1109/TSSC.1968.300136

[9] Hart P.E., Nilsson N.J., Raphael B. Correction to “A Formal Basis for the Heuristic Determination of Minimum Cost Paths.” SIGART Newsletter, 1972, vol. 37, pp. 28–29. https://doi.org/10.1145/1056777.1056779

[10] Lee C.Y. An Algorithm for Path Connections and Its Applications. IRE Transactions on Electronic Computers, 1961, vol. EC-10, no. 2, pp. 346–365.