新算法CARL通过标量化求解约束随机最短路径问题，效率提升50%。
Solving Constrained Stochastic Shortest Path Problems with Scalarisation
- 将多目标成本转化为单标量成本，用启发式搜索求解无约束子问题。
- 在基准测试中解决的问题比现有方法多50%。
- 适合需要高效求解带约束的随机路径规划的研究者。
约束随机最短路径问题（CSSP）用于建模具有概率效应的场景，目标是最小化主要成本，同时满足次要成本的约束，例如在预算内最小化时间。现有启发式搜索算法通过逐步求解一系列不断增大的线性规划问题来逼近原问题最优解。本文提出新算法CARL，通过求解一系列无约束的随机最短路径问题（SSP）来解决该问题。这些子问题通过标量化技术将主成本与次成本向量投影为单一成本函数构建。CARL采用类似次梯度法的优化算法寻找最优标量组合，结合其对应的SSP解，生成一组策略并合成原CSSP的最优策略。实验表明，该算法在现有基准上比当前最优方法多解决了50%的问题。
原文摘要 · Abstract (English)
Constrained Stochastic Shortest Path Problems (CSSPs) model problems with probabilistic effects, where a primary cost is minimised subject to constraints over secondary costs, e.g., minimise time subject to monetary budget. Current heuristic search algorithms for CSSPs solve a sequence of increasingly larger CSSPs as linear programs until an optimal solution for the original CSSP is found. In this paper, we introduce a novel algorithm CARL, which solves a series of unconstrained Stochastic Shortest Path Problems (SSPs) with efficient heuristic search algorithms. These SSP subproblems are constructed with scalarisations that project the CSSP's vector of primary and secondary costs onto a scalar cost. CARL finds a maximising scalarisation using an optimisation algorithm similar to the subgradient method which, together with the solution to its associated SSP, yields a set of policies that are combined into an optimal policy for the CSSP. Our experiments show that CARL solves 50% more problems than the state-of-the-art on existing benchmarks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。