  We present a fast algorithm for the design of smooth paths (or trajectories)
that are constrained to lie in a collection of axis-aligned boxes. We consider
the case where the number of these safe boxes is large, and basic preprocessing
of them (such as finding their intersections) can be done offline. At runtime
we quickly generate a smooth path between given initial and terminal positions.
Our algorithm designs trajectories that are guaranteed to be safe at all times,
and detects infeasibility whenever such a trajectory does not exist. Our
algorithm is based on two subproblems that we can solve very efficiently:
finding a shortest path in a weighted graph, and solving (multiple) convex
optimal-control problems. We demonstrate the proposed path planner on
large-scale numerical examples, and we provide an efficient open-source
software implementation, fastpathplanning.
