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 的推广。