Investigations of Continual Computation

Autonomous agents that sense, reason, and act in
real-world environments for extended periods often
need to solve streams of incoming problems. Traditionally,
effort is applied only to problems that have
already arrived and have been noted. We examine
continual computation methods that allow agents
to ideally allocate time to solving current as well
as potential future problems under uncertainty. We
first review prior work on continual computation.
Then, we present new directions and results, including
the consideration of shared subtasks and
multiple tasks. We present results on the computational
complexity of the continual-computation
problem and provide approximations for arbitrary
models of computational performance. Finally, we
review special formulations for addressing uncertainty
about the best algorithm to apply, learning
about performance, and considering costs associated
with delayed use of results.