Affiliations: Computer and Information Science Department,
University of Massachusetts Dartmouth, North Dartmouth, MA 02747, USA. E-mail:
[email protected]
Abstract: 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,
λ-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.
Keywords: resource bounded computation, process algebra, problem solving, search, complete-ness, optimization, total optimization
