论文标题
增强的多目标A*具有部分扩展
Enhanced Multi-Objective A* with Partial Expansion
论文作者
论文摘要
通常在图表上提出的多目标最短路径问题（MO-SPP），在优化多个目标的同时，确定了从启动顶点到目标顶点的一组路径。通常，没有一个单个解决方案路径可以同时优化所有目标，因此问题试图找到一组所谓的帕累托最佳解决方案。为了解决这个问题，最近开发了几种多目标A*（MOA*）算法来快速计算质量保证的解决方案。但是，这些MOA*算法通常患有高内存使用情况，尤其是当该图的分支因子（即任何顶点的邻居数）很大时。因此，这项工作旨在减少MOA*的高度记忆消耗，而运行时间几乎没有增加。通过概括和统一几种单目标搜索算法，我们开发了运行时和内存有效的MOA*（RME-MOA*）方法，可以通过调整两个用户定义的超参数来平衡运行时和内存效率之间的平衡。
The Multi-Objective Shortest Path Problem (MO-SPP), typically posed on a graph, determines a set of paths from a start vertex to a destination vertex while optimizing multiple objectives. In general, there does not exist a single solution path that can simultaneously optimize all the objectives and the problem thus seeks to find a set of so-called Pareto-optimal solutions. To address this problem, several Multi-Objective A* (MOA*) algorithms were recently developed to quickly compute solutions with quality guarantees. However, these MOA* algorithms often suffer from high memory usage, especially when the branching factor (i.e. the number of neighbors of any vertex) of the graph is large. This work thus aims at reducing the high memory consumption of MOA* with little increase in the runtime. By generalizing and unifying several single- and multi-objective search algorithms, we develop the Runtime and Memory Efficient MOA* (RME-MOA*) approach, which can balance between runtime and memory efficiency by tuning two user-defined hyper-parameters.
