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

University Of Texas At Austin, Austin TX

Investigators

Abstract

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.