Review of Path Planning, Search, and Area Coverage Methods for Multi-Agent Systems with Emphasis on Mathematical and Ergodic Approaches

Prepared By Editor-in-Chief

International Journal of Innovative Solutions in Engineering is published semi-annually.

ISSN: 3029-3200

Review Article

DOI: https://doi.org/10.47960/3029-3200.2026.2.2.10
Citations (Crossref, OpenAlex): …
Mila Zovko* ORCID profile of Mila Zovko and Ivana Marić ORCID profile of Ivana Marić
*CAmila.zovko@fpmoz.sum.ba
ivana.maric@fpmoz.sum.ba

Full text:

In Press

This article belongs to Vol. 2 No. 2, 2026

M. Zovko and I. Marić, “Review of Path Planning, Search, and Area Coverage Methods for Multi-Agent Systems with Emphasis on Mathematical and Ergodic Approaches,” International Journal of Innovative Solutions in Engineering, vol. 2, no. 2, pp. 10–26, doi: 10.47960/3029-3200.2026.2.2.10.

pages 10-26

Download a citation file:

Preview and download a citation file in BibTex format that can be imported by citation management software, including Mendeley, EndNote, ProCite, RefWorks, and Reference Manager.

This article is archived in Zenodo

Zenodo Archive DOI: 10.5281/19400759

Abstract

This paper provides a structured overview of path planning, search, and area coverage problems, with a focus on multi-agent autonomous systems and mathematically grounded approaches. The evolution of path planning is reviewed, from classical graph-based, sampling-based, and artificial potential field methods to recent centralized and decentralized multi-agent pathfinding (MAPF) strategies. Search methods are examined from early Koopman models to adaptive real-time algorithms, while area coverage approaches are discussed from distributed Voronoi-based strategies to modern ergodic methods such as SMC and HEDAC. The interconnections between path planning, search, and coverage are highlighted, and a comparative analysis of the reviewed methods is presented, emphasizing their advantages, limitations, and suitability for operation in uncertain environments with limited resources.

Keywords

Path Planning, Search, Area Coverage, Multi-Agent Systems, Mathematical Modeling

ijise ID

19

URI

https://ijise.ba/article/19/

Publication Date

In Press

