In this work, we examine the problem of online decision making under uncertainty, which we formulate as planning in the belief space. Maintaining beliefs (i.e., distributions) over high-dimensional states (e.g., entire trajectories) was not only shown to significantly improve accuracy, but also allows planning with information-theoretic objectives, as required for the tasks of active SLAM and information gathering. Nonetheless, planning under this "smoothing" paradigm holds a high computational complexity, which makes it challenging for online solution. Thus, we suggest the following idea: before planning, perform a standalone state variable reordering procedure on the initial belief, and "push forwards" all the predicted loop closing variables. Since the initial variable order determines which subset of them would be affected by incoming updates, such reordering allows us to minimize the total number of affected variables, and reduce the computational complexity of candidate evaluation during planning. We call this approach PIVOT: Predictive Incremental Variable Ordering Tactic. Applying this tactic can also improve the state inference efficiency; if we maintain the PIVOT order after the planning session, then we should similarly reduce the cost of loop closures, when they actually occur. To demonstrate its effectiveness, we applied PIVOT in a realistic active SLAM simulation, where we managed to significantly reduce the computation time of both the planning and inference sessions. The approach is applicable to general distributions, and induces no loss in accuracy.
翻译:在这项工作中,我们检查了在不确定情况下进行在线决策的问题,我们把它作为信仰空间的规划。在高维状态(例如整个轨道)上维持信仰(即分布)不仅显示大大提高了准确性,而且允许按照积极SLM和信息收集任务所需的信息理论目标进行规划。然而,在这种“移动”模式下进行规划具有很高的计算复杂性,这给在线解决方案带来挑战。因此,我们提出以下想法:在规划之前,对最初的信仰进行独立的状态变量重新排序程序,并“向前推进”所有预测的循环结束变量。由于最初的变数顺序决定了哪些类别将受到最新消息的影响,这种重新排序使我们能够最大限度地减少受影响的变量总数,并降低在规划期间对候选人评价的计算复杂性。我们称之为PIVOT:预测性增量变异策略。应用这一策略还可以提高状态的效率;如果我们在规划阶段后维持PIVOOT秩序,那么在规划阶段,我们在实际的模拟过程中将大幅降低成本,在规划周期的升级过程中,我们同样应该降低成本。