Collaborative Research: A Comprehensive Dynamic Search Framework for Asynchronous Multi-Objective Multi-Agent Planning

协作研究：异步多目标多智能体规划的综合动态搜索框架

• 批准号: 2120529
• 负责人: Howard Choset
• 金额: $ 49.47万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-09-15 至 2024-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2120529&HistoricalAwards=false
• 关键词: Collaborative; Research; Comprehensive; Dynamic; Search

Natural disasters are causing significant economic and human losses more than ever. The increase in frequency and intensity of these wide-scale disasters places additional strains on rescue workers in their heroic struggle to save lives and mitigate the impacts on health and the economy. As such, rescue workers must make critical decisions at high tempo. In these scenarios, information is key, and obtaining such information, as quickly as possible, saves lives. Therefore, this project develops search methods that can direct multiple heterogeneous agents to efficiently search and acquire information. This multi-agent planning is not just a problem in Humanitarian Assistance Disaster Relief (HADR) missions, but also in customized manufacturing, critical infrastructure management, pandemic response, automated construction of field hospitals, and post-disaster forensics. Since lives are on the line, the approaches used must not only find feasible paths that maximize the likelihood of finding life, but also finds “best” possible solutions within a given response time. Therefore, this project seeks to create a comprehensive framework to address a wide family of multi-agent multi-objective planning problems operating under several logistic constraints.The intellectual merit of this project investigates how to couple, partially decouple, or completely decouple the coordinated planning of the agent's trajectories, and therefore defer planning until absolutely needed. As such, the work develops formal guarantees, either in terms of completeness and optimality properties, or approximation bounds, for the sub-optimal solutions obtained for various generalizations of the multi-agent problem. The performance of the approaches will be corroborated through large-scale simulations, and experiments on real robots. As part of the experimental process, this project will also define relevant metrics against which the new methods will be measured. This project will aim to substantiate that deferred planning, until necessary, offers computational, as well as path quality, and efficacy, benefits for several important generalizations of multi-agent path findingproblems.This project is supported by the cross-directorate Foundational Research in Robotics program, jointly managed and funded by the Directorates for Engineering (ENG) and Computer and Information Science and Engineering (CISE).This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

自然灾害造成的经济和人员损失比以往任何时候都更加严重。这些大规模灾难的频率和强度的增加给救援人员在拯救生命和减轻对健康和经济的影响的英勇斗争中带来了额外的压力。因此，救援人员必须快速做出关键决定。在这些情况下，信息是关键，尽快获取此类信息可以挽救生命。因此，该项目开发了可以指导多个异构代理高效搜索和获取信息的搜索方法。这种多智能体规划不仅是人道主义援助救灾 (HADR) 任务中的问题，也是定制制造、关键基础设施管理、流行病应对、野战医院自动化建设和灾后取证中的问题。由于生命攸关，所使用的方法不仅必须找到最大限度地提高发现生命可能性的可行路径，而且还要在给定的响应时间内找到“最佳”可能的解决方案。因此，该项目旨在创建一个综合框架来解决在多种逻辑约束下运行的一系列多智能体多目标规划问题。该项目的智力优点研究了如何耦合、部分解耦或完全解耦智能体轨迹的协调规划，从而将规划推迟到绝对需要时。因此，这项工作为针对多智能体问题的各种泛化获得的次优解提供了形式保证，无论是在完整性和最优性属性方面，还是在近似界限方面。这些方法的性能将通过大规模模拟和真实机器人实验得到证实。作为实验过程的一部分，该项目还将定义衡量新方法的相关指标。该项目旨在证实，在必要时推迟规划可以为多智能体寻路问题的几个重要概括提供计算、路径质量和效率方面的好处。该项目得到了机器人学跨部门基础研究计划的支持，该计划由工程理事会 (ENG) 和计算机与信息科学与工程理事会 (CISE) 共同管理和资助。该奖项反映了 NSF 的法定使命，并已 通过使用基金会的智力优点和更广泛的影响审查标准进行评估，认为值得支持。

项目成果

Enhanced multi-objective A* using balanced binary search trees

使用平衡二叉搜索树增强多目标 A*

• 发表时间: 2022
• 期刊: Proceedings of the International Symposium on Combinatorial Search
• 作者: Ren, Zhongqiang;Zhan, Richard;Sivakumar, Rathinam;Likhachev, Maxim;Choset, Howie
• 通讯作者: Choset, Howie

Conflict-Based Steiner Search for Multi-Agent Combinatorial Path Finding

基于冲突的斯坦纳搜索多智能体组合路径查找

• DOI: 10.15607/rss.2022.xviii.058
• 发表时间: 2022
• 期刊: Robotics: Science and Systems XVIII
• 作者: Z. Ren;S. Rathinam;H. Choset
• 通讯作者: H. Choset

A Lower Bounding Framework for Motion Planning amid Dynamic Obstacles in 2D.

二维动态障碍中运动规划的下限框架。

• 发表时间: 2022
• 期刊: International Workshop on the Algorithmic Foundations of Robotics
• 作者: Ren, Zhongqiang;Rathinam, Sivakumar;Choset, Howie
• 通讯作者: Choset, Howie

Search Algorithms for Multi-Agent Teamwise Cooperative Path Finding

多智能体团队合作寻路的搜索算法

• DOI: 10.1109/icra48891.2023.10160864
• 发表时间: 2023
• 期刊: IEEE
• 作者: Ren, Zhongqiang;Zhang, Chaoran;Rathinam, Sivakumar;Choset, Howie
• 通讯作者: Choset, Howie

Binary Branching Multi-Objective Conflict-Based Search for Multi-Agent Path Finding

用于多智能体路径查找的二元分支多目标冲突搜索

• 发表时间: 2023
• 期刊: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS
• 作者: Ren, Z.;Li, J.;Zhang, H.;Koenig, S.;Rathinam, S.;Choset, H.
• 通讯作者: Choset, H.