Continual on-line planning as decision-theoretic incremental heuristic search

Details

Event AAAI 2010 Spring Symposium on Embedded Reasoning: Intelligence in Embedded Systems

Authors

Do, Minh B.
Sungwook Yoon
Technical Publications
March 22nd 2010
This paper presents an approach to integrating planning and execution in time-sensitive environments. We present a simple setting in which to consider the issue, that we call continual on-line planning. New goals arrive stochastically during execution, the agent issues actions for execution one at a time, and the environment is otherwise deterministic. We take the objective to be a form of time-dependent partial satisfaction planning reminiscent of discounted MDPs: goals offer reward that decays over time, actions incur fixed costs, and the agent attempts to maximize net utility. We argue that this setting highlights the central challenge of time-aware planning while excluding the complexity of non-deterministic actions. Our approach to this problem is based on real-time heuristic search. We view the two central issues as the decision of which partial plans to elaborate during search and the decision of when to issue an action for execution. We propose an extension of Russell and Wefalds decision-theoretic A* algorithm that can cope with our inadmissible heuristic. Our algorithm, DTOCS, handles the complexities of the online setting by balancing deliberative planning and real-time response.

Citation

Lemons, S.; Benton, J.; Ruml, W.; Do, M. B.; Yoon, S. Continual on-line planning as decision-theoretic incremental heuristic search. AAAI Spring Symposium on Embedded Reasoning: Intelligence in Embedded Systems; 2010 March 22-24; Stanford, CA.

Additional information

Focus Areas

Our work is centered around a series of Focus Areas that we believe are the future of science and technology.

FIND OUT MORE
Licensing & Commercialization Opportunities

We’re continually developing new technologies, many of which are available for¬†Commercialization.

FIND OUT MORE
News

PARC scientists and staffers are active members and contributors to the science and technology communities.

FIND OUT MORE