A Polynomial-time Algorithm for Constructing k-Maintainable Policies

All Papers

In this paper we present a polynomial time algorithm for constructing k-maintainable policies (Nakamura, Baral, and Bjareland 2000). Our algorithm, in polynomial time, constructs a k-maintainable control policy, if one exists, or tells that no such policy is possible. Our algorithm is based on SAT Solving, and employs a suitable formulation of the existence of k-maintainable control in a fragment of SAT which is tractable. We then give a logic programming implementation of our algorithm and use it to give a standard procedural algorithm. We then present several complexity results about constructing k- maintainable controls, under different assumptions such as k = 1, and compact representation.