A Comparative Study of Three Multi-Objective Formulations for NSGA-II-Based Multi-Robot Path Planning

Ariadie Chandra Nugraha; Oyas Wahyunggoro; Adha Imam Cahyadi

doi:10.12928/biste.v8i5.16915

Authors

Ariadie Chandra Nugraha Universitas Gadjah Mada
Oyas Wahyunggoro Universitas Gadjah Mada
Adha Imam Cahyadi Universitas Gadjah Mada

DOI:

https://doi.org/10.12928/biste.v8i5.16915

Keywords:

Multi-Robot Path Planning, NSGA-II, Multi-Objective Optimization, Problem Formulation, Pareto Front, Collision Avoidance

Abstract

Existing works utilizing NSGA-II in multi-robot path planning have been primarily concerned with problem formulations where the aggregation of robot objectives, individuality of the objectives defined per each robot, and modeling of the collision avoidance through constraints and optimization objectives differ. The research contribution is systematic comparative analysis of three multi-objective optimization problem formulations within the same NSGA-II framework: (i) an aggregated objective formulation without constraints; (ii) a per-agent objective formulation with constraints; and (iii) a per-agent objective formulation without constraints. Initial population of NSGA-II are initialized using A* algorithm, while the formulations are tested on twelve scenarios comprising two to five robots for three 25 × 25 environments. Ten independent experiments are run for each scenario, and the non-parametric statistical tests are used. Aggregated and per-agent formulations with constraints maintain full feasibility for all scenarios and provide statistically equal results on the total travel time of up to four robots. On the other hand, the per-agent formulation without constraints loses feasibility and demonstrates highly inferior results for three or more robots. Front quality measures (hypervolume and inverted generational distance) calculated in a common objective space prove this and demonstrate the loss of diversity of the latter formulation in scenarios with five robots. The per-agent formulation with constraints is preferable: it matches the aggregated formulation in solution quality while exposing per-robot travel-time trade-offs and a clear Pareto front. This demonstrates the importance of problem formulation in affecting the convergence and termination behavior of NSGA-II.

References

J. Banfi, N. Basilico, and F. Amigoni, “Intractability of Time-Optimal Multirobot Path Planning on 2D Grid Graphs with Holes,” IEEE Robotics and Automation Letters, vol. 2, no. 4, pp. 1941–1947, 2017, https://doi.org/10.1109/LRA.2017.2715406.

H. Ma, “Graph-Based Multi-Robot Path Finding and Planning,” Current Robotics Reports, vol. 3, no. 3, pp. 77–84, 2022, https://doi.org/10.1007/s43154-022-00083-8.

S. Banik, S. C. Banik, and S. S. Mahmud, “Path Planning Approaches in Multi‐robot System: A Review,” Engineering Reports, vol. 7, no. 1, p. e13035, 2025, https://doi.org/10.1002/eng2.13035.

M. Khaneghaei, D. Asadi, B. Ebrahimi, Ö. Tutsoy, and Y. Nabavi Chashmi, “Intelligent hybrid optimization algorithms for multi-agent aerial robots path planning: review of the recent emerging trends and open research directions,” Artificial Intelligence Review, vol. 59, no. 3, p. 94, 2026, https://doi.org/10.1007/s10462-025-11472-8.

M. B. Aremu, G. Ahmed, S. Elferik, and A.-W. A. Saif, “Autonomous Mobile Robot Path Planning Techniques—A Review: Metaheuristic and Cognitive Techniques,” Robotics, vol. 15, no. 1, p. 23, 2026, https://doi.org/10.3390/robotics15010023.

Á. Madridano, A. Al-Kaff, D. Martín, and A. De La Escalera, “Trajectory planning for multi-robot systems: Methods and applications,” Expert Systems with Applications, vol. 173, p. 114660, 2021, https://doi.org/10.1016/j.eswa.2021.114660.

L. Wang and G. Liu, “Research on multi-robot collaborative operation in logistics and warehousing using A3C optimized YOLOv5-PPO model,” Frontiers in Neurorobotics, vol. 17, p. 1329589, 2024, https://doi.org/10.3389/fnbot.2023.1329589.

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, https://doi.org/10.1016/j.artint.2014.11.006.

J. Yu and S. M. LaValle, “Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics,” IEEE Transactions on Robotics, vol. 32, no. 5, pp. 1163–1177, 2016, https://doi.org/10.1109/TRO.2016.2593448.

K. Okumura, M. Machida, X. Défago, and Y. Tamura, “Priority inheritance with backtracking for iterative multi-agent path finding,” Artificial Intelligence, vol. 310, p. 103752, 2022, https://doi.org/10.1016/j.artint.2022.103752.

