  We tackle the challenging problem of multi-agent cooperative motion planning
for complex tasks described using signal temporal logic (STL), where robots can
have nonlinear and nonholonomic dynamics. Existing methods in multi-agent
motion planning, especially those based on discrete abstractions and model
predictive control (MPC), suffer from limited scalability with respect to the
complexity of the task, the size of the workspace, and the planning horizon. We
present a method based on {\em timed waypoints\/} to address this issue. We
show that timed waypoints can help abstract nonlinear behaviors of the system
as safety envelopes around the reference path defined by those waypoints. Then
the search for waypoints satisfying the STL specifications can be inductively
encoded as a mixed-integer linear program. The agents following the synthesized
timed waypoints have their tasks automatically allocated, and are guaranteed to
satisfy the STL specifications while avoiding collisions. We evaluate the
algorithm on a wide variety of benchmarks. Results show that it supports
multi-agent planning from complex specification over long planning horizons,
and significantly outperforms state-of-the-art abstraction-based and MPC-based
motion planning methods. The implementation is available at
https://github.com/sundw2014/STLPlanning.
