Data Association Aware POMDP Planning with Hypothesis Pruning Performance Guarantees
This work addresses the problem of computational overhead in POMDP planning for autonomous agents dealing with ambiguous data associations, representing an incremental improvement over traditional methods.
The paper tackles the computational challenge of planning under partial observability with ambiguous data associations by proposing a pruning-based algorithm that maintains multiple data association hypotheses as a belief mixture. It derives bounds on the value function to trade off efficiency and performance, demonstrating efficacy in simulated environments.
Autonomous agents that operate in the real world must often deal with partial observability, which is commonly modeled as partially observable Markov decision processes (POMDPs). However, traditional POMDP models rely on the assumption of complete knowledge of the observation source, known as fully observable data association. To address this limitation, we propose a planning algorithm that maintains multiple data association hypotheses, represented as a belief mixture, where each component corresponds to a different data association hypothesis. However, this method can lead to an exponential growth in the number of hypotheses, resulting in significant computational overhead. To overcome this challenge, we introduce a pruning-based approach for planning with ambiguous data associations. Our key contribution is to derive bounds between the value function based on the complete set of hypotheses and the value function based on a pruned-subset of the hypotheses, enabling us to establish a trade-off between computational efficiency and performance. We demonstrate how these bounds can both be used to certify any pruning heuristic in retrospect and propose a novel approach to determine which hypotheses to prune in order to ensure a predefined limit on the loss. We evaluate our approach in simulated environments and demonstrate its efficacy in handling multi-modal belief hypotheses with ambiguous data associations.