J. I. Solis Vidana, J. Motes, R. Sandstrom, and N. Amato, “Representation-Optimal Multi-Robot Motion Planning Using Conflict-Based Search,” IEEE Robotics and Automation Letters, vol. 6, no. 3, pp. 4608–4615, 2021, https://doi.org/10.1109/LRA.2021.3068910.

N. AbuJabal, R. Fareh, S. Sinan, M. Baziyad, and M. Bettayeb, “A comprehensive review of the latest path planning developments for multi-robot formation systems,” Robotica, vol. 41, no. 7, pp. 2079–2104, 2023, https://doi.org/10.1017/S0263574723000322.

J. Yu, “Research on mobile robot path planning and tracking control,” International Journal of Computational Science and Engineering, vol. 1, no. 1, p. 1, 2023, https://doi.org/10.1504/IJCSE.2023.10054169.

G. Nagib and W. Gharieb, “Path planning for a mobile robot using genetic algorithms,” in International Conference on Electrical, Electronic and Computer Engineering, 2004. ICEEC ’04., Cairo, Egypt: IEEE, pp. 185–189, 2004, https://doi.org/10.1109/ICEEC.2004.1374415.

B. K. Patle, G. Babu L, A. Pandey, D. R. K. Parhi, and A. Jagadeesh, “A review: On path planning strategies for navigation of mobile robot,” Defence Technology, vol. 15, no. 4, pp. 582–606, 2019, https://doi.org/10.1016/j.dt.2019.04.011.

M. Nazarahari, E. Khanmirza, and S. Doostie, “Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm,” Expert Systems with Applications, vol. 115, pp. 106–120, 2019, https://doi.org/10.1016/j.eswa.2018.08.008.

N. Wilde and J. Alonso-Mora, “Statistically Distinct Plans for Multiobjective Task Assignment,” IEEE Transactions on Robotics, vol. 40, pp. 2217–2232, 2024, https://doi.org/10.1109/TRO.2024.3359530.

Z. Ren, S. Rathinam, M. Likhachev, and H. Choset, “Multi-Objective Safe-Interval Path Planning With Dynamic Obstacles,” IEEE Robotics and Automation Letters, vol. 7, no. 3, pp. 8154–8161, 2022, https://doi.org/10.1109/LRA.2022.3187270.

K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182–197, 2002, https://doi.org/10.1109/4235.996017.

E. Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving the strength pareto evolutionary algorithm,” TIK report, vol. 103, 2001, https://doi.org/10.3929/ETHZ-A-004284029.

C. A. C. Coello, G. T. Pulido, and M. S. Lechuga, “Handling multiple objectives with particle swarm optimization,” IEEE Transactions on Evolutionary Computation, vol. 8, no. 3, pp. 256–279, 2004, https://doi.org/10.1109/TEVC.2004.826067.

K. Zhong, F. Xiao, and X. Gao, “Three-dimensional dynamic collaborative path planning for multiple UCAVs using an improved NSGAII,” Cluster Computing, vol. 28, no. 2, p. 75, 2025, https://doi.org/10.1007/s10586-024-04690-2.

D. Wang, G. Wang, and H. Wang, “Optimal Lane Change Path Planning Based on the NSGA-II and TOPSIS Algorithms,” Applied Sciences, vol. 13, no. 2, p. 1149, 2023, https://doi.org/10.3390/app13021149.

C. Lucas, D. Hernández-Sosa, D. Greiner, A. Zamuda, and R. Caldeira, “An Approach to Multi-Objective Path Planning Optimization for Underwater Gliders,” Sensors, vol. 19, no. 24, p. 5506, 2019, https://doi.org/10.3390/s19245506.

Z. Li, W. Ma, and H. Pang, “Multi-Objective Path Optimization Method for Maritime UAVs Equipped with Inertial Navigation Systems,” Journal of Marine Science and Engineering, vol. 13, no. 5, p. 870, 2025, https://doi.org/10.3390/jmse13050870.

Z. Liang, F. Li, and S. Zhou, “An Improved NSGA-II Algorithm for MASS Autonomous Collision Avoidance under COLREGs,” Journal of Marine Science and Engineering, vol. 12, no. 7, p. 1224, 2024, https://doi.org/10.3390/jmse12071224.

A. C. Nugraha, O. Wahyunggoro, and A. I. Cahyadi, “Path planning as multi-objective optimization using the NSGA-II algorithm,” In AIP Conference Proceedings, vol. 3281, no. 1, p. 030005, 2025, https://doi.org/10.1063/5.0261570.

P. Duan, Z. Yu, K. Gao, L. Meng, Y. Han, and F. Ye, “Solving the multi-objective path planning problem for mobile robot using an improved NSGA-II algorithm,” Swarm and Evolutionary Computation, vol. 87, p. 101576, 2024, https://doi.org/10.1016/j.swevo.2024.101576.

