Monitoring is an important activity for any embedded agent. To operate effectively, agents must gather information about their environment. The policy by which they do this is called a monitoring strategy. Our work has focused on classifying different types of monitoring strategies and understanding how strategies depend on features of the task and environment. We have discovered only a few general monitoring strategies, in particular periodic and interval reduction, and speculate that there are no more. The relative advantages and generality of each strategy will be discussed in detail. The wide applicability of interval reduction will be demonstrated both empirically and analytically. We conclude with a number of general laws that state when a strategy is most appropriate.
Agre, P.E., & Chapman, D. (1987). Pengi: An implementation of a theory of activity . Proceedings of the Sixth National Conference on Artificial Intelligence, 268-272.
2.
Agre, P.E., & Chapman, D. (1990). What are plans for? In P. Maes (Ed.), Designing autonomous agents: Theory and practice from biology to engineering and back. Cambridge, MA: MIT Press.
3.
Ambros-Ingerson, J.A., and Steel, S. (1988). Integrating planning, execution, and monitoring , Proceedings of the Seventh National Conference on Artificial Intelligence, 83-88.
4.
Atkin, M., & Cohen, P.R. (1993). Genetic programming to learn an agent's monitoring strategy, Proceedings of the AAAI 93 Workshop on Learning Action Models.
5.
Atkin, M.S. (1991). Research summary: Using a genetic algorithm to monitor cupcakes, EKSL Memo no. 24. Amherst, University of Massachusetts, Experimental Knowledge Systems Laboratory.
6.
Atkin, M.S. (1993). Using genetic algorithms to learn monitoring strategies . Unpublished.
7.
Atkin, M.S., & Cohen, P.R. (1994). Learning monitoring strategies: A difficult genetic programming application. In Proceedings of the First IEEE Conference on Evolutionary Computation.
8.
Bajscy, R. (1988). Active perception. Proceedings of the IEEE, 76 (8), 996-1005.
9.
Carbonell, J.R. (1966). A queueing model for many-instrument visual sampling . IEEE Transactions on Human Factors in Electronics, HFE-7, 157-164.
10.
Carbonell, J.R., Ward, J.L., & Senders, J.W. (1968). A queueing model of visual sampling; Experimental validation. IEEE Transactions on Man-Machine Systems, MMS-9 (3), 82-87.
11.
Ceci, S.J., & Bronfenbrenner, U. (1985). "Don't forget to take the cupcakes out of the oven": Prospective memory, strategic time-monitoring, and context. Child Development, 56, 152-164.
12.
Chrisman, L., & Simmons, R. (1991). Sensible planning: Focusing perceptual attention . Proceedings of the Ninth National Conference on Artificial Intelligence, 756-761.
13.
Cohen, P.R. (1990). Modeling how interactions between agents' architectures and environments produce behaviors, for the purpose of design and analysis . Proceedings of the AAAI Workshop on Planning .
14.
Cohen, P.R., Atkin, M.S., & Hansen, E.A. (1994). The interval reduction strategy for monitoring cupcake problems. Proceedings of the Third International Conference on the Simulation of Adaptive Behavior.
15.
Cohen, P.R., Howe, A.E., & Hart, D.M. (1990). Intelligent real-time problem solving: Issues and examples. (Tech. Rep. No. 90-20.) Amherst, MA: University of Massachusetts.
16.
Dean, T. (1987). Planning, execution, and control. Proceedings of the DARPA Knowledge-Based Planning Workshop.
17.
Doyle, R., Atkinson, D., & Doshi, R. (1986). Generating perception requests and expectations to verify the execution of plans. Proceedings of the Fifth National Conference on Artificial Intelligence, 81-88.
18.
Ferster, C.B., & Skinner, B.F. (1957). Schedules of reinforcement. New York: Appleton-Century-Crofts.
19.
Fikes, R., Hart, P., & Nilsson, N. (1972). Learning and executing generalized robot plans . Artificial Intelligence, 3(4), 251-288. Reprinted in J. F. Allen, J. Handler, & A. Tate (Eds.), Readings in planning. San Mateo, CA: Morgan Kaufmann.
20.
Firby, R.J. (1987). An investigation into reactive planning in complex domains. Proceedings of the Sixth National Conference on Artificial Intelligence, 202-206.
21.
Georgeff, M.P., & Lansky, A.L. (1987). Reactive reasoning and planning. Proceedings of the Sixth National Conference on Artificial Intelligence , 677-682.
22.
Goldberg, D.E. (1989). Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley
23.
Goldberg, D.E., & Kalyanmoy, D. (1991). A comparative analysis of selection schemes used in genetic algorithms. In G. J. E. Rawlins (Ed.), Foundations of genetic algorithms. San Mateo, CA: Morgan Kaufmann.
24.
Hansen, E.A. (1992a). Note on monitoring cupcakes (EKSL Memo no. 22) . Amherst, MA: University of Massachusetts , Experimental Knowledge Systems Laboratory.
25.
Hansen, E.A. (1992b). Learning a decision rulefor monitoring tasks with deadlines (CMP-SCI Tech. Rep. No. 92-80). Amherst, MA: University of Massachusetts.
26.
Hansen, E.A. (1994). Cost-effective sensing during plan execution. Proceedings of the Twelfth National Conference on Artificial Intelligence , 1029-1035.
27.
Hendler, J., &. Sanborn, J. (1987). A model of reaction for planning in dynamic environments. Proceedings of the DARPA Knowledge-Based Planning Workshop.
28.
Kaebling, L. (1987). An architecture for intelligent reactive systems. In M. P. Georgeff and A. L. Lansky (Eds.), Reasoning about actions and plans. Reprinted in J. E Allen, J. Handler, & A. Tate (Eds.), Readings in planning. San Mateo, CA: Morgan Kaufmann.
29.
Koza, J.R. (1992). Genetic programming: On the programming of computers by means of natural selection and genetics. Cambridge, MA: MIT Press.
30.
Koza, J.R., & Rice, J.P. (1992). Automatic programming of robots using genetic programming. Proceedings of the Tenth National Conference on Artificial Intelligence , 194-207.
31.
Koza, J.R., Rice, J.P., & Roughgarden, J. (1992). Evolution of food-foraging strategies for the carribean Anolis lizard using genetic programming. Adaptive Behavior, 1, 171-199.
32.
Kvalseth, T. (1977). The effect of cost on the sampling behavior of human instrument monitors. In T. B. Sheridan & G. Johannsen (Eds.), Monitoring behavior and supervisory control. New York: Plenum.
33.
Latombe, J.-C., Lazanas, A., & Shekhar, S. (1991). Robot motion planning with uncertainty in control and sensing. Artificial Intelligence, 52 (1), 1-47.
34.
Lowe, C.F., Beasty, A., & Bentall, R.P. (1983). The role of verbal behavior in human learning: Infant performance on fixed-interval schedules. Journal of the Experimental Analysis of Behavior, 39 (1), 157-164.
35.
Lowe, C.F., Harzem, P., & Bagshaw, M. (1978). Species differences in temporal control of behavior II: Human performance. Journal of the Experimental Analysis of Behavior, 29 (3), 351-361.
36.
Lowe, C.F., Harzem, P., & Spencer, P.T. (1979). Temporal control of behavior and the power law . Journal of the Experimental Analysis of Behavior, 31 (3), 333-343.
37.
Mackintosh, N.J. (1974). The psychology of animal learning. London: Academic Press.
38.
McDermott, D. (1978). Planning and acting. Cognitive Science, 2 (2), 71-109. Reprinted in J. F. Allen, J. Handler, & A. Tate (Eds.), Readings in planning. San Mateo, CA: Morgan Kaufinann.
39.
McDermott, D. (1992). Robot planning. AI Magazine, 13(2), 55-79.
40.
Moray, N. (1986). Monitoring behavior and supervisory control. In Boff, Kaufinan, and Thomas (Eds.), Handbook of perception and human performance , Vol. 2. New York: Wiley.
41.
Pyke, G.H. (1984). Optimal foraging: A critical review. Annual Review of Ecology and Systematics, 15, 523-575.
42.
Pyke, G.H., Pulliam, H.R., & Charnov, E.L. (1977). Optimal foraging: A selective review of theory and tests. Quarterly Review of Biology, 52, 137-154.
43.
Raphael, B. (1976). The thinking computer: Mind inside matter. San Francisco: W H. Freeman.
44.
Schneider, B.A. (1969). A two-state analysis of fixed-interval responding in the pigeon. Journal of the Experimental Analysis of Behavior , 12 (5), 677-687.
45.
Schoppers, M. (1987). Universal plans for reactive robots in unpredictable domains. Proceedings of the Tenth International Joint Conference on Artificial Intelligence, 1039-1046.
46.
Schwartz, B. (1984). Psychology and learning behavior (2nd ed.). New York: Norton.
47.
Senders, J.W. (1983). Visual scanning processes. Tilburg, The Netherlands: University of Tilburg Press .
48.
Senders, J.W., Elkind, J.I., Grignetti, M.C., & Smallwood, R. (1966). An investigation of the visual sampling behavior of human observers (NASA CR-434). Washington, D.C.: National Aeronautics and Space Administration.
49.
Sheridan, T.B. (1970). How often the supervisor should sample. IEEE Transactions on Systems, Science, and Cybernetics, SSC-6 (2), 140-145.
50.
Simmons, R.G. (1990). An architecture for coordinating planning, sensing, and action. Proceedings of the DARPA Workshop on Innovative Approaches to Planning, Scheduling, and Control, 292-297.
51.
Sutton, R.S. (1990). Integrated architectures for learning, planning, and reacting based on approximately dynamic programming. Proceedings of the Seventh International Conference on Machine Learning, 216-224.
52.
Wearden, J.H. (1985). The power law and Weber's law in fixed-interval postreinforcement pausing: A scalar timing model. The Quarterly Journal of Experimental Psychology, 37B (3), 191-211.
