TY - GEN
T1 - A Polynomial-time Algorithm for Constructing k-Maintainable Policies
AU - Baral, Chitta
AU - Eiter, Thomas
N1 - Funding Information:
∗This work was partially supported by FWF (Austrian Science Funds) projects P-16536-N04 and Z29-N04, NSF (National Science Foundation of USA) grant number 0070463 and NASA grant number NCC2-1232. The major part of this work was done when Chitta was visiting Vienna University of Technology during May 2003. Copyright ©c 2004, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.
Publisher Copyright:
Copyright © 2004, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.
PY - 2004
Y1 - 2004
N2 - 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 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.
AB - 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 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.
UR - https://www.scopus.com/pages/publications/29344462786
UR - https://www.scopus.com/pages/publications/29344462786#tab=citedBy
M3 - Conference contribution
AN - SCOPUS:29344462786
T3 - Principles of Knowledge Representation and Reasoning: Proceedings of the 9th International Conference, KR 2004
SP - 720
EP - 729
BT - Principles of Knowledge Representation and Reasoning
PB - AAAI press
T2 - 9th International Conference on Principles of Knowledge Representation and Reasoning, KR 2004
Y2 - 2 June 2004 through 5 June 2004
ER -