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

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

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.