HySST: An Asymptotically Near-Optimal Motion Planning Algorithm for Hybrid Systems

This paper proposes a stable sparse rapidly-exploring random trees (SST) algorithm to solve the optimal motion planning problem for hybrid systems. At each iteration, the proposed algorithm, called HySST, selects a vertex with minimal cost among all the vertices within the neighborhood of a random sample, subsequently extending the search tree through flow or jump, which is also chosen randomly when both regimes are possible. In addition, HySST maintains a static set of witness points where all vertices within each witness's neighborhood are pruned, except for the ones with lowest cost. We show that HySST is asymptotically near-optimal, namely, the probability of failing to find a motion plan with cost close to the optimal approaches zero as the number of iterations of the algorithm increases to infinity. The proposed algorithm is applied to a collision-resilient tensegrity multicopter system so as to highlight its generality and computational features.