Planning in Dynamic and Partially Unknown Environments

Abstract Motion planning in dynamic and partially unknown environments is a difficult problem requiring both perception and control components. We propose a solution to the control component while cleanly abstracting perception. We show that this clean abstraction can be used to synthesize verifiably safe reference trajectories using a combination of reachability analysis and Mixed Integer Linear Programming. Experiments with a prototype implementation of this algorithm show promise as it has subsecond synthesis performance for nonlinear vehicle models in scenarios with hundred plus obstacles on standard hardware.