  In recent years, Signal Temporal Logic (STL) has gained traction as a
practical and expressive means of encoding control objectives for robotic and
cyber-physical systems. The state-of-the-art in STL trajectory synthesis is to
formulate the problem as a Mixed Integer Linear Program (MILP). The MILP
approach is sound and complete for bounded specifications, but such strong
correctness guarantees come at the price of exponential complexity in the
number of predicates and the time bound of the specification. In this work, we
propose an alternative synthesis paradigm that relies on Bayesian optimization
rather than mixed integer programming. This relaxes the completeness guarantee
to probabilistic completeness, but is significantly more efficient: our
approach scales polynomially in the STL time-bound and linearly in the number
of predicates. We prove that our approach is sound and probabilistically
complete, and demonstrate its scalability with a nontrivial example.
