Search papers, labs, and topics across Lattice.
This paper addresses the challenge of efficiently computing optimal solutions in robotic planning with multiple objectives defined by complex priority relationships, formalized through rulebooks. The authors introduce epsilon-rule-dominance and the RA*pex algorithm, which utilizes dimensionality reduction to significantly speed up the search process while adhering to rule hierarchies. Empirical evaluations show that RA*pex can compute a compact set of epsilon-approximate rulebook-optimal solutions over two orders of magnitude faster than existing methods.
Epsilon-rule-dominance allows for a dramatic reduction in computation time for multi-objective robotic planning, achieving speedups of over 100 times compared to traditional methods.
Robotic planning often involves multiple objectives with complex priority relationships, such as safety, efficiency, and regulatory compliance. Rulebooks formalize these relationships, allowing partial ordering of objectives that generalizes both Pareto and lexicographic dominance. Computing the full set of rulebook-optimal solutions, however, is computationally expensive. To address this challenge, we introduce the concept of epsilon-rule-dominance, a principled notion of approximate dominance under rulebooks, and propose RA*pex, a best-first search algorithm that efficiently computes a compact set of epsilon-approximate rulebook-optimal solutions. RA*pex leverages dimensionality reduction, a technique used to speed up existing multi-objective search algorithms, while respecting rule hierarchies by maintaining separate closed sets and performing dominance checks over truncated and residual rule sets. We provide a formal analysis of RA*pex, proving that every rulebook-optimal solution is epsilon-rule-dominated (a generalization of approximate dominance we introduce) by at least one solution in the returned set. Empirical results demonstrate that our approach achieves computation times over two orders of magnitude faster than existing methods.
