A polynomial-time algorithm for constructing k -maintainable policies
Chitta R. Baral, Thomas Eiter · 2004
In this paper we present a polynomial time algorithm for constructing k-maintainable policies (Nakamura, Baral, & 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 formula-tion of the existence of k-maintainable control in a frag-ment 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.