Simple and efficient bi-objective search algorithms via fast dominance checks
Simple and efficient bi-objective search algorithms via fast dominance checks
复制标题
DOI：
10.1016/j.artint.2022.103807
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Carlos Hernández;W. Yeoh;Jorge A. Baier;Han Zhang;L. Suazo;Sven Koenig;Oren Salzman
中科院分区：
文献类型：
--
作者：
Carlos Hernández;W. Yeoh;Jorge A. Baier;Han Zhang;L. Suazo;Sven Koenig;Oren Salzman
许多有趣的搜索问题都可以表示为双目标搜索问题，即两种成本都必须最小化的搜索问题，例如，运输问题的旅行距离和时间。而不是寻找一个单一的最优路径，我们计算一个帕累托最优边界的双目标搜索，这是一组路径，其中没有两个路径相互支配。双目标搜索算法在每次发现新路径时执行优势检查。因此，这些检查的效率是性能的关键。在这篇文章中，我们提出了两种双目标搜索问题的算法。首先，我们考虑计算连接给定起始状态与给定目标状态的路径的帕累托最优边界的问题。我们提出了双目标A*（BOA*），一个启发式搜索算法的基础上，A*，为这个问题。其次，我们考虑的问题，计算一个Pareto最优边界的每个statesof搜索图，其中包含的路径，连接一个给定的开始状态与s。我们提出了双目标Dijkstra（BOD），这是基于BOA*，这个问题。BOA* 和BOD的一个共同特点是，所有的优势检查都是在恒定的时间内执行的，这与以前算法的优势检查不同。我们在实验评估中表明，BOA* 和BOD都比最先进的双目标搜索算法快得多。
Many interesting search problems can be formulated as bi-objective search problems, that is, search problems where two kinds of costs have to be minimized, for example, travel distance and time for transportation problems. Instead of looking for a single optimal path, we compute a Pareto-optimal frontier in bi-objective search, which is a set of paths in which no two paths dominate each other. Bi-objective search algorithms perform dominance checks each time a new path is discovered. Thus, the efficiency of these checks is key to performance. In this article, we propose algorithms for two kinds of bi-objective search problems. First, we consider the problem of computing the Pareto-optimal frontier of the paths that connect a given start state with a given goal state. We propose Bi-Objective A* (BOA*), a heuristic search algorithm based on A*, for this problem. Second, we consider the problem of computing one Pareto-optimal frontier for each statesof the search graph, which contains the paths that connect a given start state withs. We propose Bi-Objective Dijkstra (BOD), which is based on BOA*, for this problem. A common feature of BOA* and BOD is that all dominance checks are performed in constant time, unlike the dominance checks of previous algorithms. We show in our experimental evaluation that both BOA* and BOD are substantially faster than state-of-the-art bi-objective search algorithms.