CSE Colloquium: Eugene Eberbach

A Uniform Approach to Automatic Problem Solving in the Context of Process Calculi of Self-modifying Algorithms and Bounded Rational Agents

Eugene Eberbach, Ph.D., D.Sc., Professor of Practice

Dept. of Engineering and Science, Rensselaer Polytechnic Institute

275 Windsor Street, Hartford, CT 06120

www.ewp.rpi.edu/~eberbe

Abstract

The never ending dream of universal problem solving methods resurrect throughout all computer science history, including Universal Turing Machine, Simon and Newell’s General Problem Solver (GPS), Evolutionary Algorithms, Prolog and Fifth Generation Computers Project, Koza’s Genetic Programming Problem Solver (GPPS), and, more recently, CSA/$-calculus. Unfortunately, most results are negative: a universal algorithm does not exist (famous halting/decision problem of Universal Turing Machine), or No Free Lunch Theorem. The $-calculus gives some hope that despite that a universal algorithm does not exist, it can be indefinitely asymptotically approximated.

The $-Calculus (read: Cost Calculus) is a process algebra using anytime algorithms for automatic problem solving targeting intractable and undecidable problems. It is formalization of resource-bounded computation (anytime algorithms) guaranteeing to produce better results if more resources (e.g., time, memory) become available. Its unique feature is support for problem solving by incrementally searching for solutions and using cost performance measure to direct its search. Historically, it has been inspired by Church’s l-calculus and Milner’s p-calculus. The $-calculus covers parallel algorithms, belongs to super-Turing models of computation, has built-in support for automatic problem solving (kW-optimization) and uses cost as a basic primitive. The kW-optimization meta-search represents this “impossible” to construct but “possible to approximate indefinitely” universal algorithm. It is a very general search method, allowing to simulate many other search algorithms, including A*, Minimax, ID3, dynamic programming, tabu search, evolutionary algorithms, neural networks, cooperating or competing multi-agent systems. To deal with uncertainty, it can use probabilities or fuzzy sets or rough sets membership functions. The advantage of the $-calculus approach is that it allows to experiment, combine and compare various methods in a uniform framework, to experiment with them; to select on-line the best method, or perhaps, to produce a new search algorithm.  

Short Biographical Note about the Speaker

Dr. Eugene Eberbach is Professor of Practice at Department of Engineering and Science, Rensselaer Polytechnic Institute, Hartford, USA. He has D.Sc. (2015) degree in Computer Science from AGH University of Science and Technology, Ph.D. (1982) degree in Applied Mathematics, and M.Sc. and Eng. (1977) degree in Computer Science  both from Warsaw University of Technology, Poland. He held various academic and industrial positions in USA, Canada, United Kingdom and Poland, including Rensselaer Polytechnic Institute, University of Massachusetts Dartmouth, Acadia University, Technical University of Nova Scotia/Dalhousie University, University of Memphis, University College London, Rzeszow University of Technology, WSK “PZL-Rzeszow” and Applied Research Lab, Pennsylvania State University. In late 1980s he worked on new non-von Neumann 5^th Generation Computer Architectures at University College London. In 1990-2000s he worked on distributed autonomous underwater vehicles with support of ONR. In Canada and USA he introduced Calculus of Self-modifiable Algorithms and $-Calculus process algebra for automatic problem solving under bounded resources with support of NSERC and ONR. He proposed two super-Turing models of computation: $-Calculus and Evolutionary Turing Machines. His current work is in the areas of process algebras, resource bounded optimization, autonomous agents and mobile robotics. General topics of interest are new computing paradigms, languages and architectures, distributed computing, concurrency and interaction, evolutionary computing and neural nets. Dr. Eberbach is the author of more than 170 publications in the above areas and he has been a recipient of 17 external research grants. More information about projects, publications, courses taught can be found at  http://www.ewp.rpi.edu/~eberbe.