Efficient Computation Employing Partial Order Theory

Computing safety controllers with imperfect information is usually computationally prohibitive for general systems. In order to overcome this bottleneck, we have restricted the class of systems to those whose state spaces and inputs can be extended to partial orders (lattices) and whose trajectories preserve the partial ordering on the state space. Specifically, we have shown using lattice theory that in such a case, the complexity of the hybrid state estimator can be linear with the number of variables and that convergence is guaranteed under suitable observability assumptions. Furthermore, the proposed dynamic feedback algorithm can also have linear complexity with the number of continuous variables. This is because the computations of the capture sets reduce to the computation of suitable upper and lower bounds. A number of systems of practical relevance generate trajectories that preserve a partial ordering. Examples include multi-agent systems in which agents evolve on paths, such as vehicles in lanes, trains on rails, and aircrafts on their pre-designed routes, as well as several bio-molecular and chemical networks. We are currently extending these techniques to apply to general systems for which an order preserving abstraction can be computed.