Studi Penerapan Modifikasi Algoritma Flood fill Pada Multi-AgenUntuk Mencari Jalan tercepat Dalam Labirin

Semuil Tjiharjadi

doi:10.33557/jen5c387

Authors

Semuil Tjiharjadi

DOI:

https://doi.org/10.33557/jen5c387

Keywords:

multi-agents, maze, path finding, flood-fill

Abstract

This research is structured to serve as an essential foundation for the development of automated pathfinding systems using Multi-Agent Pathfinding (MAPF) methods within maze environments. Although the Flood fill algorithm has long been recognized and widely used for maze solving by single agents, its application in multi-agent configurations remains limited and requires adaptive innovation. Therefore, this study reviews various related research on MAPF and relevant maze algorithms, proposing modifications to the Flood fill algorithm to enable effective operation in multi-agent scenarios. By expanding the capacity of Flood fill, it is anticipated that the algorithm's advantages, such as low complexity and fast execution, can be harnessed in dynamic multi-agent systems. The primary contribution of this research highlights the significance of implementing a modified Flood fill algorithm as an innovative basis for pathfinding solutions involving multiple agents simultaneously, thereby opening opportunities for more efficient and adaptive robotic and automation system developments

Downloads

Download data is not yet available.

References

[1] S. Tjiharjadi and E. Setiawan, “Design and implementation of a path finding robot using flood fill algorithm,” Int. J. Mech. Eng. Robot. Res., 2016, doi: 10.18178/ijmerr.5.3.180-185.

[2] D. Silver, “Cooperative pathfinding,” in AI Game Programming Wisdom 3, 3rd ed., S. Rabin, Ed. Boston: Charles River Media, 2005, pp. 99–111.

[3] G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, “Conflict-based search for optimal multi-agent pathfinding,” Artificial Intelligence, vol. 219, pp. 40–66, 2015.

[4] R. Luna and K. E. Bekris, “Push and swap: Fast cooperative path-finding with completeness guarantees,” in Proc. 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI), 2011, pp. 294–300.

[5] S. Tjiharjadi, M. C. Wijaya, and E. Setiawan, “Optimization maze robot using A* and flood fill algorithm,” Int. J. Mech. Eng. Robot. Res., vol. 6, no. 5, 2017, doi: 10.18178/ijmerr.6.5.366-372.

[6] S. Tjiharjadi, S. Razali, H. A. Sulaiman, and G. Fernando, “Design of Multi-Agent Pathfinding Robot Using Improved Flood Fill Algorithm in Maze Exploration,” Int. J. Mech. Eng. Robot. Res., vol. 11, no. 8, pp. 631–638, 2022, doi: 10.18178/ijmerr.11.8.631-638.

[7] I. Elshamarka and A. Bakar Sayuti Saman, “Design and Implementation of a Robot for Maze-Solving using Flood-Fill Algorithm,” Int. J. Comput. Appl., vol. 56, no. 5, pp. 8–13, 2012, doi: 10.5120/8885-2882.

[8] G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, “Conflict-based search for optimal multi-agent pathfinding,” Artificial Intelligence, vol. 219, pp. 40–66, 2015.

[9] M. Linardakis, I. Varlamis, and G. Th. Papadopoulos, “Multi‑robot maze exploration using an efficient cost‑utility method,” *Proc. 13th Hellenic Conf. on Artificial Intelligence (SETN 2024)*, Piraeus, Greece, Jul. 2024, pp. 1–12. [Online]. Available: https://arxiv.org/abs/2407.14218

[10] H. Qiu, “Multi-agent navigation based on deep reinforcement learning and traditional pathfinding algorithm,” *arXiv preprint arXiv:2012.09134*, Dec. 2020. [Online]. Available: https://arxiv.org/abs/2012.09134

[11] B. Bertolini, “Flow field-based multi-agent pathfinding: A survey,” *Robotics and Autonomous Systems*, vol. 150, p. 104054, 2022.

[12] A. Jabbar, “Autonomous Navigation of Mobile Robot Based on Flood Fill Algorithm,” Iraqi J. Electr. Electron. Eng., vol. 12, no. 1, pp. 79–84, 2016, doi: 10.37917/ijeee.12.1.8.

