The $-Calculus of Bounded Rational Agents for Problem Solving

The $-Calculus of Bounded Rational Agents for Problem Solving

The $-calculus (pronounced: cost calculus) is the process algebra which provides the support for distributed problem solving based on ideas of anytime algorithms/resource bounded computation. Its uniqueness is to target real-world intractable optimization problems, and to provide support for nonalgorithmic solutions of undecidable problems. It is based on the former author's work on the Calculus of Self-modifiable Algorithms, leading to a higher-order polyadic process algebra called $-calculus. Process algebras are currently the most mature approach to concurrent and distributed systems.

This ONR and NSERC supported research is about flexible optimization and adaptation under bounded resources in real-time complex systems. Resource bounded computation is known under a variety of names, including flexible computation, anytime algorithms, imprecise computation, design-to-time scheduling. All attempt to trade off result quality for the time or memory needed to generate results. A process algebra variant of resource-bounded computation is proposed to integrate deliberative and reactive approaches for action selection in real time. The approach has been developed independent of anytime algorithms under the name of $-calculus. Unique aspects of this approach are proposing anytime algorithms as a general theory of computation comparable to l- or p-calculi, an extension of performance measures beyond time to include answer quality and uncertainty, a complete set of operators to build programs, the kW-optimization to deal with spatial and temporal constraints in a flexible way. The $-calculus integrates several approaches to problem solving into a common framework, including neural networks, evolutionary computation, symbolic AI, and autonomous agents.

The $-calculus although being a relatively new approach has found already several applications. It has been applied to the Office of Naval Research Project SAMON project for coordination of multiple heterogeneous Autonomous Undersea Vehicles (AUVs). The Generic Behavior Message-Passing Language (GBML), and Common Control Language (CCL) have been derived from $-calculus for communication and control of multiple cooperating mobile robots. The project on $-calculus aims at investigation, design and implementation of a wide class of adaptive real-time complex systems exhibiting meta-computation and optimization. This includes robotics, software agents, neural nets, and evolutionary computation.

Current Goals and Some Open Research Problems:

$-calculus as a formal model of resource-bounded computation. Resource bounded computation attempts to find the best answer possible given operational constraints. The approach is known under a variety of names, including flexible computation, anytime algorithms, imprecise-computation, or design-to-time scheduling (see, e.g. Dean, Horvitz, Zilberstein). Anytime algorithms together with decision-theoretic metareasoning (Russell) are two new promising techniques and their application to general decision-making architectures has not yet been investigated in any depth.

$-calculus as a universal model of computation and its expressiveness. It looks that interactive distributed systems (e.g., intelligent agents) require formalisms having richer behavior than Turing machines and algorithms. Investigation of the $-calculus expressiveness in relation to other models of computation, including other superTuring models of computation. It will be investigated a hierarchy of expressiveness of particular models. Problems of universal computation and universal construction will be studied in the context of this new model.

Formal semantics of $-calculus based on non-well-founded sets and coinduction. Formal semantics of $-calculus is given in a typical form for process algebras, i.e. in the form of the Labeled Transition System, inference rules and meta-level cost control. Wegner et al have suggested that interactive systems require models based on non-well-founded sets, coinduction and greatest fixed points.

Cost metrics performance measure standardization and generality. A unique aspect of $-calculus, compared to other models of computation, is its associated cost mechanism. So far, a standard cost function is predefined in $-calculus that allows to use probabilities, fuzzy sets and rough sets. The user is free to define own cost functions. It will be desirable to establish a library of most common cost metrics spanning as many applications as possible. Such a standardization attempt should benefit also the field of evolutionary computation. Does there exist a minimal and complete set of cost functions? Is a complexity theory just a special case of asymptotic cost function metrics?

Axiomatization of cost/utiltiy theory. Can we define better, more general (i.e., not based on lotteries and probabilities) and concise axioms for costs than is provided by von Neumann/Morgenstern's utility theory (e.g., like Kolmogorov did in an elegant way for probability theory)?

Cost function profiling. This is a crucial problem for applicability of cost calculus, i.e., to establish the way to define costs of atomic cost expressions (an analogue of the elementary probability distribution). Resource-bounded optimization typically assumes that statistics from previous experiments are used to develop profiles of cost functions. Deduction and empirical testing can be used to derive costs of atomic and composite cost expressions.

Meta-level control standardization and generality. The $-calculus uses a kW-optimization for meta-level control, which is a generalization of control structures used for adaptive expert systems, evolutionary computation and neural nets. It is a very generic control structure allowing to simulate many other search algorithms. However, in a similar was as an evolutionary algorithm may lead to a more complex form like the cultural, or genocop algorithm, the $-calculus allows for an arbitrary flexible meta-control. Thus a work on the library of typical meta-control is needed. Can a kW-optimization evolve to a better version of itself?

