Dynamic Sensor Policies
Kurt D. Krebsbach, Maria L. Gini · 1994
When an agent’s task environment is largely benign and partially predictable (although uncertain), and the goals involve accomplishing tasks, we can make the agent more adaptive by planning to acquire unknown or uncertain information during execution of the task. Of course we pay a price for this flexibility. In this paper we dicuss a strategy for measuring this price in a realistic way and reducing it by making rational decisions about how to acquire unknown environmental information with imperfect sensors. Ultimately, we are interested in a generM framework for making optimal sensor decisions which will minimize a cost (or set of costs) we expect to incur by employing sensors. In particular, we propose to generate a tree of possible sensing policies offline (using dynamic programming), cache the optimal sensor decisions at each level, and subsequently use actual world states as indexes into this structure to make a rational sensor choice online. Because no states are discarded in the dynamic programming process (only non-optimal paths), we are always guaranteed of having earlier cached an optimal decision for each state we anticipate possibly encountering at execution time. This combination of offiine and online computation allows the sensor selection process to be sensitive to actual events, while making use of assumptions and regularities inherent in the structure of the domain. The work presented here builds on some of our earlier work in which we have discussed strategies for static (i.e., offline) sensor scheduling [Krebsbach et al., 1992, Olawsky et al., 1993], and in which we have used techniques similar to these to combat the inherent computational complexity of the problems involved [Krebsbaeh, 1993]. Many of these ideas have been suggested by others employing decision-theoretic methods for a wide variety of optimization and control problems, including those related to planning and sensing [Bellman, 1957, Boddy, 1991b]. Boddy proposes the use of dynamic programming for constructing anytime algorithms [Boddy, 1991a]. Hager and Mintz [1991] have proposed methods for sensor planning based on probabilistic models of uncertainty. Abramson [1991] casts sensory integration as a decision problem and presents a formula for deciding how often to sense, depending on the rate of change of the environment. Goodwin and Simmons [1992] use a decision-theoretic approach to incorporate the achievement of a new goal into a partially executed plan, and Chrisman and Simmons employ Markov Decision Processes in order to handle a significant amount of uncertainty in the outcomes of actions [1991].