Collaborative Multi-Robot Systems with Provable Availability, Safety, and Optimality Guarantees