This paper presents a system-theoretic approach to the general problem of autonomous planning under uncertainty. The autonomous planning problem involves an automaton (an autonomous machine) which interacts with an environment via a set of unreliable control and sensing operations. The task assigned to the automaton is to plan and execute a sequence of control and sensing operations which changes the state of the environment in a desirable way. The paper introduces the concept of an Uncertainty Machine which models the propagation of the information from the environment to the automaton during the execution of the plans. Based on the concept of an uncertainty machine, mathematical expressions are presented for the active-sensing, the passive-sensing and the control (sensorless) entropies of an arbitrary execution instance. These entropies are shown to be useful measures of the automaton's ability to utilize its control and sensing resources in reducing its uncertainty. In a companion paper,7 the concept of an uncertainty machine is utilized to synthesize strategies which enable the automaton to actively explore the environment. |