提出高效算法求解多目标规划中的加权最大值问题。
Efficient Multi-Objective Planning with Weighted Maximization Using Large Neighbourhood Search
- 基于大邻域搜索框架设计新算法，提升求解效率。
- 相比现有方法，计算速度提升1到2个数量级。
- 适合需要全面探索最优权衡的自动驾驶场景。
自主导航常需同时优化多个目标。传统加权求和法虽常用，但无法发现所有可能的权衡方案，易遗漏关键解。加权最大值法可找到所有帕累托最优解，包括非凸区域的解，但其在离散域中计算复杂度高，限制了实际应用。为此，本文提出一种基于大邻域搜索框架的新算法，高效求解加权最大值规划问题。通过大量仿真验证，该算法在解质量相当的前提下，运行时间较现有加权最大值规划器缩短1至2个数量级，使其成为自动驾驶中的可行选择。
原文摘要 · Abstract (English)
Autonomous navigation often requires the simultaneous optimization of multiple objectives. The most common approach scalarizes these into a single cost function using a weighted sum, but this method is unable to find all possible trade-offs and can therefore miss critical solutions. An alternative, the weighted maximum of objectives, can find all Pareto-optimal solutions, including those in non-convex regions of the trade-off space that weighted sum methods cannot find. However, the increased computational complexity of finding weighted maximum solutions in the discrete domain has limited its practical use. To address this challenge, we propose a novel search algorithm based on the Large Neighbourhood Search framework that efficiently solves the weighted maximum planning problem. Through extensive simulations, we demonstrate that our algorithm achieves comparable solution quality to existing weighted maximum planners with a runtime improvement of 1-2 orders of magnitude, making it a viable option for autonomous navigation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。