Motion planning serves as a pivotal role in various robotics applications, endowing robots with intelligence and autonomy. It translates human commands and tasks into a reference trajectory, with a tracking controller steering the system along the reference trajectory, eventually implementing the commands and tasks. Despite extensive study in motion planning for continuous-time and discrete-time systems, the emergence of hybrid dynamical systems underscores their limitations. Hybrid dynamical systems feature state variables that may evolve continuously (flow) and, at times, evolve discretely (jump). Compared with motion planning for pure continuous-time/discrete-time system, only a few efforts have been devoted to motion planning for a special class of hybrid dynamical systems. Motivated by these gaps, this dissertation focuses on developing provably-correct and efficient motion planning algorithms for a broad class of hybrid dynamical systems.
Firstly, this dissertation lays the groundwork by establishing the fundamental theory of motion planning for hybrid dynamical systems. The motion planning problem for hybrid dynamical systems is formulated using the hybrid equations framework, which is general to capture most hybrid dynamical systems. To overcome the lack of the systematic analysis on the propagation, reversal, concatenation, and truncation operations, which are used in almost all motion planning algorithms, on the solutions to hybrid dynamical systems, this dissertation formalizes the definitions of those operations for the hybrid dynamical systems. This dissertation proposes a bidirectional propagation algorithm template that describes a general framework using the aforementioned operations to solve the motion planning problem for hybrid dynamical systems.
Secondly, a rapidly-exploring random trees (RRT) implementation of the proposed algorithm template is designed to solve the motion planning problem for hybrid dynamical systems. At each iteration, the proposed algorithm, called HyRRT, randomly picks a state sample and extends the search tree by flow or jump, which is also chosen randomly when both regimes are possible. Through a definition of concatenation of functions defined on hybrid time domains, we show that HyRRT is probabilistically complete, namely, the probability of failing to find a motion plan approaches zero as the number of iterations of the algorithm increases. This property is guaranteed under mild conditions on the data defining the motion plan, which include a relaxation of the usual positive clearance assumption imposed in the literature of classical systems. The motion plan is computed through the solution of two optimization problems, one associated with the flow and the other with the jumps of the system.
Thirdly, this dissertation proposes a bidirectional RRT algorithm to solve the motion planning problem for hybrid dynamical systems, accelerating the search process. The proposed algorithm, called HyRRT-Connect, propagates in both forward and backward directions in hybrid time until an overlap between the forward and backward propagation results is detected. Then, HyRRT-Connect constructs a motion plan through the reversal and concatenation of functions defined on hybrid time domains, ensuring the motion plan thoroughly satisfies the given hybrid dynamics. To address the potential discontinuity along the flow caused by tolerating some distance between the forward and backward partial motion plans, we reconstruct the backward partial motion plan by a forward-in-hybrid-time simulation from the final state of the forward partial motion plan. By applying the reversed input of the backward partial motion plan, the reconstruction process effectively eliminates the discontinuity and ensures that as the tolerance distance decreases to zero, the distance between the endpoint of the reconstructed motion plan and the final state set approaches zero.
At last, we formulate an optimal motion planning problem for hybrid dynamical systems and design a stable sparse RRT (SST) algorithm to solve the optimal motion planning problem for hybrid dynamical 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. 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 contributions of this dissertation go beyond the development of certain motion planning algorithms. It introduces a novel motion planning problem for a general dynamical system and furnishes theoretical tools, enabling researchers to design their own algorithms for solving this problem while ensuring completeness guarantees. In addition, a hybrid dynamical system serves as a powerful modeling tool for addressing difficult motion planning problems. By employing a generic hybrid dynamical system model, users can tackle challenging motion planning tasks efficiently, with minimal modeling effort and theoretical guarantees.