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).