Series: Penn State Logic Seminar Date: Tuesday, April 25, 2000 Speaker: Eugene Eberbach, Acadia University, Computer Science Title: $-Calculus Bounded Rationality = Process Algebra + Anytime Algorithms Time: 2:30 - 3:20 PM Place: 219 Thomas Building Abstract: This talk will be about bounded rationality. Recently, there has been shift from consideration of optimal decisions in simple search algorithms and games to a consideration of optimal decision-making programs for dynamic, inaccessible, complex environments that are closer to the real world. Unfortunately to be perfectly rational is impossible, because of prohibiting deliberation complexity. Anytime algorithms attempt to trade off result quality for the time or memory needed to generate results. A bounded rational agent is one that always takes the action that is expected to optimize its performance measure - costs, given the percept sequence it has seen so far and limited resources one has. Nobody proposed so far, anytime algorithms as a general theory of computation. Based on Church’s lambda-calculus, Milner’s pi-calculus and Wegner’s interaction machines, we extend process algebra operators with von Neumann/Morgenstern’s costs/utilities. As the result we shift a computational paradigm from the design of agents achieving one-time goals, to the agents who persistently attempt to optimize their happiness. We believe that this will lead to more rational programs, more rational computers, and perhaps more rational world. Intelligence is a moving target if it is not well defined, thus adding a computable performance measure, should have the highest priority. In our approach to achieve a ``nirvana'' means to achieve a global optimum, which is a well defined concept. We call the presented approach $-calculus (pronounced ``cost-calculus''), which is a higher-order polyadic process algebra with a utility (cost) allowing to capture bounded optimization and metareasoning in distributed interactive AI systems. Unique aspects of $-calculus are proposing anytime algorithms as a general theory of computation comparable to lambda- or pi-calculi, targeting more expressive than Turing machines models, extension of performance measures beyond time to include answer quality and uncertainty, a complete set of operators to build rational programs, k Omega -optimization to deal with spatial and temporal constraints in a flexible way. Each agent has its own Omega search space and its own limited horizon of deliberation k. Agents can cooperate by selecting actions with minimal costs, can compete if some of them minimize and some maximize costs, and be impartial (irrational or probabilistic) if they do not attempt to optimize (evolve, learn) from the point of view of the observer. $-calculus leads to a new programming paradigm cost languages and a new class of computer architectures cost-driven computers. Similar like neural networks or genetic algorithms, it can be applied to anything. The NSERC supported 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. Potentially could be used for design of cost langugages, cellular evolvable cost-driven hardware, DNA-based computing and molecular biology, electronic commerce, and quantum computing. It has been applied to the Office of Naval Research SAMON robotics testbed at ARL Penn State to derive GBML (Generic Behavior Message-passing Language) for behavior planning, control and communication of heterogeneous Autonomous Underwater Vehicles (AUVs).
Mathematical Logic at Penn State
Department of Mathematics