AF: Small: RUI: Competitive Search, Evacuation and Reconfiguration with Coordinated Mobile Agents

AF：小型：RUI：通过协调移动代理进行竞争性搜索、疏散和重新配置

• 批准号: 1813940
• 负责人: Sunil Shende
• 金额: $ 23.75万
• 依托单位: Rutgers University Camden
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-06-01 至 2022-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1813940&HistoricalAwards=false
• 关键词: AF; Small; RUI; Competitive; Search

In recent years, innovations in special-purpose sensor hardware and machine-learning algorithms have led to rapid advances in robotics and autonomous vehicle technology. This project aims to develop and analyze algorithms for an ensemble of mobile agents working in parallel to achieve coordinated, goal-directed motion in simple geometric spaces that are abstractions of complex terrains. The agents cooperate among themselves to efficiently search, explore, synchronize and reconfigure into patterns using distributed algorithms with limited memory, sensing and communication capabilities. The research will contribute to a deeper understanding of coordination protocols to complete navigational tasks, even when some of the agents may be faulty. Results from the research will provide critical insights that can be used in robot-assisted applications such as search-and-rescue in hostile or unknown terrains, or surface exploration needed to develop and maintain future colonies and human outposts on other planets. The study of reconfiguration problems will also provide ideas that can shed light on previously unexplained aspects of flocking phenomena in birds, such as murmurations. The project will involve undergraduate students in theoretical research and will train them to develop and maintain an open-source repository of distributed algorithms for robot coordination problems and their animations. In addition, results from the project will be archived as a permanent online resource for the parallel and distributed computing community at large. Two specific annual initiatives for outreach will be a part of the project: firstly, participation by the investigator and undergraduate research students in the Rutgers Future Scholars program, and secondly, conducting workshops for K-12 teachers to teach basic computational and algorithm design skills.The project addresses fundamental theoretical problems of efficient, coordinated exploration and reconfiguration by a team of mobile agents as they work together to accomplish a computational task in simple geometric spaces. Three basic problem settings are considered: (a) the search problem, where an unknown target location, which can only be sensed when reached, has to be found by at least one robot in the team, (b) the evacuation problem, that requires some subset of the robots to reach an unknown exit location in the region after it has been found, and (c) the reconfiguration problem, where the robots must rearrange themselves in a certain desired configuration based on either a given arrangement or on local rules. Within each problem setting, the goal is to develop an algorithm for the robots so that they can attain the desired configuration or complete the task defined by the problem with the minimum amount of resource usage possible, e.g. total distance traveled or time taken. Many interesting variants of the problems will also be studied, such as the peculiarities of the region's geometry, constraints on the communication capabilities of the robots, and handling faulty robots that may be benign or malicious.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.

近年来，专用传感器硬件和机器学习算法的创新推动了机器人和自动驾驶汽车技术的快速发展。该项目旨在开发和分析并行工作的移动的代理的合奏算法，以实现协调，目标导向的运动在简单的几何空间是复杂地形的抽象。代理之间的合作，有效地搜索，探索，同步和重新配置成模式，使用分布式算法与有限的内存，传感和通信能力。这项研究将有助于更深入地了解协调协议，以完成导航任务，即使一些代理可能有故障。研究结果将提供关键的见解，可用于机器人辅助应用，如在敌对或未知地形中的搜索和救援，或开发和维护其他行星上的未来殖民地和人类前哨所需的表面探索。重构问题的研究也将提供一些思路，可以阐明以前无法解释的鸟类群集现象，如杂音。该项目将让本科生参与理论研究，并培训他们开发和维护一个开放源代码的分布式算法库，用于机器人协调问题及其动画。此外，该项目的成果将作为并行和分布式计算界的永久在线资源存档。两项具体的年度外联举措将是该项目的一部分：首先，研究者和本科研究生参与罗格斯大学未来学者计划，其次，为K-12教师举办讲习班，教授基本的计算和算法设计技能。该项目解决了效率，当一组移动的代理一起工作以在简单几何空间中完成计算任务时，由它们进行协调的探索和重新配置。 考虑三个基本问题设置：（a）搜索问题，其中只有在到达时才能感测到的未知目标位置必须由团队中的至少一个机器人找到，（B）疏散问题，其要求机器人的某个子集在已经找到该区域中的未知出口位置之后到达该未知出口位置，以及（c）重新配置问题，其中机器人必须基于给定的布置或基于局部规则将其自身重新布置成特定的期望配置。在每个问题设置中，目标是为机器人开发一种算法，以便它们能够以最小的资源使用量（例如总行驶距离或所需时间）获得所需的配置或完成问题定义的任务。此外，还将研究该地区的几何形状的特殊性、机器人通信能力的限制、良性或恶意的故障机器人的处理等问题的许多有趣的变体。该奖项反映了NSF的法定使命，通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Time-energy tradeoffs for evacuation by two robots in the wireless model

无线模型中两个机器人疏散的时间与能量权衡

• DOI: 10.1016/j.tcs.2020.11.014
• 发表时间: 2021
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Czyzowicz, Jurek;Georgiou, Konstantinos;Killick, Ryan;Kranakis, Evangelos;Krizanc, Danny;Lafond, Manuel;Narayanan, Lata;Opatrny, Jaroslav;Shende, Sunil
• 通讯作者: Shende, Sunil

Priority evacuation from a disk: The case of n ≥ 4

优先从磁盘疏散：n-4的情况

• DOI: 10.1016/j.tcs.2020.09.023
• 发表时间: 2020
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Czyzowicz, J.;Georgiou, K.;Killick, R.;Kranakis, E.;Krizanc, D.;Narayanan, L.;Opatrny, J.;Shende, S.
• 通讯作者: Shende, S.

God Save the Queen

上帝保佑女王

• 发表时间: 2018
• 期刊: 9th International Conference on Fun with Algorithms
• 作者: Czyzowicz, J;Georgiou, K;Killick, R;Kranakis, E;Krizanc, D;Narayanan, L;Opatrny, J;Shende, S.
• 通讯作者: Shende, S.

Search on a Line by Byzantine Robots

拜占庭机器人在线搜索

• DOI: 10.1142/s0129054121500209
• 发表时间: 2021
• 期刊: International Journal of Foundations of Computer Science
• 影响因子: 0.8
• 作者: Czyzowicz, Jurek;Georgiou, Konstantinos;Kranakis, Evangelos;Krizanc, Danny;Narayanan, Lata;Opatrny, Jaroslav;Shende, Sunil
• 通讯作者: Shende, Sunil

Graph Exploration by Energy-Sharing Mobile Agents

能量共享移动代理的图探索

• 发表时间: 2021
• 期刊: 28th International Colloquium on Structural Information and Communication Complexity (SIROCCO
• 作者: Czyzowicz, J.;Dobrev, S.;Killick, R.;Kranakis, E.;Krizanc, D.;Narayanan, L.;Opatrny, J;Pankratov, D.;Shende, S.
• 通讯作者: Shende, S.