EMOA*: A framework for search-based multi-objective path planning

In the Multi-Objective Shortest Path Problem (MO-SPP), one has to find paths on a graph that simultaneously minimize multiple objectives. It is not guaranteed that there exists a path that minimizes all objectives, and the problem thus aims to find the set of Pareto-optimal paths from the start to the goal vertex. A variety of multi-objective A*-based search approaches have been developed for this purpose. Typically, these approaches maintain a front set at each vertex during the search process to keep track of the Pareto-optimal paths that reach that vertex. Maintaining these front sets becomes burdensome and often slows down the search when there are many Pareto-optimal paths. In this article, we first introduce a framework for MO-SPP with the key procedures related to the front sets abstracted and highlighted, which provides a novel perspective for understanding the existing multi-objective A*-based search algorithms. Within this framework, we develop two different, yet closely related approaches to maintain these front sets efficiently during the search. We show that our approaches can find all cost-unique Pareto-optimal paths, and analyze their runtime complexity. We implement the approaches and compare them against baselines using instances with three, four and five objectives. Our experimental results show that our approaches run up to an order of magnitude faster than the baselines.

Authors

• Zhongqiang Ren Shanghai Jiao Tong University
• Carlos Hernández
• Maxim Likhachev Carnegie Mellon University
• Ariel Felner Computer and Information Sciences, Ben-Gurion University of the Negev
• Sven Koenig University of California & Örebro University
• Oren Salzman Technion
• Sivakumar Rathinam
• Howie Choset

Keywords

• Heuristic search
• Multi-objective optimization
• Path planning