Theorem 2  An agent following policy, P, with value function, V, generated as described in Section 4.4, from any state s E S will satisfy each and every requiring constraint with probability one if and only if V(s) = {F, C, a UC,,, U) (for some U and F). Proof Sketch: The proof parallels that of Theorem 1, but with a state partition, Sk, where k corresponds to the maximum number of transitions before satisfying a requiring constraint. However, here, states in Soo are those that violate the constraint, rather than stisfy it. Some cycles in the state space can prevent a guarantee of satisfying a requiring constraint within any fixed number of transitions, although the probability of satisfaction in the limit may be 1. In our current constraint semantics, we have decided that such a situation fails to satisfy the constraint, and our algorithm behaves accordingly. Such cycles have no effect on the handling of forbidding constraints, where, as we saw for Theorem 1, we need consider only the minimum-length trajectory. □
The proofs of the two theorems operate independently, so the policy-specified action will stisfy all constraints, if such an action exists. The precedence of forbidding constraints over requiring ones has no effect on the optimal action in such states. However, if there are conflicting forbidding and requiring constraints in a state, then the preference ordering causes the agent to choose a policy that satisfies the forbidding constraint and violates a requiring constraint. The agent can make the opposite choice if we simply ange the preference ordering from Section 4.4. Regardless of the choice, from Theorems 1 and 2, the agent can use the value function, V, to identify the existence of any such violation and notify the user of the violation and possible constraint conflict.

## References

Barber, K., Goel, A., & Martin, C. (2000a). Dynamic adaptive autonomy in multi-agent systems. Journal of Experimental and Theoretical Artificial Intelligence, 12 (2), 129–
148.

Barber, K. S., Martin, C., & Mckay, R. (2000b). A communication protocol supporting dynamic autonomy agreements. In Proceedings of PRICAI 2000 Workshop on Teams with Adjustable Autonomy, pp. 1-10, Melbourne, Australia.

Bonasso, R., Firby, R., Gat, E., Kortenkamp, D., Miller, D., & Slack, M. (1997). Experiences with an architecture for intelligent reactive agents. Journal of Experimental and Theorectical Artificial Intelligence, 9 (1), 237–256.

Brann, D., Thurman, D., & Mitchell, C. (1996). Human interaction with lights-out automation: A field study. In Proceedings of the 1996 Symposium on Human Interaction and Complex Systems, pp. 276-283, Dayton, USA.

Cesta, A., Collia, M., & D'Aloisi, D. (1998). Tailorable interactive agents for scheduling meetings. In Lecture Notes in AI, Proceedings of AIMSA'98, No. 1480, pp. 153–166.

Springer Verlag.

Chalupsky, H., Gil, Y., Knoblock, C., Lerman, K., Oh, J., Pynadath, D., Russ, T., & Tambe, M. (2001). Electric Elves: Applying agent technology to support human organizations.

In International Conference on Innovative Applications of AI, pp. 51–58.