Anytime Approximate Bi-Objective Search
| Autor: | Han Zhang, Oren Salzman, T. K. Satish Kumar, Ariel Felner, Carlos Hernández Ulloa, Sven Koenig |
|---|---|
| Rok vydání: | 2022 |
| Zdroj: | Proceedings of the International Symposium on Combinatorial Search. 15:199-207 |
| ISSN: | 2832-9163 2832-9171 |
| Popis: | The Pareto-optimal frontier for a bi-objective search problem instance consists of all solutions that are not worse than any other solution in both objectives. The size of the Pareto-optimal frontier can be exponential in the size of the input graph, and hence finding it can be hard. Some existing works leverage a user-specified approximation factor epsilon to compute an approximate Pareto-optimal frontier that can be significantly smaller than the Pareto-optimal frontier. In this paper, we propose an anytime approximate bi-objective search algorithm, called Anytime Bi-Objective A*-epsilon (A-BOA*). A-BOA* is useful when deliberation time is limited. It first finds an approximate Pareto-optimal frontier quickly, iteratively improves it while time allows, and eventually finds the Pareto-optimal frontier. It efficiently reuses the search effort from previous iterations and makes use of a novel pruning technique. Our experimental results show that A-BOA* substantially outperforms baseline algorithms that do not reuse previous search effort, both in terms of runtime and number of node expansions. In fact, the most advanced variant of A-BOA* even slightly outperforms BOA*, a state-of-the-art bi-objective search algorithm, for finding the Pareto-optimal frontier. Moreover, given only a limited amount of deliberation time, A-BOA* finds solutions that collectively approximate the Pareto-optimal frontier much better than the solutions found by BOA*. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|