Autonomous vehicles face the problem of optimizing the expected performance
of subsequent maneuvers while bounding the risk of collision with surrounding
dynamic obstacles. These obstacles, such as agent vehicles, often exhibit
stochastic transitions that should be accounted for in a timely and safe
manner. The Constrained Stochastic Shortest Path problem (C-SSP) is a formalism
for planning in stochastic environments under certain types of operating
constraints. While C-SSP allows specifying constraints in the planning problem,
it does not allow for bounding the probability of constraint violation, which
is desired in safety-critical applications. This work's first contribution is
an exact integer linear programming formulation for Chance-constrained SSP
(CC-SSP) that attains deterministic policies. Second, a randomized rounding
procedure is presented for stochastic policies. Third, we show that the CC-SSP
formalism can be generalized to account for constraints that span through
multiple time steps. Evaluation results show the usefulness of our approach in
benchmark problems compared to existing approaches.

本文介绍了一个基于约束的随机规划问题，其中利用整数线性规划方法确保了确定性决策，同时为安全性关键的应用提供了约束违规概率的上界。同时还介绍了确定性策略和随机策略的随机舍入过程，并探讨了如何在考虑不同时间步的约束情况下进行 CC-SSP 的推广。

用于自主车辆行为规划的概率约束随机最短路径双重描述

Dual Formulation for Chance Constrained Stochastic Shortest Path with Application to Autonomous Vehicle Behavior Planning

The fixed-horizon constrained stochastic shortest path problem (C-SSP) is a
formalism for planning in stochastic environments under certain operating
constraints. Chance-Constrained SSP (CC-SSP) is a variant that allows bounding
the probability of constraint violation, which is desired in many
safety-critical applications. This work considers an important variant of
(C)C-SSP under local transition, capturing a broad class of SSP problems where
state reachability exhibit a certain locality. Only a constant number of states
can share some subsequent states. (C)C-SSP under local transition is NP-Hard
even for a planning horizon of two. In this work, we propose a fully
polynomial-time approximation scheme for (C)C-SSP that computes (near) optimal
deterministic policies. Such an algorithm is the best approximation algorithm
attainable in theory

本文提出了一个在局部转换下的全多项式近似方案，可用于计算最优确定性策略，以解决 (C) C-SSP 问题，其中固定阈值限制随机最短路径问题是在一定操作限制下的规划形式，当限制违反时，这种 CC-SSP 变体允许边界概率，而 SSP 问题的状态可达性呈现出一定的局部性，并且在此情况下，只有一定数量的状态可以共享一些后续状态。