该研究首次理论分析了质量多样性算法在路径规划中的高效表现。
Theoretical Analysis of Quality Diversity Algorithms for a Classical Path Planning Problem
- 用地图精英法解决所有点对最短路径问题，实现并行计算
- 算法可高效为每对节点生成最短路径，计算效率显著提升
- 新父代选择策略使速度远超传统方法，适合优化场景
质量多样性（QD）算法在机器人、游戏和组合优化中展现出生成高质量解集的能力，但其理论基础仍落后于实际应用。本文针对经典规划问题，研究了地图精英法（Map-Elites）在所有点对最短路径（APSP）问题中的行为。基于图中所有节点对构建行为空间，结果表明该方法能高效并行计算出每对节点间的最短路径。此外，引入的交叉父代选择技术相比标准QD方法显著加速，为复杂优化问题提供理论支持与实践改进。
原文摘要 · Abstract (English)
Quality diversity (QD) algorithms have shown to provide sets of high quality solutions for challenging problems in robotics, games, and combinatorial optimisation. So far, theoretical foundational explaining their good behaviour in practice lack far behind their practical success. We contribute to the theoretical understanding of these algorithms and study the behaviour of QD algorithms for a classical planning problem seeking several solutions. We study the all-pairs-shortest-paths (APSP) problem which gives a natural formulation of the behavioural space based on all pairs of nodes of the given input graph that can be used by Map-Elites QD algorithms. Our results show that Map-Elites QD algorithms are able to compute a shortest path for each pair of nodes efficiently in parallel. Furthermore, we examine parent selection techniques for crossover that exhibit significant speed ups compared to the standard QD approach.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。