RI: Small: Stochastic Planning and Probabilistic Inference for Factored State and Action Spaces
RI:小:因子状态和行动空间的随机规划和概率推理
基本信息
- 批准号:1616280
- 负责人:
- 金额:$ 44.71万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2016
- 资助国家:美国
- 起止时间:2016-06-01 至 2020-01-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
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.
许多重要的问题需要控制多个执行器,或代理,并行,以实现一个共同的协调目标,在随机环境中。这样的问题的例子包括在具有多个电梯的建筑物中的调度、管理用于消防和救援操作的团队、管理大公司的库存、控制机器人足球队以及控制机器人团队来管理仓库环境中的货架和订单。这些问题自然适合作为离散时间中央控制问题的公式,我们设计了一个算法,决定每个代理在任何时间步采取什么行动,以优化共同的目标。相应的计算问题,称为随机规划,是具有挑战性的,由于其庞大的规模。特别是,在任何感兴趣的问题实例中,可能的状态(例如,仓库中机器人、货架和商品的可能位置)和可能的联合动作(单个机器人的动作组合)的数量都是巨大的。现有技术的方法通常由于需要太多的时间来正确地搜索好的策略或者由于需要太多的存储器来存储中间值而失败。透过机率推论的透镜观察随机规划,本计画提出几种新颖的领域独立演算法,利用问题结构在时间限制下有效地计算近似解。项目资金主要用于支持博士生的培训和研究,因此直接支持国家重要的高影响力领域的人类发展。更具体地说,我们提出了三种相互竞争的方法来解决这些问题,所有这些方法都是从将有限时域控制问题制定为相应图形模型(也称为动态贝叶斯网络)中的概率推理中获得的。第一种方法使用蒙特卡罗搜索的思想,但通过引入聚合轨迹增加了一个强大的符号组件。聚集轨迹是通过模拟一个组成的符号模型下的独立性假设的随机变量。每个聚合轨迹提供近似的值估计,但可以替代许多单独的轨迹。通过这种方法,我们得到了快速的近似值和有效的控制下的时间约束。第二种方法使用问题结构将推理问题转化为整数线性规划,其中通过问题分解可以权衡解决方案的目标和质量以获得速度。一个新的建设表明如何回避的指数复杂性的问题,并获得一个序列的整数规划,都是小的和可分解的,以便产生有效的控制下的时间限制。第三种方法,或更准确地说,框架,建立在相应的动态贝叶斯网络的随机规划和概率推理之间的紧密联系。我们表明,前两种方法的变体可以从这个角度来看,并通过这一点,我们提出了新的推理算法来解决随机规划问题。此外,基于这种分析,我们提出了新的概率推理算法,和新的广义推理问题,超越了目前的边缘图在图形模型的研究。
项目成果
期刊论文数量(4)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Sampling Networks and Aggregate Simulation for Online POMDP Planning
在线 POMDP 规划的采样网络和聚合模拟
- DOI:
- 发表时间:2019
- 期刊:
- 影响因子:0
- 作者:Cui, H;Khardon, R.
- 通讯作者:Khardon, R.
From Stochastic Planning to Marginal MAP
从随机规划到边际 MAP
- DOI:
- 发表时间:2018
- 期刊:
- 影响因子:0
- 作者:Cui, H;Marinescu, R;Khardon, R.
- 通讯作者:Khardon, R.
Stochastic Planning and Lifted Inference
随机规划和提升推理
- DOI:
- 发表时间:2021
- 期刊:
- 影响因子:0
- 作者:R. Khardon;S. Sanner
- 通讯作者:S. Sanner
Stochastic Planning with Lifted Symbolic Trajectory Optimization
- DOI:10.1609/icaps.v29i1.3467
- 发表时间:2019-07
- 期刊:
- 影响因子:0
- 作者:Hao Cui;Thomas Keller;R. Khardon
- 通讯作者:Hao Cui;Thomas Keller;R. Khardon
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Roni Khardon其他文献
Explainable models via compression of tree ensembles
- DOI:
10.1007/s10994-023-06463-1 - 发表时间:
2023-11-29 - 期刊:
- 影响因子:2.900
- 作者:
Siwen Yan;Sriraam Natarajan;Saket Joshi;Roni Khardon;Prasad Tadepalli - 通讯作者:
Prasad Tadepalli
Complexity parameters for first order classes
- DOI:
10.1007/s10994-006-8261-3 - 发表时间:
2006-05-08 - 期刊:
- 影响因子:2.900
- 作者:
Marta Arias;Roni Khardon - 通讯作者:
Roni Khardon
Roni Khardon的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Roni Khardon', 18)}}的其他基金
RI: Small: Approximate Inference for Planning and Reinforcement Learning
RI:小:规划和强化学习的近似推理
- 批准号:
2246261 - 财政年份:2023
- 资助金额:
$ 44.71万 - 项目类别:
Standard Grant
RI: Small: Stochastic Planning and Probabilistic Inference for Factored State and Action Spaces
RI:小:因子状态和行动空间的随机规划和概率推理
- 批准号:
2002393 - 财政年份:2019
- 资助金额:
$ 44.71万 - 项目类别:
Standard Grant
III: Small: Algorithms and Theoretical Foundations for Approximate Bayesian Inference in Machine Learning
III:小:机器学习中近似贝叶斯推理的算法和理论基础
- 批准号:
1906694 - 财政年份:2018
- 资助金额:
$ 44.71万 - 项目类别:
Continuing Grant
III: Small: Algorithms and Theoretical Foundations for Approximate Bayesian Inference in Machine Learning
III:小:机器学习中近似贝叶斯推理的算法和理论基础
- 批准号:
1714440 - 财政年份:2017
- 资助金额:
$ 44.71万 - 项目类别:
Continuing Grant
RI: Medium: Collaborative Research: Optimizing Policies for Service Organizations in Complex Structured Domains
RI:中:协作研究:优化复杂结构领域服务组织的政策
- 批准号:
0964457 - 财政年份:2010
- 资助金额:
$ 44.71万 - 项目类别:
Continuing Grant
EAGER: First Order Decision Diagrams for Relational Markov Decision Processes
EAGER:关系马尔可夫决策过程的一阶决策图
- 批准号:
0936687 - 财政年份:2009
- 资助金额:
$ 44.71万 - 项目类别:
Standard Grant
Learning and Reasoning with Relational Structures
利用关系结构进行学习和推理
- 批准号:
0099446 - 财政年份:2001
- 资助金额:
$ 44.71万 - 项目类别:
Continuing Grant
相似国自然基金
昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
- 批准号:
- 批准年份:2024
- 资助金额:0.0 万元
- 项目类别:省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
- 批准号:n/a
- 批准年份:2022
- 资助金额:10.0 万元
- 项目类别:省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
- 批准号:32000033
- 批准年份:2020
- 资助金额:24.0 万元
- 项目类别:青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
- 批准号:31972324
- 批准年份:2019
- 资助金额:58.0 万元
- 项目类别:面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
- 批准号:81900988
- 批准年份:2019
- 资助金额:21.0 万元
- 项目类别:青年科学基金项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
- 批准号:31802058
- 批准年份:2018
- 资助金额:26.0 万元
- 项目类别:青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
- 批准号:31870821
- 批准年份:2018
- 资助金额:56.0 万元
- 项目类别:面上项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
- 批准号:31772128
- 批准年份:2017
- 资助金额:60.0 万元
- 项目类别:面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
- 批准号:81704176
- 批准年份:2017
- 资助金额:20.0 万元
- 项目类别:青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
- 批准号:91640114
- 批准年份:2016
- 资助金额:85.0 万元
- 项目类别:重大研究计划
相似海外基金
NSF-BSF: CNS Core: Small: Reliable and Zero-Power Timekeepers for Intermittently Powered Computing Devices via Stochastic Magnetic Tunnel Junctions
NSF-BSF:CNS 核心:小型:通过随机磁隧道结为间歇供电计算设备提供可靠且零功耗的计时器
- 批准号:
2400463 - 财政年份:2023
- 资助金额:
$ 44.71万 - 项目类别:
Standard Grant
CIF: Small: Accelerating Stochastic Approximation for Optimization and Reinforcement Learning
CIF:小型:加速优化和强化学习的随机逼近
- 批准号:
2306023 - 财政年份:2023
- 资助金额:
$ 44.71万 - 项目类别:
Standard Grant
NSF-BSF: AF: Small: Parameter-Free Stochastic Optimization via Trajectory Cues
NSF-BSF:AF:小:通过轨迹线索进行无参数随机优化
- 批准号:
2239527 - 财政年份:2023
- 资助金额:
$ 44.71万 - 项目类别:
Standard Grant
Collaborative Research: CIF: Small: Nonasymptotic Analysis for Stochastic Networks and Systems: Foundations and Applications
合作研究:CIF:小型:随机网络和系统的非渐近分析:基础和应用
- 批准号:
2207547 - 财政年份:2022
- 资助金额:
$ 44.71万 - 项目类别:
Standard Grant
Collaborative Research: CIF: Small: Nonasymptotic Analysis for Stochastic Networks and Systems: Foundations and Applications
合作研究:CIF:小型:随机网络和系统的非渐近分析:基础和应用
- 批准号:
2207548 - 财政年份:2022
- 资助金额:
$ 44.71万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: A Unified Framework for Analyzing Adaptive Stochastic Optimization Methods Based on Probabilistic Oracles
合作研究:AF:Small:基于概率预言的自适应随机优化方法分析统一框架
- 批准号:
2139735 - 财政年份:2022
- 资助金额:
$ 44.71万 - 项目类别:
Standard Grant
Collaborative Research: AF: Small: A Unified Framework for Analyzing Adaptive Stochastic Optimization Methods Based on Probabilistic Oracles
合作研究:AF:Small:基于概率预言的自适应随机优化方法分析统一框架
- 批准号:
2140057 - 财政年份:2022
- 资助金额:
$ 44.71万 - 项目类别:
Standard Grant
CISE-ANR: FET: Small: Hybrid Stochastic Tunnel Junction Circuits for Optimization and Inference
CISE-ANR:FET:小型:用于优化和推理的混合随机隧道结电路
- 批准号:
2121957 - 财政年份:2021
- 资助金额:
$ 44.71万 - 项目类别:
Standard Grant
III: Small: Stochastic Algorithms for Large Scale Data Analysis
III:小型:大规模数据分析的随机算法
- 批准号:
2131335 - 财政年份:2021
- 资助金额:
$ 44.71万 - 项目类别:
Continuing Grant
NSF-BSF: CNS Core: Small: Reliable and Zero-Power Timekeepers for Intermittently Powered Computing Devices via Stochastic Magnetic Tunnel Junctions
NSF-BSF:CNS 核心:小型:通过随机磁隧道结为间歇供电计算设备提供可靠且零功耗的计时器
- 批准号:
2106562 - 财政年份:2021
- 资助金额:
$ 44.71万 - 项目类别:
Standard Grant