A Customized Niching Methodology for the Many-Objective Pathfinding Problem

Abstract

Route planning, also called pathfinding, is an essential element in various fields such as logistics and mobile robotics with a considerable impact on the engineering of such systems. Pathfinding problems usually contain multiple conflicting objectives, which pose a challenge for the design of algorithms. Additionally, in pathfinding applications, several paths can map to similar or even exact objective values. Typical multi-objective optimization algorithms prioritize the selection mechanism in the objective space, making such multi-modal solutions challenging to find. This paper introduces a new approach to preserve diversity in the decision space, which is particularly well suited to pathfinding problems. In the decision space, we impose a total order on a naturally unordered set of paths and measure the solutions' isolation precisely, by utilizing discrete Fréchet distance. In this concept, diversification in the decision-space replaces the widely known concept of crowding distance. An examination of the proposed method is conducted using a variety of benchmarks and a real-world example.