In this work, we introduce a new and efficient solution approach for the problem of decision making under uncertainty, which can be formulated as decision making in a belief space, over a possibly high-dimensional state space. Typically, to solve a decision problem, one should identify the optimal action from a set of candidates, according to some objective. We claim that one can often generate and solve an analogous yet simplified decision problem, which can be solved more efficiently. A wise simplification method can lead to the same action selection, or one for which the maximal loss in optimality can be guaranteed. Furthermore, such simplification is separated from the state inference and does not compromise its accuracy, as the selected action would finally be applied on the original state. First, we present the concept for general decision problems and provide a theoretical framework for a coherent formulation of the approach. We then practically apply these ideas to decision problems in the belief space, which can be simplified by considering a sparse approximation of their initial belief. The scalable belief sparsification algorithm we provide is able to yield solutions which are guaranteed to be consistent with the original problem. We demonstrate the benefits of the approach in the solution of a realistic active-SLAM problem and manage to significantly reduce computation time, with no loss in the quality of solution. This work is both fundamental and practical, and holds numerous possible extensions.
翻译:在这项工作中,我们引入了一种在不确定情况下决策问题的新的、有效的解决办法,这种办法可以作为信仰空间的决策,在可能高维的状态空间中,在可能高维的状态空间中形成一种决策空间。通常,为了解决一个决策问题,人们应当根据某些目标,从一组候选人中确定最佳行动。我们声称,一个人往往能够产生和解决一个相似的、简化的决定问题,这些问题可以更有效率地解决。明智的简化方法可以导致同样的行动选择,或者保证最佳性的最大损失。此外,这种简化可以与状态的推断分开,并且不会损害其准确性,因为所选择的行动最终会适用于初始状态。首先,我们提出一般决定问题的概念,并为连贯地制定方法提供一个理论框架。然后,我们实际地将这些想法应用于信仰空间中的决策问题,如果考虑到最初信念的细微近近,就可以简化。我们提供的可缩缩信通缩算法能够产生保证与最初问题相一致的解决办法。我们展示了在解决实际实际的、实际质量和可能的计算方法方面的做法的好处。