$-Calculus of Bounded Rational Agents : Flexible Optimization as Search under Bounded Resources in Interactive Systems

• Autorzy: Eberbach E.
• Języki publikacji: EN

Abstrakty

EN

This paper presents a novel model for resource bounded computation based on process algebras. Such model is called the $-calculus (cost calculus). Resource bounded computation attempts to find the best answer possible given operational constraints. The $-calculus provides a uniform representation for optimization in the presence of limited resources. It uses cost-optimization to find the best quality solutions while using a minimal amount of resources. A unique aspect of the approach is to propose a resource bounded process algebra as a generic problem solving paradigm targeting interactive AI applications. The goal of the $-calculus is to propose a computational model with built-in performance measure as its central element. This measure allows not only the expression of solutions, but also provides the means to incrementally construct solutions for computationally hard, real-life problems. This is a dramatic contrast with other models like Turing machines, l-calculus, or conventional process algebras. This highly expressive model must therefore be able to express approximate solutions. This paper describes the syntax and operational cost semantics of the calculus. A standard cost function has been defined for strongly and weakly congruent cost expressions. Example optimization problems are given which take into account the incomplete knowledge and the amount of resources used by an agent. The contributions of the paper are twofold: firstly, some necessary conditions for achieving global optimization by performing local optimization in time and/or space are found. That deals with incomplete information and complexity during problem solving. Secondly, developing an algebra which expresses current practices, e.g., neural nets, cellular automata, dynamic programming, evolutionary computation, or mobile robotics as limiting cases, provides a tool for exploring the theoretical underpinnings of these methods. As the result, hybrid methods can be naturally expressed and developed using the algebra.

Słowa kluczowe

EN

resource bounded computation; process algebras; problem solving; search; completeness; optimization; total optimization

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 68, nr 1/2
• Strony: 47--102
• Opis fizyczny: Bibliogr. 89 poz.

Twórcy

autor

Eberbach E.

• Computer and Information Science Department University of Massachusetts Dartmouth North Dartmouth, MA 02747, USA,

Bibliografia

