RI: Small: Stochastic Planning and Probabilistic Inference for Factored State and Action Spaces

在随机环境中，许多重要的问题需要并行控制多个执行器或代理来实现共同的协调目标。这类问题的示例包括在有多个电梯的建筑物中进行调度、管理消防和救援操作团队、管理大型公司的库存、控制机器人足球队以及控制机器人团队来管理仓库环境中的货架和订单。这些问题自然适合于离散时间中央控制问题的公式，我们设计一个算法来决定每个代理在任何时间步采取什么行动，以优化共同目标。相应的计算问题，被称为随机规划，由于其庞大的规模而具有挑战性。特别是，在任何感兴趣的问题实例中，可能状态的数量（例如，机器人、货架和仓库中商品的可能位置）和可能联合动作的数量（单个机器人的动作组合）都是巨大的。最先进的方法通常会失败，因为需要太多的时间来正确地搜索一个好的策略，或者需要太多的内存来存储中间值。通过概率推理的视角来看待随机规划，本项目提出了几种新的领域独立算法方法，这些方法利用问题结构在时间约束下有效地计算近似解。项目资金主要用于支持博士生的培训和研究，因此直接支持国家重要的高影响力领域的人类发展。更具体地说，我们提出了三种相互竞争的方法来解决这些问题，所有这些方法都是从相应的图形模型（也称为动态贝叶斯网络）中将有限视界控制问题表述为概率推理中获得的见解。第一种方法使用蒙特卡罗搜索的思想，但通过引入聚合轨迹增加了强大的符号成分。在对随机变量独立的假设下，通过模拟组合符号模型得到了集合轨迹。每个聚合轨迹提供了一个近似的值估计，但可以取代许多单独的轨迹。通过这种方法，我们可以得到快速逼近值和在时间约束下的有效控制。第二种方法使用问题结构将推理问题转化为整数线性规划，其中可以通过问题分解来权衡解决方案的目标和质量。一种新颖的结构展示了如何避开问题的指数复杂性，获得一个小而可分解的整数程序序列，从而在时间约束下产生有效的控制。第三种方法，或者更准确的框架，建立在随机规划和相应的动态贝叶斯网络的概率推理之间紧密联系的基础上。我们证明了前两种方法的变体可以从这个角度来看待，并通过这一点，我们提出了解决随机规划问题的新推理算法。此外，在此基础上，我们提出了新的概率推理算法和新的广义推理问题，这些问题超越了目前图形模型中边缘图的研究。

Many important problems require control of multiple actuators, or agents, in parallel, to achieve a common coordinated goal in a stochastic environment. Examples of such problems include scheduling in a building with multiple elevators, managing a team for fire and rescue operations, managing the inventory of a large company, controlling a robotic soccer team, and controlling a robotic team to manage shelving and orders in a warehouse environment. These problems naturally fit into a formulation as discrete-time central-control problems where we design an algorithm that decides what action each agent takes at any time step in order to optimize the common objective. The corresponding computational problem, known as stochastic planning, is challenging due its sheer size. In particular, the number of possible states (for example, possible positions of robots, shelves and merchandise in a warehouse) and the number of possible joint actions (combinations of actions of individual robots) are huge in any problem instance of interest. State of the art approaches typically fail due to requiring too much time to properly search for a good policy or due to requiring too much memory to store intermediate values. By viewing stochastic planning through the lens of probabilistic inference, this project proposes several novel domain independent algorithmic approaches that take advantage of problem structure to calculate approximate solutions effectively under time constraints. The project funds are largely devoted to support training and research of PhD students therefore directly support human development in an important high impact area for the nation. More concretely, we propose three competing approaches to solving such problems, all taking insight from formulating the finite horizon control problem as probabilistic inference in a corresponding graphical model, also known as a dynamic Bayesian network. The first approach uses the idea of Monte Carlo search, but adds a strong symbolic component by introducing aggregate trajectories. Aggregate trajectories are obtained by simulating a compositional symbolic model under independence assumptions over the random variables. Each aggregate trajectory provides a value estimate that is approximate but can replace numerous individual trajectories. In this way we get fast approximation of values and effective control under time constraints. The second approach uses problem structure to translate the inference problem into an integer linear program, where the objective and quality of the solution can be traded-off for speed through problem decomposition. A novel construction shows how to sidestep the exponential complexity of the problem and obtain a sequence of integer programs that are both small and decomposable so as to yield effective control under time constraints. The third approach, or more accurately framework, builds on the tight connection between stochastic planning and probabilistic inference in the corresponding dynamic Bayesian network. We show that variants of the first two approaches can be viewed in this light, and through this we propose new inference algorithms for solving the stochastic planning problem. In addition, based on this analysis, we propose new algorithms for probabilistic inference, and new generalized inference questions that go beyond current research on marginal map in graphical models.