arXiv:2608.04398cs.ROcs.AI2026-08

提出近似规则支配机制,高效求解多目标机器人规划问题。

Approximate Multi-Objective Search Under Rulebooks

  • 引入epsilon规则支配概念,实现规则书下的近似最优解搜索
  • 算法RA*pex计算速度比现有方法快两个数量级以上
  • 适合需兼顾安全、效率等多重优先级的复杂规划场景

机器人规划常涉及多个目标及其复杂的优先关系,如安全性、效率和合规性。规则书形式化了这些关系,允许目标之间的部分排序,推广了帕累托和词典序占优。然而,计算完整的规则书最优解集计算成本高昂。为此,本文引入ε规则占优这一原则性近似占优概念,并提出RA*pex算法,该算法以最佳优先搜索方式高效生成紧凑的ε近似规则书最优解集。RA*pex结合维度约减技术加速现有多目标搜索算法,同时通过维护独立闭集并针对截断与残余规则集执行占优检查,保持规则层次结构。我们对RA*pex进行形式化分析,证明每个规则书最优解至少被返回解集中一个解ε规则占优(我们提出的近似占优泛化)。实验结果表明,本方法计算时间比现有方法快两个数量级以上。

原文摘要 · Abstract (English)

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.

机器人规划多目标优化规则书近似算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。