References

  1. S. M. LaValle, Planning Algorithms. Cambridge: Cambridge University Press, 2006. doi: https://doi.org/10.1017/CBO9780511546877.
  2. H. Choset, K. M. Lynch, S. Hutchinson, G. A. Kantor, and W. Burgard, Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, 2005.
  3. R. Tarjan, “Depth-First Search and Linear Graph Algorithms,”SIAM J. Comput., vol. 1, no. 2, pp. 146–160, Jun. 1972, doi: https://doi.org/10.1137/0201010.
  4. E. F. Moore, “The shortest path through a maze,” pp. 285–292, Jan. 1959, [Online]. Available: https://ci.nii.ac.jp/naid/10015375086
  5. E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numer. Math., vol. 1, no. 1, pp. 269–271, Dec. 1959, doi: https://doi.org/10.1007/BF01386390.
  6. P. Hart, N. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,”IEEE Trans. Syst. Sci. Cyber., vol. 4, no. 2, pp. 100–107, 1968, doi: https://doi.org/10.1109/TSSC.1968.300136.
  7. L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,”IEEE Trans. Robot. Automat., vol. 12, no. 4, pp. 566–580, Aug. 1996, doi: https://doi.org/10.1109/70.508439.
  8. S. M. LaValle, “Rapidly-exploring random trees: A new tool for path planning,” The annual research report, 1998. [Online]. Available: https://api.semanticscholar.org/CorpusID:14744621
  9. S. M. LaValle and J. J. Kuffner, “Randomized Kinodynamic Planning,”The International Journal of Robotics Research, vol. 20, no. 5, pp. 378–400, May 2001, doi: https://doi.org/10.1177/02783640122067453.
  10. O. Khatib, “Real-Time Obstacle Avoidance for Manipulators and Mobile Robots,”The International Journal of Robotics Research, vol. 5, no. 1, pp. 90–98, Mar. 1986, doi: https://doi.org/10.1177/027836498600500106.
  11. B. H. Krogh, “A generalized potential field approach to obstacle avoidance control,” in SME Conference Proceedings Robotics Research: The Next Five Years and Beyond, Bethlehem, PA, 1984.
  12. C. Thorpe and L. Matthies, “Path Relaxation: Path Planning for a Mobile Robot,” in OCEANS 1984, Sep. 1984, pp. 576–581. doi: https://doi.org/10.1109/OCEANS.1984.1152243.
  13. B. Krogh and C. Thorpe, “Integrated path planning and dynamic steering control for autonomous vehicles,” in 1986 IEEE International Conference on Robotics and Automation Proceedings, Apr. 1986, pp. 1664–1669. doi: https://doi.org/10.1109/ROBOT.1986.1087444.
  14. P. Vadakkepat, K. C. Tan, and W. Ming-Liang, “Evolutionary artificial potential fields and their application in real time robot path planning,” in Proceedings of the 2000 Congress on Evolutionary Computation. CEC00 (Cat. No.00TH8512), Jul. 2000, pp. 256–263 vol.1. doi: https://doi.org/10.1109/CEC.2000.870304.
  15. D. Yagnik, J. Ren, and R. Liscano, “Motion planning for multi-link robots using Artificial Potential Fields and modified Simulated Annealing,” in Proceedings of 2010 IEEE/ASME International Conference on Mechatronic and Embedded Systems and Applications, Jul. 2010, pp. 421–427. doi: https://doi.org/10.1109/MESA.2010.5551989.
  16. R. Daily and D. M. Bevly, “Harmonic potential field path planning for high speed vehicles,” in 2008 American Control Conference, Jun. 2008, pp. 4609–4614. doi: https://doi.org/10.1109/ACC.2008.4587222.
  17. W. Afzal and A. A. Masoud, “Harmonic potential-based Communication-Aware Navigation of mobile agents in cluttered spaces,” in 2016 IEEE 55th Conference on Decision and Control (CDC), Las Vegas, NV, USA: IEEE, Dec. 2016, pp. 5146–5151. doi: https://doi.org/10.1109/CDC.2016.7799056.
  18. K. Sato, “Deadlock-free motion planning using the Laplace potential field, “Advanced Robotics, vol. 7, no. 5, pp. 449–461, Jan. 1992, doi: https://doi.org/10.1163/156855393X00285.
  19. A. Saudi and J. Sulaiman, “Path planning for mobile robot with half sweep successive over-relaxation (HSSOR) iterative method,” in Proceedings of the Symposium on Progress in Information and Communication Technology (SPICT), Kuala Lumpur, Malaysia, 2009, pp. 57–62.
  20. D. E. Goldberg and J. H. Holland, “Genetic Algorithms and Machine Learning,”Machine Learning, vol. 3, no. 2–3, pp. 95–99, Oct. 1988, doi: https://doi.org/10.1023/A:1022602019183.
  21. J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proceedings of ICNN’95 – International Conference on Neural Networks, Nov. 1995, pp. 1942–1948 vol.4. doi: https://doi.org/10.1109/ICNN.1995.488968.
  22. M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53–66, Apr. 1997, doi: https://doi.org/10.1109/4235.585892.
  23. D. Karaboğa, “Artificial bee colony algorithm,” Scholarpedia, vol. 5, p. 6915, 2010.
  24. K. M. Passino, “Biomimicry of bacterial foraging for distributed optimization and control,” IEEE Control Systems Magazine, vol. 22, no. 3, pp. 52–67, Jun. 2002, doi: https://doi.org/10.1109/MCS.2002.1004010.
  25. X.-S. Yang, “Genetic Algorithms,” in Nature-Inspired Optimization Algorithms, Elsevier, 2021, pp. 91–100. doi: https://doi.org/10.1016/B978-0-12-821986-7.00013-5.
  26. J. Del Ser et al., “Bio-inspired computation: Where we stand and what’s next,”Swarm and Evolutionary Computation, vol. 48, pp. 220–250, Aug. 2019, doi: https://doi.org/10.1016/j.swevo.2019.04.008.
  27. 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, Feb. 2015, doi: https://doi.org/10.1016/j.artint.2014.11.006.
  28. G. Sharon, R. Stern, A. Felner, and N. Sturtevant, “Conflict-based search,” in Proc. AAAI Conf. Artif. Intell, 2012, pp. 563-569.
  29. G. Sharon, R. Stern, A. Felner, and N. Sturtevant, “Meta-Agent Conflict-Based Search For Optimal Multi-Agent Path Finding,”SOCS, vol. 3, no. 1, pp. 97–104, Aug. 2021, doi: https://doi.org/10.1609/socs.v3i1.18244.
  30. E. Boyarski, A. Felner, R. Stern, G. Sharon, E. Shimony, O. Bezalel, and D. Tolpin, “Improved conflict-based search for optimal multi-agent path finding,” in 24th International Joint Conference on Artificial Intelligence (IJCAI), 2015.
  31. V. R. Desaraju and J. P. How, “Decentralized path planning for multi-agent teams in complex environments using rapidly-exploring random trees,” in 2011 IEEE International Conference on Robotics and Automation, May 2011, pp. 4956–4961. doi: https://doi.org/10.1109/ICRA.2011.5980392.
  32. H. Wang and M. Rubenstein, “Walk, Stop, Count, and Swap: Decentralized Multi-Agent Path Finding With Theoretical Guarantees,”IEEE Robotics and Automation Letters, vol. 5, no. 2, pp. 1119–1126, Apr. 2020, doi: https://doi.org/10.1109/LRA.2020.2967317.
  33. G. Sartoretti et al., “PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning,” IEEE Robotics and Automation Letters, vol. 4, no. 3, pp. 2378–2385, Jul. 2019, doi: https://doi.org/10.1109/LRA.2019.2903261.
  34. J. van den Berg, S. J. Guy, M. Lin, and D. Manocha, “Optimal Reciprocal Collision Avoidance for Multi-Agent Navigation,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), IEEE, 2010.
  35. M. Parooei, M. Tale Masouleh, and A. Kalhor, “MAP3F: a decentralized approach to multi-agent pathfinding and collision avoidance with scalable 1D, 2D, and 3D feature fusion,”Intel Serv Robotics, vol. 17, no. 3, pp. 401–418, May 2024, doi: https://doi.org/10.1007/s11370-024-00537-2.
  36. T. Chauvin, D. Gianazza, and N. Durand, “ORCA-A*: A Hybrid Reciprocal Collision Avoidance and Route Planning Algorithm for UAS in Dense Urban Areas,” in Proceedings of the SESAR Innovation Days 2024, Rome, Italy, 2024.
  37. R. Yonetani, T. Taniai, M. Barekatain, M. Nishimura, and A. Kanezaki, “Path Planning using Neural A* Search,” 2020,arXiv. doi: https://doi.org/10.48550/ARXIV.2009.07476.
  38. T. Takahashi, H. Sun, D. Tian, and Y. Wang, “Learning Heuristic Functions for Mobile Robot Path Planning Using Deep Neural Networks,” ICAPS, vol. 29, pp. 764–772, Jul. 2019, doi: https://doi.org/10.1609/icaps.v29i1.3545.
  39. S. Ivić, B. Crnković, and I. Mezić, “Ergodicity-Based Cooperative Multiagent Area Coverage via a Potential Field,”IEEE Transactions on Cybernetics, vol. 47, no. 8, pp. 1983–1993, Aug. 2017, doi: https://doi.org/10.1109/TCYB.2016.2634400.
  40. G. Mathew, A. Surana, and I. Mezić, “Uniform coverage control of mobile sensor networks for dynamic target detection,” in 49th IEEE Conference on Decision and Control (CDC), Dec. 2010, pp. 7292–7299. doi: https://doi.org/10.1109/CDC.2010.5717451.
  41. B. O. Koopman, “Search and Screening,” Arlington, VA, 1946.
  42. B. O. Koopman, “The Theory of Search. I. Kinematic Bases,” Operations Research, vol. 4, no. 3, pp. 324–346, Jun. 1956, doi: https://doi.org/10.1287/opre.4.3.324.
  43. B. O. Koopman, “The Theory of Search. II. Target Detection,” Operations Research, vol. 4, no. 5, pp. 503–531, Oct. 1956, doi: https://doi.org/10.1287/opre.4.5.503.
  44. B. O. Koopman, “The Theory of Search: III. The Optimum Distribution of Searching Effort,” Operations Research, vol. 5, no. 5, pp. 613–626, Oct. 1957, doi: https://doi.org/10.1287/opre.5.5.613.
  45. B. O. Koopman, Search and Screening: General Principles with Historical Applications. New York: Pergamon Press, 1980.
  46. J. R. Frost and L. D. Stone, Review of Search Theory: Advances and Applications to Search and Rescue Decision Support. Groton, CT: US Coast Guard Research and Development Center, 2001.
  47. E. Kagan and I. Ben-Gal, Search and Foraging, 0 ed. Chapman and Hall/CRC, 2015. doi: https://doi.org/10.1201/b18604.
  48. R. Mickelsen and L. D. Stone, “Theory of Optimal Search.,”Journal of the American Statistical Association, vol. 71, no. 356, p. 1008, Dec. 1976, doi: https://doi.org/10.2307/2286890.
  49. S. S. Brown, “Optimal Search for a Moving Target in Discrete Time and Space,” Operations Research, vol. 28, no. 6, pp. 1275–1289, Dec. 1980, doi: https://doi.org/10.1287/opre.28.6.1275.
  50. A. R. Washburn, “On a search for a moving target,”Naval Research Logistics, vol. 27, no. 2, pp. 315–322, Jun. 1980, doi: https://doi.org/10.1002/nav.3800270214.
  51. J. N. Eagle, “The Optimal Search for a Moving Target When the Search Path Is Constrained,”Operations Research, vol. 32, no. 5, pp. 1107–1115, Oct. 1984, doi: https://doi.org/10.1287/opre.32.5.1107.
  52. S. Singh and V. Krishnamurthy, “The optimal search for a Markovian target when the search path is constrained: the infinite-horizon case,” IEEE Trans. Automat. Contr., vol. 48, no. 3, pp. 493–497, Mar. 2003, doi: https://doi.org/10.1109/TAC.2003.809165.
  53. O. Hellman, “On the Optimal Search for a Randomly Moving Target,”SIAM J. Appl. Math., vol. 22, no. 4, pp. 545–552, Jun. 1972, doi: https://doi.org/10.1137/0122049.
  54. O. Hellman, Introduction of the Theory of Optimal Search. Moscow, Russia: Nauka, 1985.
  55. M. Lukka, “On the Optimal Searching Tracks for a Moving Target,”SIAM J. Appl. Math., vol. 32, no. 1, pp. 126–132, Jan. 1977, doi: https://doi.org/10.1137/0132010.
  56. A. Ohsumi, “Optimal search for a Markovian target,” Naval Research Logistics, vol. 38, no. 4, pp. 531–554, Aug. 1991, doi: https://doi.org/10.1002/1520-6750(199108)38:4<531::AID-NAV3220380407>3.0.CO;2-L.
  57. E. Kagan, G. Goren, and I. Ben-Gal, “Probabilistic double-distance algorithm of search after static or moving target by autonomous mobile agent,” in 2010 IEEE 26-th Convention of Electrical and Electronics Engineers in Israel, Nov. 2010, pp. 000160–000164. doi: https://doi.org/10.1109/EEEI.2010.5661898.
  58. G. Chernikhovsky, E. Kagan, G. Goren, and I. Ben-Gal, “Path Planning for Sea Vessel Search Using Wideband Sonar,” in Proceedings of the 27th IEEE Convention of Electrical and Electronics Engineers in Israel (EEEI), Eilat, Israel, 2012. doi: https://doi.org/10.1109/EEEI.2012.6377122.
  59. E. Kagan, G. Goren, and I. Ben-Gal, “Algorithm of Search for Static or Moving Target by Autonomous Mobile Agent with Erroneous Sensor,” in Proceedings of the 27th IEEE Convention of Electrical and Electronics Engineers in Israel (EEEI), Eilat, Israel, 2012. doi: https://doi.org/10.1109/EEEI.2012.6377124.
  60. M. Israel, E. Khmelnitsky, and E. Kagan, “Search for a Mobile Target by Ground Vehicle on a Topographic Terrain,” in Proceedings of the 27th IEEE Convention of Electrical and Electronics Engineers in Israel (EEEI), Eilat, Israel, 2012. doi: https://doi.org/10.1109/EEEI.2012.6377123.
  61. A. Khan, E. Yanmaz, and B. Rinner, “Information merging in multi-UAV cooperative search,” in 2014 IEEE International Conference on Robotics and Automation (ICRA), 2014, pp. 3122–3129. doi: https://doi.org/10.1109/ICRA.2014.6907308.
  62. Y. Yang, M. M. Polycarpou, and A. A. Minai, “Multi-UAV Cooperative Search Using an Opportunistic Learning Method,”Journal of Dynamic Systems, Measurement, and Control, vol. 129, no. 5, pp. 716–728, Sep. 2007, doi: https://doi.org/10.1115/1.2764515.
  63. S. Ivić, B. Crnković, H. Arbabi, S. Loire, P. Clary, and I. Mezić, “Search strategy in a complex and dynamic environment: the MH370 case,”Sci Rep, vol. 10, no. 1, p. 19640, Nov. 2020, doi: https://doi.org/10.1038/s41598-020-76274-0.
  64. G. Mathew and I. Mezić, “Metrics for ergodicity and design of ergodic dynamics for multi-agent systems,” Physica D: Nonlinear Phenomena, vol. 240, no. 4–5, pp. 432–442, Feb. 2011, doi: https://doi.org/10.1016/j.physd.2010.10.010.
  65. C. Y. Lee, “An Algorithm for Path Connections and Its Applications,” IRE Transactions on Electronic Computers, vol. EC-10, no. 3, pp. 346–365, Sep. 1961, doi: https://doi.org/10.1109/TEC.1961.5219222.
  66. S. Alamri, S. Alshehri, W. Alshehri, H. Alamri, A. Alaklabi, and T. Alhmiedat, “Autonomous Maze Solving Robotics: Algorithms and Systems,”IJMERR, pp. 668–675, 2021, doi: https://doi.org/10.18178/ijmerr.10.12.668-675.
  67. E. H. Kivelevitch and K. Cohen, “Multi-Agent Maze Exploration,”Journal of Aerospace Computing, Information, and Communication, vol. 7, no. 12, pp. 391–405, Dec. 2010, doi: https://doi.org/10.2514/1.46304.
  68. H. Alian, “Multi-Agent Asynchronous Real-time Maze-solving,” University of Alberta Library, 2022. doi: https://doi.org/10.7939/R3-ESGW-9V62.
  69. S. Tjiharjadi, S. Razali, and H. A. Sulaiman, “A Systematic Literature Review of Multi-agent Pathfinding for Maze Research,”JAIT, vol. 13, no. 4, 2022, doi: https://doi.org/10.12720/jait.13.4.358-367.
  70. A. Nandy, S. Seshathri, and A. Sarkar, “Maze Solving Using Deep Q-Network,” in Advances In Robotics – 6th International Conference of The Robotics Society, Ropar India: ACM, Jul. 2023, pp. 1–5. doi: https://doi.org/10.1145/3610419.3610458.
  71. Z. Husain, A. Al Zaabi, H. Hildmann, F. Saffre, D. Ruta, and A. F. Isakovic, “Search and Rescue in a Maze-like Environment with Ant and Dijkstra Algorithms,” Drones, vol. 6, no. 10, p. 273, Sep. 2022, doi: https://doi.org/10.3390/drones6100273.
  72. M. Zovko, “Exploration of graphs and continuous domains by a cooperative multi-agent system using a potential field,” Doctoral Thesis, University of Zagreb, Faculty of Science, 2025.
  73. Y. Gabriely and E. Rimon, “Spanning-tree based coverage of continuous areas by a mobile robot,”Annals of Mathematics and Artificial Intelligence, vol. 31, no. 1–4, pp. 77–98, Oct. 2001, doi: https://doi.org/10.1023/A:1016610507833.
  74. J. Cortes, S. Martinez, T. Karatas, and F. Bullo, “Coverage control for mobile sensing networks,” IEEE Transactions on Robotics and Automation, vol. 20, no. 2, pp. 243–255, Apr. 2004, doi: https://doi.org/10.1109/TRA.2004.824698.
  75. R. Mitra and I. Saha, “Online On-Demand Multi-Robot Coverage Path Planning,” in 2024 IEEE International Conference on Robotics and Automation (ICRA), May 2024, pp. 14583–14589. doi: https://doi.org/10.1109/ICRA57147.2024.10611610.
  76. S. Ivić, A. Andrejčuk, and S. Družeta, “Autonomous control for multi-agent non-uniform spraying,”Applied Soft Computing, vol. 80, pp. 742–760, Jul. 2019, doi: https://doi.org/10.1016/j.asoc.2019.05.001.
  77. T. Löw, J. Maceiras, and S. Calinon, “drozBot: Using Ergodic Control to Draw Portraits,”IEEE Robotics and Automation Letters, vol. 7, no. 4, pp. 11728–11734, Oct. 2022, doi: https://doi.org/10.1109/LRA.2022.3186735.
  78. S. Ivić, “Motion Control for Autonomous Heterogeneous Multiagent Area Search in Uncertain Conditions,”IEEE Transactions on Cybernetics, vol. 52, no. 5, pp. 3123–3135, May 2022, doi: https://doi.org/10.1109/TCYB.2020.3022952.
  79. S. Ivić, A. Sikirica, and B. Crnković, “Constrained multi-agent ergodic area surveying control based on finite element approximation of the potential field,” Engineering Applications of Artificial Intelligence, vol. 116, p. 105441, Nov. 2022, doi: https://doi.org/10.1016/j.engappai.2022.105441.
  80. S. Ivić, B. Crnković, L. Grbčić, and L. Matleković, “Multi-UAV trajectory planning for 3D visual inspection of complex structures,” Automation in Construction, vol. 147, p. 104709, Mar. 2023, doi: https://doi.org/10.1016/j.autcon.2022.104709.
  81. S. Lukhozi, “Cooperative Multi-Agent Coverage Problem,” University of KwaZulu-Natal, School of Mathematics, Statistics and Computer Science, Durban, South Africa, 2024.
Post Views: 46

Investigation on Ampacity for Direct Burial Low-Voltage Power Cables

ISSN: 3029-3200

Reach out to us for more opportunities

If you have any inquiries, please use the information below to contact us.

Contact Us

All articles published in the International Journal of Innovative Solutions in Engineering (IJISE) are preserved in Zenodo for long-term archiving and global accessibility.

© 2026 by The Author(s). Licensee IJISE by Faculty of Mechanical Engineering, Computing and Electrical Engineering, University of Mostar. All articles are an open-access and distributed under the terms and conditions of the CC BY 4.0Creative Commons LicenseAttribution 4.0 International (CC BY 4.0)