T
he notion of maintenance often appears in t
he AI literature in t
he context of agent be
havior and planning. In t
his paper, we argue t
hat earlier c
haracterizations of t
he notion of maintenance are not intuitive to c
haracterize t
he maintenance be
havior of certain agents in a dynamic environment. We propose a different c
haracterization of maintenance and distinguis
h it from earlier notions suc
h as
stabilizability. Our notion of maintenance is more sensitive to a good-natured agent w
hic
h struggles wit
h an “adversary” environment, w
hic
h hinders
her by unforeseeable events to reac
h her goals (not in principle, but in case). It
has a parameter
k, referring to t
he lengt
h of non-interference (from exogenous events) needed to maintain a goal; we refer to t
his notion as
k-maintainability. We demonstrate t
he notion on examples, and address t
he important but non-trivial issue of efficient construction of maintainability control functions. We present an algorit
hm w
hic
h in polynomial time constructs a
k-maintainable control function, if one exists, or tells t
hat no suc
h control is possible. Our algorit
hm is based on SAT Solving, and employs a suitable formulation of t
he existence of
k-maintainable control in a fragment of SAT w
hic
h is tractable. For small
k (bounded by a constant), our algorit
hm is linear time. We t
hen give a logic programming implementation of our algorit
hm and use it to give a standard procedural algorit
hm, and analyze t
he complexity of constructing
k-maintainable controls, under different assumptions suc
h as
href=""/science?_ob=MathURL&_method=retrieve&_udi=B6TYF-4S6G91R-1&_mathId=mml1&_user=1067359&_cdi=5617&_rdoc=2&_acct=C000050221&_version=1&_userid=10&md5=04868026b328a40e77c6896d36ae818a"" title=""Click to view the MathML source"" alt=""Click to view the MathML source"">k=1, and states described by variables. On t
he one
hand, our work provides new concepts and algorit
hms for maintenance in dynamic environment, and on t
he ot
her
hand, a very fruitful application of computational logic tools. We compare our work wit
h earlier works on control synt
hesis from temporal logic specification and relate our work to
Dijkstra's notion of self-stabilization and related notions in distributed computing.