S&AS: FND: Long-Term Planning and Robust Plan Execution for Multi-Robot Systems

S

• 批准号: 1724392
• 负责人: Sven Koenig
• 金额: $ 60万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2023-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1724392&HistoricalAwards=false
• 关键词: S& FND; Long; Term; Planning

How can multi-robot teams maneuver in tight and cluttered environments when "no plan survives contact" with reality? Traditional approaches plan for idealized situations and must patch up maneuvers when sensors or actuators are imprecise, making them neither robust nor safe. This project, a collaboration of PIs from artificial intelligence and robotics, will investigate fundamental research to capture and use timing and uncertainty constraints in large robot navigation and coordination problems. The target applications are just-in-time manufacturing and automated warehousing, but the results will extend beyond to many applications of smart and autonomous systems that need reliable and safe planning. The project will study Multi-Agent Path Finding (MAPF), which is an NP-hard planning problem that belongs to a class of important planning problems, namely multi-agent navigation problems with temporal and spatial constraints. The research will relax simplifying assumptions typically made by MAPF solvers, namely that plan execution is perfect and stops once all robots have reached their goal locations. Many AI planning methods that have been developed are not used on robots, since planning/scheduling uses idealized models of the environment and plan execution is never perfect, and there is often insufficient time for re-planning if execution deviates from the plan. This project will develop well-founded planning and plan-execution methods, based on probabilistic and temporal reasoning, that fuse ideas from robotics and artificial intelligence. In particular, the PIs will combine advances in planning algorithms from the AI community, namely Simple Temporal Networks (STN), and adapt them to the robotics domain by adding timely execution constraints, as well as sensor, actuator, and model uncertainties. They will make project results (such as papers, videos and code) available on their web pages, present tutorials on their research results to the artificial intelligence and robotics research communities, develop teaching material for multi-robot planning, and integrate undergraduate students into their research activities.

多机器人团队如何在紧凑和混乱的环境中进行机动？传统的方法是为理想情况做计划，当传感器或执行器不精确时，必须修补机动，这使得它们既不健壮也不安全。该项目是人工智能和机器人技术pi的合作，将调查基础研究，以捕获和使用大型机器人导航和协调问题中的时间和不确定性约束。目标应用是即时制造和自动化仓储，但结果将扩展到需要可靠和安全规划的智能和自主系统的许多应用。该项目将研究Multi-Agent Path Finding (MAPF)，这是一个NP-hard规划问题，属于一类重要的规划问题，即具有时空约束的多智能体导航问题。该研究将简化MAPF求解器通常做出的假设，即计划执行是完美的，一旦所有机器人到达目标位置就会停止。许多已经开发的人工智能规划方法并没有用于机器人，因为规划/调度使用的是理想化的环境模型，计划的执行从来都不是完美的，如果执行偏离计划，通常没有足够的时间来重新规划。该项目将基于概率和时间推理，融合机器人和人工智能的思想，开发有充分根据的规划和计划执行方法。特别是，pi将结合人工智能社区在规划算法方面的进展，即简单时态网络（STN），并通过添加及时执行约束以及传感器、执行器和模型不确定性，使其适应机器人领域。他们将在自己的网页上发布项目成果（如论文、视频和代码），向人工智能和机器人研究社区提供有关其研究成果的教程，开发多机器人规划的教材，并将本科生纳入他们的研究活动。

项目成果

Summary: Distributed Task Assignment and Path Planning with Limited Communication for Robot Teams

摘要：机器人团队沟通有限的分布式任务分配和路径规划

• 发表时间: 2019
• 期刊: AAMAS '19: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems
• 作者: Albani, Dario;Hönig, Wolfgang;Ayanian, Nora;Nardi, Daniele;Trianni, Vito
• 通讯作者: Trianni, Vito

Toward a String-Pulling Approach to Path Smoothing on Grid Graphs

网格图路径平滑的拉弦方法

• 发表时间: 2020
• 期刊: Symposium on Combinatorial Search (SoCS
• 作者: Han, J.;Uras, T.;Koenig, S.
• 通讯作者: Koenig, S.

Overview: A Hierarchical Framework for Plan Generation and Execution in Multirobot Systems

• DOI: 10.1109/mis.2017.4531217
• 发表时间: 2017-11
• 期刊: IEEE Intelligent Systems
• 影响因子: 6.4
• 作者: Hang Ma;W. Hönig;L. Cohen;T. Uras;Hong Xu;T. K. S. Kumar;Nora Ayanian;Sven Koenig

Quadratic Reformulation of Nonlinear Pseudo-Boolean Functions via the Constraint Composite Graph

通过约束复合图对非线性伪布尔函数进行二次重构

• 发表时间: 2019
• 期刊: and Operations Research (CPAIOR
• 作者: Yip, K.;Xu, H.;Koenig, S.;Kumar, S.
• 通讯作者: Kumar, S.

Lifelong Multi-Agent Path Finding in Large-Scale Warehouses

• DOI: 10.1609/aaai.v35i13.17344
• 发表时间: 2020-05
• 作者: Jiaoyang Li;Andrew Tinka;Scott Kiesel;Joseph W. Durham;T. K. S. Kumar;Sven Koenig