  We present the design of a motion planning algorithm that ensures safety for
an autonomous vehicle. In particular, we consider a multimodal distribution
over uncertainties; for example, the uncertain predictions of future
trajectories of surrounding vehicles reflect discrete decisions, such as
turning or going straight at intersections. We develop a computationally
efficient, scenario-based approach that solves the motion planning problem with
high confidence given a quantifiable number of samples from the multimodal
distribution. Our approach is based on two preprocessing steps, which 1)
separate the samples into distinct clusters and 2) compute a bounding polytope
for each cluster. Then, we rewrite the motion planning problem approximately as
a mixed-integer problem using the polytopes. We demonstrate via simulation on
the nuScenes dataset that our approach ensures safety with high probability in
the presence of multimodal uncertainties, and is computationally more efficient
and less conservative than a conventional scenario approach.
