权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

NSF-BSF：AF：小型：多机器人多标准最佳运动规划的高效算法

基本信息

批准号：
2007556
负责人：
Pankaj Agarwal
金额：
$ 44.98万
依托单位：
Duke University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-07-15 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2007556&HistoricalAwards=false
关键词：
NSF BSF AF Small Efficient

项目摘要

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.

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