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

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

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.