[13] Y. Murata and Y. Mitani, “A Fast and Shorter Path Finding Method for Maze Images by Image Processing Techniques and Graph Theory,” J. Image Graph., vol. 2, no. 1, pp. 89–93, 2014, doi: 10.12720/joig.2.1.89-93.

[14] J. C. Young, A. Suryadibrata, R. Luhulima, and U. M. Nusantara, “Review of Various A * Pathfinding Implementations in Game Autonomous Agent,” Int. J. New Media Technol., 2019.

[15] K. Sharma and C. Munshi, “A comprehensive and comparative study of maze-solving techniques by implementing graph theory,” IOSR J. Comput. Eng., vol. 17, no. 1, pp. 24–29, 2015, doi: 10.9790/0661-17142429.

[16] K. Sharma and C. Munshi, “A comprehensive and comparative study of maze-solving techniques by implementing graph theory,” IOSR J. Comput. Eng., vol. 17, no. 1, pp. 24–29, 2015, doi: 10.9790/0661-17142429.

[17] I. R. Fahmi and D. J. Suroso, “A Simulation-Based Study of Maze-Solving-Robot Navigation for Educational Purposes,” J. Robot. Control, vol. 3, no. 1, pp. 48–54, 2022, doi: 10.18196/jrc.v3i1.12241.

[18] I. R. Fahmi and D. J. Suroso, “A Simulation-Based Study of Maze-Solving-Robot Navigation for Educational Purposes,” J. Robot. Control, vol. 3, no. 1, pp. 48–54, 2022, doi: 10.18196/jrc.v3i1.12241.

[19] J. Xin, J. Zhong, J. Sheng, P. Li, and Y. Cui, “Improved genetic algorithms based on data-driven operators for path planning of unmanned surface vehicle,” Int. J. Robot. Autom., 2019, doi: 10.2316/J.2019.206-0315.

[20] J. Xin, J. Zhong, J. Sheng, P. Li, and Y. Cui, “Improved genetic algorithms based on data-driven operators for path planning of unmanned surface vehicle,” Int. J. Robot. Autom., 2019, doi: 10.2316/J.2019.206-0315.

[21] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, *Introduction to Algorithms*, 3rd ed. Cambridge, MA, USA: MIT Press, 2009.

[22] D. Silver, “Cooperative pathfinding,” in *AI Game Programming Wisdom 3*, S. Rabin, Ed. Hingham, MA, USA: Charles River Media, 2005, pp. 99–111.

[23] R. Luna and K. E. Bekris, “Push and swap: Fast cooperative path-finding with completeness guarantees,” in *Proc. 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI)*, Barcelona, Spain, 2011, pp. 294–300.

[24] M. Dorigo and T. Stützle, *Ant Colony Optimization*. Cambridge, MA, USA: MIT Press, 2004.

[25] B. P. Gerkey and M. J. Mataric, "A formal analysis and taxonomy of task allocation in multi-robot systems," International Journal of Robotics Research, vol. 23, no. 9, pp. 939–954, 2004.

[26] B. Ponda, L. B. Johnson, E. Frazzoli, and J. P. How, “Consensus-based bundle algorithm for multi-UAV task assignment,” *International Journal of Robust and Nonlinear Control*, vol. 21, no. 12, pp. 1467–1500, Aug. 2011, doi: 10.1002/rnc.1752.

[27] R. Luna and K. E. Bekris, “Push and swap: Fast cooperative path-finding with completeness guarantees,” in *Proc. 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI)*, Barcelona, Spain, 2011, pp. 294–300.

[28] B. de Wilde, G. C. de Croon, and M. A. Dorigo, “Push and rotate: Cooperative multi-agent pathfinding,” in *Proc. 24th Int. Joint Conf. on Artificial Intelligence (IJCAI)*, Buenos Aires, Argentina, 2015, pp. 2045–2051.

[29] B. Yamauchi, “Frontier-based exploration using multiple robots,” in *Proc. 2nd Int. Conf. on Autonomous Agents*, Minneapolis, MN, USA, 1998, pp. 47–53.

[30] T. W. Malone and K. Crowston, “The interdisciplinary study of coordination,” *ACM Computing Surveys*, vol. 26, no. 1, pp. 87–119, Mar. 1994, doi: 10.1145/174666.174668.