1. MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with Known Pareto Front
- Author
-
Quemy, Alexandre, Schoenauer, Marc, Dreo, Johann, YData Lab [Seattle, USA], Poznan University of Technology (PUT), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris-Saclay, Biomédecine computationelle des systèmes / Computational systems biomedicine, Institut Pasteur [Paris] (IP)-Université Paris Cité (UPCité), and Hub Bioinformatique et Biostatistique - Bioinformatics and Biostatistics HUB
- Subjects
FOS: Computer and information sciences ,Artificial Intelligence (cs.AI) ,Computer Science - Artificial Intelligence ,[INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] - Abstract
Multi-objective AI planning suffers from a lack of benchmarks exhibiting known Pareto Fronts. In this work, we propose a tunable benchmark generator, together with a dedicated solver that provably computes the true Pareto front of the resulting instances. First, we prove a proposition allowing us to characterize the optimal plans for a constrained version of the problem, and then show how to reduce the general problem to the constrained one. Second, we provide a constructive way to find all the Pareto-optimal plans and discuss the complexity of the algorithm. We provide an implementation that allows the solver to handle realistic instances in a reasonable time. Finally, as a practical demonstration, we used this solver to find all Pareto-optimal plans between the two largest airports in the world, considering the routes between the 50 largest airports, spherical distances between airports and a made-up risk.
- Published
- 2023