<![CDATA[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.]]>