Emerging global behavior, design and integration of reactive and deliberate behaviors. There are three basic questions for autonomous agents (also valid for dynamical systems, Alife, robotics): how does an ensemble of agents produce intelligent or interesting output (an emerging global behavior), how to best decompose a global job into the group of interacting agents, and how to integrate reactive and deliberative behaviors? $-calculus addresses all three problems in a unique way. The feasibility of emerging global behavior is investigated as emerging global optimization through local optimizations. The design (synthesis) problem is done by the $-calculus meta-control to partition job in the direction of minimal costs. The integration of reactive and deliberative behaviors is done by modifying the parameter k for the kW-optimization.

Dealing with incomplete and uncertain knowledge. To deal with incomplete and uncertain knowledge, the $-calculus has built-in standard cost function. Another innovative aspect of the approach is the kW-optimization using invisible cost expressions to mask unknown or intractable portions of the search space. Can we incorporate other approaches to undertainty, like cost functions based on Dempster-Shafer theory of evidence, nonmonotonic logics? Are truly probabilistic methods superior over other methods to find optimal solutions in the presence of uncertainty (de Finetti's theorem)?

Cost Languages design and implementation. We can distinguish at least 7 main classes of programming languages: procedural, object-oriented, functional applicative and single assignment, logic, rule-based, and semantic network languages. Cost languages based on the $-calculus model of computation introduce a distinct new programming paradigm. After the SEMAL and GBML prototypes, two experimentary systems are under design and implementation: CO$T - a general purpose programming language, and CCL - a specialized languegs for mission planning and control of multiple Autonomous Underwater Vehicles.

The Long-Term Goals:

The design and implementation of anytime evolvable robots. It has been suggested that traditional AI approach of sense-plan-act is too slow and brittle for producing effective robotic systems. A nouvelle behavioral approach to robotics of purely reactive systems (Brooks), which do not build a symbolic world representation, are not scalable and not sufficient for a number of problems inherent in robotics. Instead of approaches being forcibly either reactive or deliberative, the use of $-calculus process algebra with meta-reasoning allows the systems to react flexibly using either deliberation or reaction as appropriate. Combining the best of both worlds should be beneficial for robotics.

The design and implementation of evolvable cost-driven architectures. Cost-driven computers are computer architecture representatives of $-calculus. Between the $-calculus, cost languages and cost-driven computers is the same relation as between Hoare's CSP, OCCAM and Transputer-based architectures. The main principle of work of cost-driven computers is to choose the minimal cost instruction for execution from the set of possible ones. The cost-driven model of computation is different from control-driven, data-driven, demand-driven, or pattern-driven models. An evolvable cost-driven cellular computer CICADA should be re-configurable and each cell should implement the $-calculus kW-optimization in FPGA.

Electronic commerce market behavior analysis, prediction and control. The $-calculus with its optimization cost mechanism could be useful for distributed market behavior analysis, prices and profits prediction and control.

DNA-based agents and bioinformatics.An agent architecture provides a more natural model for DNA-based computing. Algorithmic descriptions of DNA computing are fundamentally flawed by failing to account for the chemical complexity of collections of biomolecules. DNA computing incorporates self-modifiability through the action of enzymes. Through the minimization of free energy, a DNA-based computer is a cost-driven machine. The $-calculus can provide the theoretical framework to direct, control, and better understanding of DNA-based computing. In bioinformatics, the $-calculus flexible optimization search mechanism could be investigated for solutions of hard problems of DNA sequence alignment, protein folding and structure prediction by energy minimization.

Design and implementation of hybrid expert systems, neural nets, genetic algorithms, and fuzzy systems. The $-calculus can express an arbitrary neural network, evolutionary computation, rule-based expert system, or logic programming. Very often, it is unclear, which of these methods will work the best, or the system may consist of heterogeneous modules. Then an integration under one theoretical framework subsymbolic and symbolic systems should be beneficial, i.e., the $-calculus will either allow to pick up the best method, or to to glue heterogeneous components.

Simulation and investigation of quantum computing and algorithms. It is expected that the progress in the miniaturization of computer hardware components will lead in 2020s, independently which computing paradigm will dominate, to the necessity to take into account quantum effects. Two basic features of quantum computing are quantum parallelism and quantum superposition of states in qubits. Quantum superposition could be interpreted as a new $-calculus cost metric in the domain of complex numbers, and parallelism is inherent in $-calculus. Whether a $-calculus could be useful for quantum computing, it is an open research question and requires careful studies.