• [1] Bäck T., Fogel D.B., Michalewicz Z. (eds.), Handbook of Evolutionary Computation, Oxford University Press, 1997.
• [2] Barhen J., Protopepscu V., Reister D.(1997) TRUST: A Deterministic Algorithm for Global Optimization, Science. vol. 276, pp. 1094-1097.May 16, 1997.
• [3] Bellman R.E., Dynamic Programming, Princeton University Press, 1957.
• [4] Blake C. L., Mertz C. J., UCI Repository of machine learning databeses, http://www.ics.uci.edu/˜mlearn/MLRepository.html, 1998.
• [5] Bergstra J. A., Ponse A., Smolka S. A. (eds.), Handbook of Process Algebra, Noth Holland, Elsevier, 2001.
• [6] Brooks R. A., Elephants Don’t Play Chess, in P. Maes (ed.), Designing Autonomous Agents: Theory and Practice from Biology to Engineering and Back, The MIT Press, 1994, 3-15.
• [7] Brooks R. R., Reliable Sensor Fusion Algorithms: Calibration and Cost Minimization. Ph. D. Dissertation. Department of Computer Science, Louisiana State University, Baton Rouge, Louisiana, 1996.
• [8] Brooks R. R., Iyengar S. S., and Chen J., Automatic Correlation and Calibration of Noisy Sensor Readings using Elite Genetic Algorithms, Artificial Intelligence. vol. 18, No. 1-2, pp. 339-354. July, 1996.
• [9] Brooks R. R., Iyengar S. S., Multi-Sensor Fusion: Fundamentals and Applications with Software, Prentice Hall PTR, Upper Saddle River, NJ, 1998.
• [10] Burks A., Essays on Cellular Automata, Univ. of Illinois Press, 1970.
• [11] Chellapilla K., Fogel D. B., Anaconda Defeats Hoyle 6-0: A Case Study Competing an Evolved Checkers Program against Commercially Available Software, Proc. 2000 Congress on Evolutionary Computation CEC’2000, San Diego, CA, 2000, 857-863.
• [12] Church A., The Calculi of Lambda Conversion, Princeton, N.J., Princeton University Press, 1941.
• [13] Dean T., Boddy M., An Analysis of Time-Dependent Planning, in Proc. Seventh National Conf. on Artificial Intelligence,Minneapolis, Minnesota, 1988, 49-54.
• [14] Eberbach E., Neural Networks and Adaptive Expert Systems in the CSA Approach, Intern. Journal of Intelligent Systems, Special Issue on Artificial Neural Networks, vol. 8, no. 4, 1993, 569-602.
• [15] Eberbach E., CSA: In the Direction of Greater Representational Power for Neurocomputing, Journal of Parallel and Distributed Computing, vol. 22, no. 1, 1994, 107-112.
• [16] Eberbach E., SEMAL: A Cost Language Based on the Calculus of Self-modifiable Algorithms, Intern. Journal of Software Engineering and Knowledge Engineering, vol. 4, no. 3, 1994, 391-408.
• [17] Eberbach E., A Generic Tool for Distributed AI with Matching as Message Passing, Proc. of the Ninth IEEE Intern. Conf. on Tools with Artificial Intelligence TAI’97, Newport Beach, California, 1997, 11-18.
• [18] Eberbach E., Brooks R., Phoha S., Flexible Optimization and Evolution of Underwater Autonomous Agents, in: New Directions in Rough Sets, DataMining, and Granular-Soft Computing, LNAI 1711, Springer-Verlag, 1999, 519-527.
• [19] Eberbach E., Expressiveness of $-Calculus: WhatMatters?, in: Advances in Soft Computing, Proc. of the 9th Intern. Symp. on Intelligent Information Systems IIS’2000, Bystra, Poland, Physica-Verlag, 2000, 145-157.
• [20] Eberbach E., $-Calculus Bounded Rationality = Process Algebra + Anytime Algorithms, in: (ed.J.C.Misra) Applicable Mathematics: Its Perspectives and Challenges, Narosa Publishing House, New Delhi, Mumbai, Calcutta, 2001, 213-220.
• [21] Eberbach E., Is EntscheidungsproblemSolvable? Beyond Undecidability of Turing Machines and Its Consequence for Computer Science and Mathematics, in: (ed.J.C.Misra) Computational Mathematics, Modelling and Algorithms, Narosa Publishing House, New Delhi, 2003, 1-32.
• [22] Eberbach E.,Wegner P., Beyond Turing Machines, The Bulletin of the European Association for Theoretical Computer Science (EATCS Bulletin), 81, Oct. 2003, 279-304.
• [23] Eberbach E., Duarte Ch., Buzzell Ch., Martel G., A Portable Language for Control of Multiple Autonomous Vehicles and Distributed Problem Solving, Proc. of the 2nd Intern. Conf. on Computational Intelligence, Robotics and Autonomous Systems CIRAS’03, Singapore, Dec. 15-18, 2003.
• [24] Eberbach E., Goldin D., Wegner P., Turing’s Ideas and Models of Computation, in: (ed. Ch.Teuscher) Alan Turing: Life and Legacy of a Great Thinker, Springer-Verlag, 2004, 159-194.
• [25] Eberbach E., Eberbach A., On Designing CO$T: A New Approach and Programming Environment for Distributed Problem Solving Based on Evolutionary Computation and Anytime Algorithms, Proc. 2004 Congress on Evolutionary Computation CEC’2004, vol.2, Portland, OR, 2004, 1836-1843.
• [26] Fogel D.B., An Introduction to Evolutionary Computation Tutorial, 2001 Congress on Evolutionary Computation CEC’2001, Seoul, Korea, 2001.
• [27] Garvey A., Lesser V., Design-to-Time Real-Time Scheduling, IEEE Transactions on Systems, Man, and Cybernetics, 23 (6), 1993, 1491-1502.
• [28] Garzon M., Models of Massive Parallelism: Analysis of Cellular Automata and Neural Networks, Springer-Verlag, 1995.
• [29] Goldin D., Persistent Turing Machines as a Model of Interactive Computation, FoIKS’00, Cottbus, Germany, 2000.
• [30] Glover F., Genetic Algorithms and Scatter Search: Unexpected Potentials, Statistics and Computing, vol. 4, 1994, 131-140.
• [31] Glover F., Tabu Thresholding: Improved Search by Nonmonotonic Trajectories, ORSA Journal on Computing. vol. 7, No. 4, 1995, 426-442.
• [32] Glover F., Tabu Search Fundaments, Technical Report, Graduate School of Business, University of Colorado, Boulder, CO, (1995).
• [33] Hart P. E., Nilsson N. J., Raphael B., A Formal Basis for the Heuristic Determination ofMinimum Cost Paths, IEEE Trans. SSC SSC-4, 1968, 100-107.
• [34] Hoare C. A. R., Communicating Sequential Processes, Prentice-Hall, 1985.
• [35] Holland J., Adaptation in Natural and Artificial Systems, second edition, The MIT Press, 1992.
• [36] Hooker J. N., Needed: An Empirical Science of Algorithms, Operations Research, vol. 42, March-April 1994, 201-212.
• [37] Hopcroft J. E., Motwani R., Ullman J. D., Introduction to Automata Theory, Languages, and Computation, 2nd edition, Addison-Wesley, 2001.
• [38] Horvitz E., Reasoning about Beliefs and Actions under Computational Resources Constraints, in Proc. of the 1987Workshop on Uncertainty in Artificial Intelligence, Seattle, Washington, 1987.
• [39] Horvitz E., Zilberstein S. (eds.), Computational Tradeoffs under Bounded Resources, Artificial Intelligence 126, 2001, 1-196.
• [40] Hu T. C., Kahng A. B., Tsao C.-W. A., Old Bachelor Acceptance: A New Class of Non-Monotone Threshold Acceptance Methods, ORSA Journal on Computing. vol. 7, No. 4, (1995), pp. 417-425.
• [41] Koza J., “Genetic Programming: On the Programming of Computers by Means of Natural Selection”, “Genetic Programming II: Automatic Discovery of Reusable Programs”, “Genetic Programming III: Darvinian Invention and Problem Solving”, The MIT Press, 1992, 1994, and 1999.
• [42] Koza J., Advanced Genetic Programming Tutorial, Third Genetic Programming Conf. GP-98, Univ. of Wisconsin, Madison, 1998.
• [43] Kumar V., Grama A., Gupta A., Karypis G., Introduction to Parallel Computing: Design and Analysis of Algorithms, The Benjamin/Cummings, 1994.
• [44] Kuratowski K., Introduction to Set Theory and Topology, PWN, Warsaw, 1977.
• [45] Laarhoven P. J. M., Aarts E. H. L., Simulated Annealing: Theory and Applications. D. Reidel Publishing Co. Dordrecht, Netherlands, (1987).
• [46] Langton Ch., Artificial Life: An Overview, The MIT Press, 1996.
• [47] Last M., Kandel A., Maimon O., Eberbach E., Anytime Algorithm for Feature Selection, in: (eds.W. Ziarko, Y.Yao) Rough Sets and Current Trends in Computing, Second Intern. Conf. on Rough Sets and Current Trends in Computing RSCTC’2000, Banff, Canada, Oct. 2000, Revised Papers, LNAI 2005, Springer-Verlag, 2001, 532-539.
• [48] Liu J. W. S., Lin K. J., Shih W. K., Yu A. C., Chung J.Y., Zhao W., Algorithms for Scheduling Imprecise Computations, IEEE Computer, 24, 1991, 58-68.
• [49] Liu H., Motoda H., Feature Selection for Knowledge Discovery and Data Mining, Kluwer Academic Publishers, 1998.
• [50] Lohn J., Self-Replication Systems in Cellular Space Models Tutorial, Genetic Programming Conference GP97, Stanford University, 1997.
• [51] Maes P. (ed.), Designing Autonomous Agents: Theory and Practice from Biology to Engineering and Back, The MIT Press, 1994.
• [52] Maimon O., Last M., Knowledge Discovery and Data Mining, the Info-Fuzzy Network (IFN) Methodology, Kluwer, 2000 (in press).
• [53] Michalewicz Z., Genetic Algorithms + Data Structures = Evolution Programs, third edition, Springer-Verlag, 1996.
• [54] Michalewicz Z., Fogel D. B., How to Solve It: Modern Heuristics, Springer-Verlag, 2000.
• [55] Michalski R. S., Bratko I., Kubat M., Machine Learning and Data Mining: Methods and Applications, John Wiley & Sons, 1998.
• [56] Milner R., A Calculus of Communicating Systems, Lect. Notes in Computer Science vol. 94, Springer-Verlag, 1980.
• [57] Milner R., Operational and Algebraic Semantics of Concurrent Processes, in: Handbook of Theoretical Computer Science, Vol. B: Formal Models and Semantics, J. Van Leeuwen, Managing Editor, The MIT Press/Elsevier, 1990, 1203-1242.
• [58] Milner R., Parrow J., Walker D., A Calculus of Mobile Processes, I & II, Information and Computation 100, 1992, 1-77.
• [59] Milner R., The Polyadic π-Calculus: A Tutorial, in F.L.Bauer,W.Brauer (eds.) Logic and Algebra of Specification, Springer-Verlag, 1992, 203-246.
• [60] Milner R., Elements of Interaction, CACM, Jan. 1993, vol. 36, no. 1, 78-89.
• [61] Milner R., Operational and Algebraic Semantics of Concurrent Processes, in: (ed. J. van Leeuwen) Handbook of Theoretical Computer Sciece, Vol.B: Formal Models and Semantics, Elsevier and The MIT Press, 1994, 1203-1242.
• [62] Moravec H., Mind Children, Harvard Univ. Press, 1988.
• [63] Nilsson N., Problem Solving Methods in Artificial Intelligence,McGraw-Hill, 1971.
• [64] Nilsson N., Artificial Intelligence: A New Synthesis, Morgan Kaufmann, 1998.
• [65] Pawlak Z., Rough Sets, Int. J. Computer and Information Sci., 11, 1982, 341-356.
• [66] Phoha S., Peluso E., Stadter P., Stover J., Gibson R., A Mobile Distributed Network of Autonomous Undersea Vehicles, Proc. of the 24th Annual Symposium and Exhibition of the Association for Unmanned Vehicle Systems International, Baltimore, MD, 1997.
• [67] Plotkin G., Stirling C., Tofte M., Proof, Language, and Interaction: Essays in Honour of Robin Milner, MIT Press, 2000.
• [68] Quinlan J. R., C4.5: Programs for Machine Learning,Morgan Kaufmann, 1993.
• [69] Russell S., Norvig P., Artificial Intelligence: A Modern Approach, Prentice-Hall, 1995 (2nd ed. 2003).
• [70] Russell S., Wefald E., Do the Right Thing: Studies in Limited Rationality, The MIT Press, 1991.
• [71] Shannon C. E., Programming a computer for playing chess, Philosophical Magazine, 41 (4), 1950, 256-275.
• [72] Siegelmann H. T., Neural Networks and Analog Computation: Beyond the Turing Limit, Birkhauser, 1999.
• [73] Sipper M. et al, The Firefly Machine: Online Evolware. In Proc. of IEEE Fourth Intern. Conf. on Evolutionary Computation ICEC’97, 1997.
• [74] Sutton R. S., Barto A. G., Reinforcement Learning: An Introduction, MIT Press, 1998.
• [75] Sutton R. S., Toward Grounding Knowledge in Prediction or Toward a Computational Theory of Artificial Intelligence, an invited talk at Congress on Evolutionary Computation CEC’2000, San Diego, July 18, 2000.
• [76] Tam K., Lloyd J., Lesperance Y., Levesque H., Lin F., Marcy D., Reiter R., Jenkin M., Controlling Autonomous Robots with GOLOG, in Proc. of the Tenth Australian Joint Conf. on Artificial Intelligence AI’97, LNAI, Springer-Verlag, 1997, 1-12.
• [77] Turing A., On Computable Numbers, with an Application to the Entscheidungsproblem, Proc. of the London Mathematical Society, ser. 2, vol. 42 , 1936-37, 230-265; corrections, Ibid, vol. 43, 1937, 544-546.
• [78] Turing A., Systems of Logic based on Ordinals, Proc. of the London Mathematical Society, ser. 2, vol. 45, 1939, 161-228.
• [79] Van Leeuwen J, (ed.), Handbook of Theoretical Computer Science, Vol. A and B, The MIT Press/Elsevier, 1990.
• [80] Van Leeuwen J., Wiedermann J., The Turing Machine Paradigm in Contemporary Computing, 2001.
• [81] Von Neumann J., Morgenstern O., Theory of Games and Economic Behavior, Princeton University Press, 1944.
• [82] Wegner P., Why Interaction is More Powerful Than Algorithms, CACM, May 1997, vol. 40, no. 5, 81-91.
• [83] Wegner P., Interactive Foundations of Computing, Theoretical Computer Science, 192, 1998, 315-351.
• [84] Wegner P., Goldin D., Coinductive Models of Finite Computing Agents, Electronic Notes in Theoretical Computer Science, vol. 19, 1999.
• [85] Wegner P., Eberbach E., New Models of Computation, The Computer Journal, 47 (1), The British Computer Society, Oxford University Press, 2004, 4-9.
• [86] Wolfe W. L., Introduction to Imaging Spectrometers, Tutorial Text, vol. TT25, SPIE Press, Bellingham, WA, 1997.
• [87] Wolpert D. H., Tumer K., An Introduction to Collective Intelligence, in Bradshaw J. M. ed., Handbook of Agent Technology, AAAI Press/MIT Press, 2000.
• [88] Zadeh L. A., Fuzzy Sets, Information and Control, 12, 1965, 338-353.
• [89] Zilberstein S., Operational Rationality through Compilation of Anytime Algorithms, Ph.D. Thesis, Univ. of California at Berkeley, 1993.