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.
翻译:在现实世界中操作的自主智能体通常要处理部分可观测性问题,这通常可以被建模为部分可观察马尔可夫决策过程(POMDPs)。然而,传统的 POMDP 模型依赖于对观测源的完全知识,被称为完全可观测的数据相关联性。为了解决这个问题,我们提出了一种规划算法,它保持多个数据关联假设,表示为信念混合物,其中每个组成部分相应于不同的数据关联假设。然而,这种方法可能导致假设数量呈指数级增长,进而导致计算负担显著。为了克服这个挑战,我们引入了一种基于修剪的方法,用于处理模糊数据关联相关方案的规划。我们的主要贡献在于,我们基于完整的假设集和基于假设的修剪子集之间的价值函数之间推导出上下界,从而使我们能够在计算效率和性能之间建立一种平衡。我们演示了这些界既可以用于事后证明任何修剪启发式方法,也提出了一种确定哪些假设要修剪,以确保损失的预定义限制的新方法。我们在模拟环境中评估了我们的方法,并展示了它在应对具有模糊数据关联假设的多模态信念假设方面的有效性。