Sampling-based planning, control and verification of hybrid systems

Abstract

A sampling-based approach to planning, control and verification inspired by robotics motion planning algorithms such as rapidly exploring random trees (RRTs) and probabilistic roadmaps (PRMs) is surveyed. With the focus on RRTs, how to adapt them to solve standard non-linear control problems is demonstrated. RRTs are extended to purely discrete spaces (replacing distance metrics with cost-to-go heuristic estimates and substituting local planners for straight-line connectivity) and computational experiments comparing them to conventional methods, such as A* are provided. Finally, RRTs are extended to the case of hybrid systems and our modifications to LaValle's motion strategy library to allow for hybrid planning and verification are described. The work on the coverage and optimality properties of sampling-based techniques is also reviewed.