NSF-BSF: AF: Small: Efficient Algorithms for Multi-Robot Multi-Criteria Optimal Motion Planning

今天，机器人技术被广泛认为是大规模制造中的灵活性和竞争力、提高工业效率和安全性以及更精确和有效的农业的关键组成部分，仅举几个政府、行业和学术界推动机器人技术的原因。机器人车队正迅速在物流中被采用，预计将在农业、检查和守卫以及最后一英里递送等其他领域变得司空见惯。尽管多机器人系统大量涌现，但机器人团队在高效运动规划方面的最新水平是相当有限的，当目标是优化运动计划时，更是有限的。即使对优化多机器人运动规划的贡献微乎其微，也可以在节约能源、降低成本、改善危急情况下的响应、提高生产率和竞争力方面产生巨大影响。该项目由美国国家科学基金会和美国-以色列两国科学基金会共同资助，旨在为平面连续域中的多机器人最优运动规划开发算法基础。这个项目的跨学科性质可能会吸引具有不同背景的研究生和本科生。这个项目产生的材料将通过多门课程、组织研讨会、开发课程材料、调查、教程和公开可用的开源软件来传播。这个项目通过调查三类不同的问题，加深了我们对各种多机器人运动规划问题计算复杂性的理解。首先，研究了在一个简单的目标函数下的最优运动规划问题，如所有机器人的路径总长度。其次，研究了在一个更复杂的目标函数下的最优运动规划，目标是对机器人的路径总长度和净空等多个目标进行优化。除了这些所谓的“一次性问题”，该项目还考虑了需要满足一系列永恒的运动规划请求的情况，即在舰队中的机器人已经在运动时出现新的请求，以满足其他运动规划请求。该项目的主要目的是开发快速、简单、健壮的近似算法，以实现最优运动规划。该项目结合了离散和计算几何、机器人学、近似算法、概率技术和变分的技术，以研究多机器人系统的最优运动规划。该项目超越了传统的最坏情况分析，了解在什么情况下最优运动规划问题在计算上是容易处理的。它还将探索降维技术，以规避在多机器人系统的标准分析中出现的维度诅咒。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Robotics is widely perceived today as a key component to flexibility and competitiveness in large-scale manufacturing, to enhanced industrial efficiency and safety, and to more precise and effective agriculture, to name just a few reasons why governments, industry, and academia promote robotics. Fleets of robots are being rapidly adopted in logistics, and are expected to become commonplace in other domains such as agriculture, inspection and guarding, and last-mile delivery. Notwithstanding the proliferation of multi-robot systems, the state-of-the-art in efficient motion-planning for teams of robots is rather limited, and is even more limited when one aims to optimize the motion plans. Even modest contributions to optimal multi-robot motion planning can have a tremendous impact in terms of saving energy, reducing costs, improving response in critical situations, increasing productivity and competitiveness. The goal of this project, jointly funded by NSF and US-Israel Binational Science Foundation, is to develop algorithmic foundations for optimal multi-robot motion-planning in a planar continuous domain. The interdisciplinary nature of this project is likely to appeal to a broad set of both graduate and undergraduate students with diverse backgrounds. The material generated from this project will be disseminated through multiple courses, organizing workshops, and developing course materials, surveys, tutorials, and publicly available open-source software.This project advances our understanding of the computational complexity of various multi-robot motion-planning problems by investigating three different classes of problems. First, it investigates optimal motion planning under a simple objective function such as the total length of paths traveled by all robots. Next, it studies optimal motion planning under a more complex objective function that aims to optimize multiple criteria such as the total length of paths and the clearance of the robots. In addition to these so-called "one-shot problems", the project also considers scenarios where a perpetual sequence of motion-planning requests need to be fulfilled, namely new requests appear while the robots in the fleet are already in motion, fulfilling other motion-planning requests. A major thrust of the project is on developing fast, simple, robust approximation algorithms for optimal motion planning. The project combines techniques from discrete and computational geometry, robotics, approximation algorithms, probabilistic techniques, and calculus of variation to investigate optimal motion planning for multi-robot systems. The project goes beyond the traditional worst-case-analysis to understand under what circumstances optimal motion-planning problems are computationally tractable. It will also explore dimension-reduction techniques to circumvent the curse of dimensionality, which arises in the standard analysis of multi-robot systems.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.