S. Liu, Q. Tian, and C. Tang, “Mobile Robot Path Planning Algorithm Based on NSGA-II,” Applied Sciences, vol. 14, no. 10, p. 4305, 2024, https://doi.org/10.3390/app14104305.

T. Zhou, Z. Zhou, H. Qiu, B. Niu, G. X.-G. Yue, and W. Pedrycz, “Two-stage knowledge-assisted coevolutionary NSGA-II for bi-objective path planning of multiple unmanned aerial vehicles,” Swarm and Evolutionary Computation, vol. 90, p. 101680, 2024, https://doi.org/10.1016/j.swevo.2024.101680.

E. García, J. R. Villar, Q. Tan, J. Sedano, and C. Chira, “An efficient multi-robot path planning solution using A* and coevolutionary algorithms,” Integrated Computer-Aided Engineering, vol. 30, no. 1, pp. 41–52, 2022, https://doi.org/10.3233/ICA-220695.

J. Zatarain Salazar, D. Hadka, P. Reed, H. Seada, and K. Deb, “Diagnostic benchmarking of many-objective evolutionary algorithms for real-world problems,” Engineering Optimization, vol. 57, no. 1, pp. 287–308, 2025, https://doi.org/10.1080/0305215X.2024.2381818.

H. Ma, Y. Zhang, S. Sun, T. Liu, and Y. Shan, “A comprehensive survey on NSGA-II for multi-objective optimization and applications,” Artificial Intelligence Review, vol. 56, no. 12, pp. 15217–15270, 2023, https://doi.org/10.1007/s10462-023-10526-z.

J. Blank and K. Deb, “Pymoo: Multi-Objective Optimization in Python,” IEEE Access, vol. 8, pp. 89497–89509, 2020, https://doi.org/10.1109/ACCESS.2020.2990567.

X. Lin, X. Peng, and L. Liang, “Simultaneous multi-objective path planning with cumulative hazardous dosage constraint for mobile detection robots in complex environments,” Expert Systems with Applications, vol. 298, p. 129808, 2026, https://doi.org/10.1016/j.eswa.2025.129808.

C. Audet, J. Bigeon, D. Cartier, S. Le Digabel, and L. Salomon, “Performance indicators in multiobjective optimization,” European Journal of Operational Research, vol. 292, no. 2, pp. 397–422, 2021, https://doi.org/10.1016/j.ejor.2020.11.016.

K. Shang, H. Ishibuchi, L. He, and L. M. Pang, “A Survey on the Hypervolume Indicator in Evolutionary Multiobjective Optimization,” IEEE Transactions on Evolutionary Computation, vol. 25, no. 1, pp. 1–20, 2021, https://doi.org/10.1109/TEVC.2020.3013290.

J. Yu, “Intractability of Optimal Multirobot Path Planning on Planar Graphs,” IEEE Robotics and Automation Letters, vol. 1, no. 1, pp. 33–40, 2016, https://doi.org/10.1109/LRA.2015.2503143.

H. Peng, Z. Xu, J. Qian, X. Dong, W. Li, and Z. Wu, “Evolutionary constrained optimization with hybrid constraint-handling technique,” Expert Systems with Applications, vol. 211, p. 118660, 2023, https://doi.org/10.1016/j.eswa.2022.118660.

C. Wang, Z. Liu, J. Qiu, and L. Zhang, “Adaptive constraint handling technique selection for constrained multi-objective optimization,” Swarm and Evolutionary Computation, vol. 86, p. 101488, 2024, https://doi.org/10.1016/j.swevo.2024.101488.

J. G. Hobbie, A. H. Gandomi, and I. Rahimi, “A Comparison of Constraint Handling Techniques on NSGA-II,” Archives of Computational Methods in Engineering, vol. 28, no. 5, pp. 3475–3490, 2021, https://doi.org/10.1007/s11831-020-09525-y.

I. Rahimi, A. H. Gandomi, F. Chen, and E. Mezura-Montes, “A Review on Constraint Handling Techniques for Population-based Algorithms: from single-objective to multi-objective optimization,” Archives of Computational Methods in Engineering, vol. 30, no. 3, pp. 2181–2209, 2023, https://doi.org/10.1007/s11831-022-09859-9.

J. Liang et al., “A Survey on Evolutionary Constrained Multiobjective Optimization,” IEEE Transactions on Evolutionary Computation, vol. 27, no. 2, pp. 201–221, 2023, https://doi.org/10.1109/TEVC.2022.3155533.

