Collision Probabilities for Continuous-Time Systems Without Sampling

Kris Frey, Ted Steiner, Jonathan P. How


Demand for high-performance, robust, and safe autonomous systems has grown substantially in recent years. These objectives motivate the desire for efficient risk estimation that can be embedded in core decision-making tasks such as motion planning. On one hand, Monte-Carlo (MC) and other sampling-based techniques provide accurate solutions for a wide variety of motion models but are cumbersome in the context of continuous optimization. On the other hand, “direct” approximations aim to compute (or upper-bound) the failure probability as a smooth function of the decision variables, and thus are convenient for optimization. However, existing direct approaches fundamentally assume discrete-time dynamics and can perform unpredictably when applied to continuous-time systems ubiquitous in the real world, often manifesting as severe conservatism. State-of-the-art attempts to address this within a conventional discrete-time framework require additional Gaussianity approximations that ultimately produce inconsistency of their own. In this paper we take a fundamentally different approach, deriving a risk approximation framework directly in continuous time and producing a lightweight estimate that actually converges as the underlying discretization is refined. Our approximation is shown to significantly outperform state-of-the-art techniques in replicating the MC estimate while maintaining the functional and computational benefits of a direct method. This enables robust, risk-aware, continuous motion-planning for a broad class of nonlinear, partially-observable systems.

Live Paper Discussion Information

Start Time End Time
07/14 15:00 UTC 07/14 17:00 UTC

Virtual Conference Presentation

Paper Reviews

Review 2

This paper presents a method to compute less conservative approximate of chance-constrained control for continuous-time problems. In particular, it uses the Lagrangian formulation that convert risk-constrained into risk-minimization, and propose an approximation of this formulation based on the concept of first passage time, rather than time discretisation. Convergence guaranteed is provided very thoroughly and simulation results for controlling 2nd order Dubins car in environment populated by obstacles is provided. I think the problem of chance-constrained control in continuous-time is interesting and the paper's attempt to solve the problem without discretising the time domain is interesting and could be very useful. Further, the derivation on how to evolve distribution for the relax Lagrange formulation of chance-constrained control via the concept of first passage time could be useful and thorough. Several feedback 1. I think avoiding fixed time discretisation is interesting and useful. However, the proposed approximation (sec. IV) seems to go back on using fixed time discretisation. I think some elaboration on how this affects the exact difficulty that the paper is trying to avoid would be needed. 2. It would be interesting if the provided example include a scenario where the proposed method is superior than Monte Carlo approach. I do understand that the contribution of the paper is more on the theoretical side, and this does not effect my score. However, considering Monte Carlo is used quite a lot to estimate distribution, I think it would have much more impact if such an example is provided. 3. I think eq. (19), right hand side, P(... | z_t = z) should be P(... | z_s \in dz) and P(z \in dz) should be P(z_s \in dz).

Review 3

Originality: Good Quality: Good Clarity: Good Significance: Good Summary: The authors address the problem of estimating and minimizing failure probabilities in the context of continuous motion planning by proposing a light-weight approximation method. The proposed method avoids estimating the anthropic belief and produces a conservative risk estimate with minimal computation. Further the method efficiently discretizes the time and reduces the planner brittleness. The paper is written well and the authors provide good theoretical analysis to support their claims. Comments: 1. In this work, only the accuracy of the proposed method is provided. No result, which describes the computation overhead of the method is given. The trade-off between speed vs accuracy is an interesting aspect, and it is difficult to measure the overall efficiency without the computational overhead. 2. It may be better for the readers if the authors specify all the contributions in a separate paragraph in the Introduction section. 3. No Future work is given. 4. It is not clear what are the limitation of the Eq.(6) in comparison of Eq. (4). 5. It may be better for the readers if the authors briefly describe the intuitive ideas at the beginning of each section.