Enhanced Multi-Objective A* Using Balanced Binary Search Trees
This work addresses efficiency issues in multi-objective path planning for applications like logistics or robotics, representing an incremental improvement over prior MOA* methods.
The paper tackles the computational expense of Multi-Objective Shortest Path Problems (MO-SPP) as objectives increase by introducing a method using balanced binary search trees within the MOA* framework, resulting in speed improvements of up to an order of magnitude over existing techniques.
This work addresses a Multi-Objective Shortest Path Problem (MO-SPP) on a graph where the goal is to find a set of Pareto-optimal solutions from a start node to a destination in the graph. A family of approaches based on MOA* have been developed to solve MO-SPP in the literature. Typically, these approaches maintain a "frontier" set at each node during the search process to keep track of the non-dominated, partial paths to reach that node. This search process becomes computationally expensive when the number of objectives increases as the number of Pareto-optimal solutions becomes large. In this work, we introduce a new method to efficiently maintain these frontiers for multiple objectives by incrementally constructing balanced binary search trees within the MOA* search framework. We first show that our approach correctly finds the Pareto-optimal front, and then provide extensive simulation results for problems with three, four and five objectives to show that our method runs faster than existing techniques by up to an order of magnitude.