Multi-agent distributed coverage control and multi-target tracking in complex and dynamic environments




Abdulghafoor, Alaa Zaki Abdulrahman

Journal Title

Journal ISSN

Volume Title



In this work, we study and investigate problems associated with decentralized/distributed area coverage control and deployment of multi-agent networks as well as density estimation, path planning and motion coordination of the latter networks for multi-target tracking in dynamic and complex environments. In particular, we consider deployment (which includes target tracking applications) and area coverage problems in which the members of the multi-agent network have to deploy and allocate themselves over a given domain in accordance with a time-varying Gaussian mixture reference density function (demand function for the network) in complex and non-complex environments (domains with or without obstacles (which can be either static or dynamic)). The latter density function can either represent the reference coverage density or the reference tracking density according to the application considered in each scenario. Hence, different scenarios of the latter problems are investigated in which the proposed problem is comprised of two sub-problems which are coupled and interconnected with each other. The first problem (high-level/macroscopic problem) corresponds to a density path planning and / or density estimation (implemented in a centralized manner) whereas the second problem (low-level/microscopic problem) to a decentralized and distributed control and motion coordination problem. Our proposed approach is based on a combination of the macroscopic and microscopic descriptions of the multi-agent network. The macroscopic description of the network corresponds to the probability distribution of the agents' locations over a given region. In this description, the multi-agent network is treated as one unit (characterized by the networks PDF). The microscopic description of the network corresponds to the collection of all individual positions of the network's agents. The objective of our work is to find control algorithms that will allow a multi-agent network to attain a spatial distribution that matches the reference density function (macroscopic high-level problem) through the local interactions of the agents at the individual level (microscopic low-level distributed control problem). The high-level problem is associated with an interpolation problem in the class of Gaussian Mixtures (GMs) which seeks to find a density path that connects two boundary GMs. Moreover, the low-level control problem is addressed by utilizing the Lloyd's algorithm together with Voronoi tessellations and a time-varying GM reference density function which corresponds to the solution of the high-level problem. Because the high-level and the low-level problems of all the considered scenarios are inherently coupled to each other (interconnected in the sense that in order to solve the second problem we require the solution of the first problem), we propose an iterative scheme that combines the solutions of the first and the second problems in order to solve and address the path planning/density estimation, motion coordination, deployment and area coverage control problems of multi-agent networks in dynamic and complex environments in a successful, complete, safe and holistic way. In the first scenario (Scenario 1 presented in Chapter 2), the goal of the multi-agent network is to track the time-varying GM reference coverage density function that reshapes the agents' distribution from an initial single Gaussian probability distribution to a Gaussian mixture distribution in a domain with no obstacles (non-complex environment). In the second scenario (Scenario 2 presented in Chapter 3) the aim is to transfer the distribution of the agents from an initial GM to a final desired GM over a cluttered complex domain populated by static obstacles that the agents must not collide with while at all times as they are moving and trying to track the time-varying GM reference coverage density. In Scenarios 1 and 2, the high-level problem (first problem) was solved analytically by providing a closed form solution. The low-level control problem (second problem) corresponds to a decentralized and distributed control problem (collision avoidance requirement is now enforced at all times) which is solved by utilizing Lloyd's algorithm together with Voronoi tessellations and a time-varying GM reference coverage density function which corresponds to the centralized solution of the high-level coverage control problem (first problem). For Scenario 2, our approach utilizes a modified version of Voronoi tessellations which are comprised of what we refer to as Obstacle-Aware Voronoi Cells (OAVC) in order to enable coverage control while ensuring obstacle avoidance. In contrast with the first two scenarios (Scenarios 1 and 2), the next scenarios to be discussed (Scenarios 3 and 4) the time-varying GM reference densities are not known a priori and will correspond to the reference tracking density of a multi-target system which is characterized as a GM tracking density utilized to steer the agents to follow the targets; thus, in the first problems of the latter scenarios, state-of the-art estimation techniques will be employed to obtain their solutions. In the third scenario (Scenario 3 presented in Chapter 4) we address a multi-target tracking problem for a multi-agent network. Thus, we consider a density estimation, path planning and distributed/decentralized motion coordination problem for a multi-agent network whose members have to track multiple moving targets over a cluttered complex environment with static obstacles. In the first problem, which corresponds to a density estimation and path planning problem, the goal is to obtain a GM reference tracking density path of the multi-target network that the multi-agent system must track as a whole. In the proposed solution approach of the latter problem, the probability density of the multi-target system is characterized by a Gaussian mixture distribution density which is estimated by an adaptive Gaussian sum filter (AGSF) in order incorporate the complete evolution of the targets' PDFs between two measurements during the estimation. Therefore, the weights (mixing proportions) of the Gaussian components/ mixands (which correspond to the individual target's PDF) update continuously at every time step during the propagation of the state PDFs between two measurements by solving a convex optimization problem which requires the GM approximation to satisfy the so called Fokker-Planck-Kolmogorov equation (FPKE) for continuous time dynamical systems. In the second problem, which corresponds to a distributed and decentralized motion coordination problem, we seeks to find the individual control inputs that steer the agents to follow and track the mobile targets (by tracking the GM reference tacking density estimated solution of the first problem) while avoiding collisions at all times. Hence the same solution approach utilized for Scenario 2 will be employed to solve the second problem of Scenario 3. In the Fourth scenario (Scenario 4 presented in Chapter 5) we address an optimal path planning, density estimation and motion coordination problem for a very-large-scale multi-agent network whose members are aimed to track a very-large-scale system of mobile targets that maneuver while avoiding dynamic moving obstacles in an uncertain changing environment. The goal of the multi-agent network is to follow the targets by tracking their optimal reference estimated probability density which is represented as a GM distribution while avoiding collision with all the dynamic obstacles over the uncertain region. The estimated reference density is optimal in the sense that it represents the GM density of the targets as they seek the shortest path to reach their final destinations in the shortest time while avoiding the dynamic obstacles in the uncertain domain. The first problem corresponds to the optimal path planning and density estimation of the VLST system in the uncertain dynamic environment while the second problem is the motion coordination problem of the very-large-scale multi-agent network. Therefore, the solution approach to tackle the first problem depends on the utilization of an adaptive distributed optimal control (ADOC) framework which is in turn based on tools and concepts from optimal mass transport theory as well as reinforcement learning and approximate dynamic programming (and optimization) in the Wasserstein-GMM space where the value functional is defined in terms of the PDF (corresponds to a GM density) of the targets and the time-varying obstacle map function which describes the dynamic uncertain environment. The key challenge in the latter approach, is estimating and the continuously updating the PDF of the VLST system in accordance with the real time/"online" approximation of the time-varying obstacle map which describe the dynamic obstacles and the uncertain changing environmental information which affect the estimation of latter PDF. The second problem of Scenario 4 will be addressed similarly to that of Scenarios 2 and 3.


LCSH Subject Headings