Dynamic Distributed Control over Semirings and Applications

We demonstrate that many constrained dynamic control problems involving hybrid systems are control problems for dynamical systems over partially ordered semirings. Applications include biological-social-communication networks, collaborative robotics, consensus, flocking, trust, swarms. We next show that when time is discrete and inputs, outputs and states take values in finite sets, these problems are equivalent to constrained shortest path problems. We then develop algorithms, mostly distributed ones, for solving these dynamic constrained shortest path problems over semirings.