Enhanced Multi-Objective A* Using Balanced Binary Search Trees

Authors

  • Zhongqiang Ren Carnegie Mellon University
  • Richard Zhan Carnegie Mellon University
  • Sivakumar Rathinam Texas A & M
  • Maxim Likhachev Carnegie Mellon University
  • Howie Choset Carnegie Mellon

DOI:

https://doi.org/10.1609/socs.v15i1.21764

Keywords:

Combinatorial Optimization, Search In Robotics

Abstract

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.

Downloads

Published

2022-07-17