Sampling-based Polytope Calculus for Reachability Analysis of Dynamical Systems

Polytope calculus is a powerful and useful tool for generating and computing polytopes that find use in many applications, from dynamical systems to higher algebra and graph theory. Despite its usefulness, this branch of study deals with many computational problems associated with convex polytopes in general dimensions. In particular, many issues arise when looking at the time complexity of existing algorithms: for example, set operations like the Minkowski sum or affine mapping are exponential in time, while volume computation has been proven to be an NP-hard problem. This study proposes a new approach to the subject, aiming at a lower time complexity and an increase in scalability: the goal is to produce a new sample-based algorithm that can output an approximated result for set operations in polynomial time. The algorithm presented in this work is accompanied by a proof of tightness and an implementation in both Matlab and Julia programming languages. The code has been tested for both its computational speed and tightness of approximation, together with a comparison with other existing tools for exact computation. Additionally, the algorithm is then applied in a case study of reachability analysis for dynamical systems, showing how it can represent an improvement in a branch that is now limited to low-dimensional spaces due to the exponential complexity of exact methods for polytope computation.