  Standard Model Predictive Control (MPC) or trajectory optimization approaches
perform only a local search to solve a complex non-convex optimization problem.
As a result, they cannot capture the multi-modal characteristic of human
driving. A global optimizer can be a potential solution but is computationally
intractable in a real-time setting. In this paper, we present a real-time MPC
capable of searching over different driving modalities. Our basic idea is
simple: we run several goal-directed parallel trajectory optimizations and
score the resulting trajectories based on user-defined meta cost functions.
This allows us to perform a global search over several locally optimal motion
plans. Although conceptually straightforward, realizing this idea in real-time
with existing optimizers is highly challenging from technical and computational
standpoints. With this motivation, we present a novel batch non-holonomic
trajectory optimization whose underlying matrix algebra is easily
parallelizable across problem instances and reduces to computing large batch
matrix-vector products. This structure, in turn, is achieved by deriving a
linearization-free multi-convex reformulation of the non-holonomic kinematics
and collision avoidance constraints. We extensively validate our approach using
both synthetic and real data sets (NGSIM) of traffic scenarios. We highlight
how our algorithm automatically takes lane-change and overtaking decisions
based on the defined meta cost function. Our batch optimizer achieves
trajectories with lower meta cost, up to 6x faster than competing baselines.