Z. Zhang, H. Yang, X. Bai, S. Zhang, and C. Xu, “The Path Planning of Mobile Robots Based on an Improved Genetic Algorithm,” Applied Sciences, vol. 15, no. 7, p. 3700, 2025, https://doi.org/10.3390/app15073700.

Y. Fan, Y. Peng, and J. Liu, “Advanced multi-objective trajectory planning for robotic arms using a multi-strategy enhanced NSGA-II algorithm,” PLOS One, vol. 20, no. 5, p. e0324567, 2025, https://doi.org/10.1371/journal.pone.0324567.

Z. Yao and Y. Xu, “An improved genetic algorithm for robot path planning,” Journal of Computational Methods in Sciences and Engineering, vol. 24, no. 3, pp. 1331–1340, 2024, https://doi.org/10.3233/JCM-247133.

R. M. Aziz, R. Mahto, K. Goel, A. Das, P. Kumar, and A. Saxena, "Modified genetic algorithm with deep learning for fraud transactions of ethereum smart contract," Appl. Sci., vol. 13, no. 2, p. 697, 2023, https://doi.org/10.3390/app13020697.

X. Wu, S. -H. Wu, J. Wu, L. Feng and K. C. Tan, "Evolutionary Computation in the Era of Large Language Model: Survey and Roadmap," in IEEE Transactions on Evolutionary Computation, vol. 29, no. 2, pp. 534-554, 2025, https://doi.org/10.1109/TEVC.2024.3506731.

Yang Xue, “Mobile Robot Path Planning with a Non-Dominated Sorting Genetic Algorithm,” Applied Sciences, vol. 8, no. 11, p. 2253, 2018, https://doi.org/10.3390/app8112253.

Z. Chen, J. Xiao, and G. Wang, “An Effective Path Planning of Intelligent Mobile Robot Using Improved Genetic Algorithm,” Wireless Communications and Mobile Computing, vol. 2022, no. 1, p. 9590367, 2022, https://doi.org/10.1155/2022/9590367.

J. Derrac, S. García, D. Molina, and F. Herrera, “A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms,” Swarm and Evolutionary Computation, vol. 1, no. 1, pp. 3–18, 2011, https://doi.org/10.1016/j.swevo.2011.02.002.

M. Nugraha and T. Stützle, “Automatically improving the anytime behaviour of optimisation algorithms,” European Journal of Operational Research, vol. 235, no. 3, pp. 569–582, 2014, https://doi.org/10.1016/j.ejor.2013.10.043.

S. Wang et al., “A Pareto dominance relation based on reference vectors for evolutionary many-objective optimization,” Applied Soft Computing, vol. 157, p. 111505, 2024, https://doi.org/10.1016/j.asoc.2024.111505.

K. Deb and H. Jain, “An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints,” IEEE Transactions on Evolutionary Computation, vol. 18, no. 4, pp. 577–601, 2014, https://doi.org/10.1109/TEVC.2013.2281535.

H. Jain and K. Deb, “An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point Based Nondominated Sorting Approach, Part II: Handling Constraints and Extending to an Adaptive Approach,” IEEE Transactions on Evolutionary Computation, vol. 18, no. 4, pp. 602–622, 2014, https://doi.org/10.1109/TEVC.2013.2281534.

Q. Zhang and H. Li, "MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition," in IEEE Transactions on Evolutionary Computation, vol. 11, no. 6, pp. 712-731, Dec. 2007, https://doi.org/10.1109/TEVC.2007.892759.

H. Ishibuchi, Y. Setoguchi, H. Masuda, and Y. Nojima, “Performance of Decomposition-Based Many-Objective Algorithms Strongly Depends on Pareto Front Shapes,” IEEE Transactions on Evolutionary Computation, vol. 21, no. 2, pp. 169–190, 2017, https://doi.org/10.1109/TEVC.2016.2587749.

W. Zhang, J. Liu, S. Tan, and H. Wang, “A decomposition-rotation dominance based evolutionary algorithm with reference point adaption for many-objective optimization,” Expert Systems with Applications, vol. 215, p. 119424, 2023, https://doi.org/10.1016/j.eswa.2022.119424.

S. Zhu, L. Zeng, and M. Cui, “Symmetrical Generalized Pareto Dominance and Adjusted Reference Vector Cooperative Evolutionary Algorithm for Many-Objective Optimization,” Symmetry, vol. 16, no. 11, p. 1484, 2024, https://doi.org/10.3390/sym16111484.

E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. G. Da Fonseca, “Performance assessment of multiobjective optimizers: an analysis and review,” IEEE Transactions on Evolutionary Computation, vol. 7, no. 2, pp. 117–132, 2003, https://doi.org/10.1109/TEVC.2003.810758.