Approximating the minimal-cost sensor-selection for discrete-event systems

This paper discusses the approximation of solutions to several NP-complete optimization problems related to the supervisory control of discrete-event systems. Approximation calculations for the minimal-cost sensor-selection problem in a partial observation, centralized control setting is first discussed. It is shown that approximate solutions to this problem cannot always be calculated with a given degree of accuracy in polynomial time. An efficient construction method is shown to convert this sensor selection problem into a novel type of graph cutting problem. Several heuristic algorithms are then shown to approximate solutions to this problem. Approximation methods for computationally difficult communicating decentralized controller problems and actuator selection problems are also discussed. It is shown how to convert these problems into graph cutting problems.