Continual On-line Planning as Decision-Theoretic Incremental Heuristic Search
| Seth Lemons | - |
University of New Hampshire |
| J. Benton | - |
Arizona State University |
| Minh Do, Sungwook Yoon | - |
Palo Alto Research Center |
Abstract:
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 Wefald’s 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.
Download Presentation: 
|
