  Planning in environments with other agents whose future actions are uncertain
often requires compromise between safety and performance. Here our goal is to
design efficient planning algorithms with guaranteed bounds on the probability
of safety violation, which nonetheless achieve non-conservative performance. To
quantify a system's risk, we define a natural criterion called interval risk
bounds (IRBs), which provide a parametric upper bound on the probability of
safety violation over a given time interval or task. We present a novel
receding horizon algorithm, and prove that it can satisfy a desired IRB. Our
algorithm maintains a dynamic risk budget which constrains the allowable risk
at each iteration, and guarantees recursive feasibility by requiring a safe set
to be reachable by a contingency plan within the budget. We empirically
demonstrate that our algorithm is both safer and less conservative than strong
baselines in two simulated autonomous driving experiments in scenarios
involving collision avoidance with other vehicles, and additionally demonstrate
our algorithm running on an autonomous class 8 truck.
