Efficient Planning under Uncertainty with Macro-actions
This work addresses the challenge of multi-step planning for robotics and AI in real-world, large partially observable domains, though it appears incremental as it builds on existing forward-search methods.
The paper tackles the problem of planning under uncertainty in partially observable environments by introducing the Posterior Belief Distribution (PBD) algorithm, which efficiently evaluates macro-actions to achieve good control performance in large domains, as demonstrated in simulation experiments and a real robotic helicopter application.
Deciding how to act in partially observable environments remains an active area of research. Identifying good sequences of decisions is particularly challenging when good control performance requires planning multiple steps into the future in domains with many states. Towards addressing this challenge, we present an online, forward-search algorithm called the Posterior Belief Distribution (PBD). PBD leverages a novel method for calculating the posterior distribution over beliefs that result after a sequence of actions is taken, given the set of observation sequences that could be received during this process. This method allows us to efficiently evaluate the expected reward of a sequence of primitive actions, which we refer to as macro-actions. We present a formal analysis of our approach, and examine its performance on two very large simulation experiments: scientific exploration and a target monitoring domain. We also demonstrate our algorithm being used to control a real robotic helicopter in a target monitoring experiment, which suggests that our approach has practical potential for planning in real-world, large partially observable domains where a multi-step lookahead is required to achieve good performance.