EAGER: Microscopic Deployment Algorithms to Achieve Macroscopic Objectives for Spatially Distributed Stochastic Networks of Mobile Agents

这个早期概念探索性研究（EAGER）项目将研究控制大型移动代理网络以完成各种任务的新方法。该项目解决的第一个挑战是考虑每个代理的位置和速度的不确定性。这种不确定性可能是由于测量不准确或通信不完善造成的。为了捕获不确定性，该项目使用概率分布来量化所有代理的集体行为。这被称为网络的宏观描述。该项目解决的第二个挑战是，仅使用分布式算法和本地信息，找到实现所需网络宏观行为的控制律。也就是说，该项目将找到每个智能体控制其自身速度的规则，仅基于少数相邻智能体的知识，但以这种方式获得所需的宏观概率分布。个体主体的局部动态行为被称为网络的微观描述，本项目的目标是找到微观行为的规则，从而产生理想的宏观结果。一个例子是对一大群自主移动机器人的控制，这些机器人在广阔的地理区域内拾取和递送包裹。宏观目标是，对于区域内的每个点，可用的送货机器人的概率密度应该与需要取走包裹的概率密度相匹配。对于数量庞大的机器人，通过单个指挥中心控制每个机器人个体来实现这一宏观目标是不切实际的。相反，为了避免对通信带宽、信息存储和数据处理的过高要求，计算任务应该分配给各个机器人——然而，单个机器人只能与附近的几个单元共享数据。这个项目所面临的挑战是，单个机器人只能基于这种有限的本地交换来规划它们的运动，以这样一种方式，整个机器人网络以一种反映客户需求的模式分布在整个交付区域。该项目通过提高控制大型移动机器人网络的能力来促进国家繁荣，并有助于确保国防安全，这些移动机器人网络用于包裹递送等商业应用，或监视和拦截等安全应用。宏观部署问题分三步进行。第一步是定义一个虚拟的代理来捕获多代理网络的宏观状态。这是通过选择网络中所有组成主体的个体状态的均值和协方差作为决定代表性主体状态概率分布的统计量来实现的。然后应用随机最优控制理论的工具将网络引导到高度重要的区域。第二步是解决网络组成智能体的微观部署问题，根据不同的智能体完成任务的适合性，将任务分配给不同的智能体。提出的解决方案是基于分而治之的方案，该方案以一类特殊的Voronoi-like空间分区（多智能体网络工作空间的细分）为中心。这项工作的预期成果将包括：1)解决宏观控制问题的随机控制算法；2)计算网络工作空间的类voronoi细分的分区算法；3)利用类voronoi分区和Lloyd算法解决微观控制问题的分布式算法。第三步也是最后一步是通过一系列实验演示来验证所提出的算法，这些实验演示将在PI本部的机器人研究设施中进行。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This EArly-concept Grant for Exploratory Research (EAGER) project will study new ways to control large networks of mobile agents to accomplish a variety of tasks. The first challenge addressed by this project is to account for uncertainty in the position and velocity of each agent. This uncertainty can be caused by inaccurate measurements or imperfect communications. To capture uncertainty, this project uses probability distributions to quantify the collective behavior of all the agents. This is called the macroscopic description of the network. The second challenge addressed by this project is to find control laws that achieve a desired macroscopic behavior of the network, using only distributed algorithms and local information. That is, the project will find rules by which each agent will control its own velocity, based only on knowledge of a few neighboring agents, but in such a way that a desired macroscopic probability distribution is obtained. The local dynamic behavior of the individual agents is called the microscopic description of the network, and the goal of this project is to find rules for microscopic behavior that give rise to a desired macroscopic result. An example is the control of a large group of autonomous mobile robots that pick up and deliver packages across a wide geographic region. The macroscopic goal is that, for each point in the region, the probability density of a delivery robot being available should match the probability density that a package needs to be picked up. For large numbers of robots, it is impractical to achieve this macroscopic goal by controlling every individual robot from a single command center. Instead, to avoid prohibitive requirements for communication bandwidth, information storage, and data processing, the computational task should be distributed among the individual robots -- however, the individual robots can only share data with a few nearby units. The challenge addressed by this project is for the individual robots to plan their movements based only on this limited local exchange, in such a way that the entire network of robots spreads out across the delivery region in a pattern mirroring the customer demand. This project advances the national prosperity and helps to secure the national defense by improving the ability to control large networks of mobile robots for commercial applications such as package delivery, or security applications such as surveillance and interdiction.The macroscopic deployment problem is approached in three steps. The first step is to define a single fictitious agent that captures the macroscopic state of the multi-agent network. This is done by choosing the mean and the covariance of the individual states of all the constituent agents of the network to be the statistical quantities that determine the probability distribution of the state of the representative agent. Tools from stochastic optimal control theory are then applied to steer the network towards areas of high importance. The second step is to solve the microscopic deployment problem for the constituent agents of the network, by assigning tasks to different agents based on their suitability to accomplish these tasks. The proposed solution approach is based on a divide-and-conquer scheme that is centered around a special class of Voronoi-like spatial partitions (sub-divisions of the workspace of the multi-agent network). The expected outcomes of this effort will include 1) stochastic control algorithms for the solution of the macroscopic control problem, 2) partitioning algorithms for the computation of Voronoi-like subdivisions of the network's workspace, 3) distributed algorithms for the solution of the microscopic control problem that leverage the Voronoi-like partitions and Lloyd's algorithm. The third and final step is to validate the proposed algorithms via a set of experimental demonstrations that will take place at the facilities for robotics research at the PI's home department.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.