Navigating Path-Influenced Environments using Evolutionary Multi-Objective Optimization

This paper explores multi-objective pathfinding in path-influenced environments. These environments contain movable obstacles which can be shifted by the agents. This way, the agents actively change their environment while traversing on their path. Therefore, pathfinding takes on a new dimension. While it has been extensively studied across various domains, finding an optimal path in a path-influenced environment introduces new challenges. In this paper, we propose several real-world inspired problem instances. Then we formally describe this sort of problem as a multi-objective optimization problem and finally evaluate the performance of seven state-of-the-art multi-objective evolutionary algorithms on our problem instances. The results indicate that the evolutionary approach can generate sets of non-dominated solutions for this new problem. The performance of the algorithms in terms of convergence and diversity of the Pareto front highly depends on the way the encountered obstacles are handled, as well as the obstacle distribution on the map. Among the algorithms, AGE-MOEA and SPEA-II demonstrate the best convergence across the majority of problem instances.