CAREER: Decentralized Constraint-Based Optimization for Multi-Agent Planning and Coordination

职业：用于多智能体规划和协调的分散式基于约束的优化

基本信息

批准号：
1838364
负责人：
William Yeoh
金额：
$ 29.37万
依托单位：
Washington University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-09-01 至 2023-02-28
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1838364&HistoricalAwards=false
关键词：
CAREER Decentralized Constraint Based Optimization

项目摘要

There is a growing need for optimization methods to support decentralized decision-making in complex multi-agent systems including target tracking in sensor networks, mission planning of unmanned autonomous vehicles, coordination of rescue robots in disaster scenarios, and scheduling of intelligent devices in smart homes within smart grids. This class of problems is particularly challenging to solve due to a combination of the following requirements: There is a high degree of uncertainty that must be taken into account during planning; the planning process must be done in a decentralized fashion; and the resulting plan must be executed in a decentralized way as well. The objective of this project is to respond to the crucial challenge of developing an integrated approach that captures all these requirements within a single framework in order to improve the scope and applicability of multi-agent techniques in real-world applications. The long-term broader impacts of this project include the potential for the research findings to improve decentralized decision-making in real-world problems. In the short term, high-school students will benefit from the education modules developed by the PI, which will be disseminated through collaborations with local outreach programs as well as local teachers and summer camp organizers. The students will develop better computational thinking skills and be exposed to computational concepts applied to relevant applications of interest. The significance of these efforts is made more crucial by the fact that a majority of the student body at local high-schools as well as at NMSU is Hispanic. This project will make the necessary foundational contributions to the field of multi-agent systems to improve the scope and applicability of such systems, especially those that utilize automated planning and constraint optimization techniques, in the real world. More specifically, this project will result in (i) novel ways to more accurately model a large class of multi-agent planning problems using decentralized constraint-based models; (ii) new scalable algorithms with theoretical guarantees suitable for solving large-scale decentralized planning problems; and (iii) effective ways of improving computational thinking in high-school students via the use of constraint-based representations.

人们越来越需要优化方法来支持复杂多智能体系统中的分散决策，包括传感器网络中的目标跟踪、无人驾驶车辆的任务规划、灾难场景中救援机器人的协调以及智能家居中智能设备的调度在智能电网内。由于以下要求的结合，此类问题的解决特别具有挑战性：在规划过程中必须考虑高度的不确定性；规划过程必须以分散的方式进行；由此产生的计划也必须以分散的方式执行。该项目的目标是应对开发一种集成方法的关键挑战，该方法在单个框架内捕获所有这些需求，以提高多代理技术在实际应用中的范围和适用性。该项目的长期更广泛影响包括研究结果有可能改善现实世界问题的分散决策。短期内，高中生将受益于 PI 开发的教育模块，这些模块将通过与当地外展项目以及当地教师和夏令营组织者的合作进行传播。学生将培养更好的计算思维技能，并接触到应用于感兴趣的相关应用的计算概念。由于当地高中和新墨西哥州立大学的大多数学生都是西班牙裔，因此这些努力的意义变得更加重要。该项目将为多智能体系统领域做出必要的基础性贡献，以提高此类系统的范围和适用性，特别是那些在现实世界中利用自动规划和约束优化技术的系统。更具体地说，该项目将产生（i）使用分散的基于约束的模型更准确地对一大类多智能体规划问题进行建模的新方法； (ii) 新的可扩展算法，具有适合解决大规模分散规划问题的理论保证； (iii) 通过使用基于约束的表示来提高高中生计算思维的有效方法。

项目成果

期刊论文数量（4）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Embedding Preference Elicitation Within the Search for DCOP Solutions

在 DCOP 解决方案的搜索中嵌入偏好诱导

DOI：
发表时间：
2020
期刊：
Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS
影响因子：
0
作者：
Xiao, Yuanming;Tabakhi, Atena M;Yeoh, William
通讯作者：
Yeoh, William

Incomplete Distributed Constraint Optimization Problems: Model, Algorithms, and Heuristics

不完全分布式约束优化问题：模型、算法和启发式

DOI：
10.1007/978-3-030-94662-3_5
发表时间：
2021
期刊：
Proceedings of the International Conference on Distributed Artificial Intelligence (DAI
影响因子：
0
作者：
Tabakhi, Atena M.;Yeoh, William;Zivan, Roie
通讯作者：
Zivan, Roie

A Simple and Fast Bi-Objective Search Algorithm

一种简单快速的双目标搜索算法

DOI：
发表时间：
2020
期刊：
Proceedings of the International Conference on Automated Planning and Scheduling
影响因子：
0
作者：
Hernandez, C.;Yeoh, W.;Baier, J.;Zhang, H.;Suazo, L.;Koenig, S.
通讯作者：
Koenig, S.

Branch-and-Bound Heuristics for Incomplete DCOPs

不完整 DCOP 的分支定界启发法

DOI：
发表时间：
2021
期刊：
Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS
影响因子：
0
作者：
Tabakhi, Atena M;Xiao, Yuanming;Yeoh, William;Zivan, Roie
通讯作者：
Zivan, Roie