Dynamic probabilistic risk assessment with K-shortest-paths planning for generating discrete dynamic event trees

Conventional risk assessment methods are often not well suited for fast-changing dynamic and complex systems since the results from the analysis may be averages or valid for a short time before the system’s state changes. A response to this problem is dynamic probabilistic risk assessment (DPRA), which considers the ever-changing nature of such systems and how their dynamic behavior affects the likelihood of future accident scenarios. Performing DPRA is difficult for complex systems — i.e., systems with many interconnected subsystems and components, for example, autonomous systems. There is a combinatorial “explosion” when considering how component failures affect one another and the overall system performance, known in the DPRA literature as the “state explosion problem”, causing DPRA methods to have poor computational performance for large-scale systems. Although solutions to state explosion alleviate the average-case performance, most DPRA methods remain computationally expensive, with exponential worst-case time complexities. In this paper, a method for solving DPRA problems with K-Shortest-Paths planning algorithms is proposed. The method, called KPRA, consists in framing a subset of DPRA problems as relaxed versions of the K-Shortest-Paths (KSP) planning problem, allowing these DPRA problems to be solved by a graph search algorithm called K*, which has a theoretical log-linear worst-case complexity. Therefore, in theory, KPRA with K* solves DPRA problems with computational performance better than exponential. KPRA was implemented and applied to a case study of DPRA for an autonomous ship for validation and comparison with conventional DPRA methods. The case study consists of two ships, one of them autonomous, in a crossing encounter with a possible collision risk. The task is to find the most critical situations for the autonomous ship, i.e., the scenarios where its collision risk is the highest. KPRA’s performance in solving the case study is compared with two conventional DPRA methods. The results show that the KPRA implementation in this work can solve the case study, i.e., produce an output equivalent to the other methods, with a polynomial worst-case computational complexity, i.e., more efficiently than the other methods with exponential complexities.