Date of Award

1-24-2024

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Electrical Engineering and Computer Science

Advisor(s)

Qinru Qiu

Second Advisor

Carlos Enrique Caicedo Bastidas

Keywords

Density Prediction;Multi-agent System;Reinforcement Learning;Task Allocation

Subject Categories

Computer Engineering | Engineering

Abstract

In recent years, the field of Multi-Agent Systems (MAS) has garnered increasing attention. The essence of Multi-Agent Systems lies in orchestrating the coordination and collaboration of autonomous agents, endowing them with the ability to work collectively towards common goals. This characteristic makes MAS particularly germane in addressing the challenges posed by complex and dynamic environments, where theadaptability and decentralized decision-making of autonomous agents prove advantageous. To delve into the intricacies of MAS, three primary research directions have emerged. Firstly, we aim to develop a model rapidly and accurately to forecast future Unmanned Aerial Systems (UAS) traffic density patterns while simultaneously simplifying model complexity. The second direction involves the study of real-time task allocation and trajectory planning algorithms, considering constraints imposed by the capabilities of individual agents. The third direction focuses on investigating multi-agent cooperative game using Multi-Agent Reinforcement Learning (MARL). The success of the deep learning-based approach spans various domains, notably in areas such as density and trajectory prediction. In our earlier work, we introduced an innovative trajectory prediction model, which forecasts instantaneous traffic density using mission schedule information. However, one of the main drawbacks of the Deep Neural Network (DNN) is the high computational cost, which prevents us from applying the model to search for the best mission plan or best locations of launching and landing zones, because it requires exponentially large numbers of predictions based on different input combinations. To reduce the complexity of the Convolutional Neural Network (CNN) model, we developed a Neural Architecture Search (NAS) optimization framework. This framework systematically identifies the optimal compression ratio for each layer, resulting in a streamlined neural architecture. As a result, we achieved a 50% reduction in the size of the instantaneous traffic density prediction model. Multi-agent task allocation challenges can be accomplished through the application of the Consensus-Based Bundle Algorithm (CBBA). The distributed algorithm exhibits provable convergence and ensures 50% optimality when the score function adheres to the conditions of Diminishing Marginal Gain (DMG). While prior research has primarily focused on the unconstrained optimization of rewards, our work addresses the challenges posed by real-world dynamic environments by incorporating specific constraints. These constraints encompass considerations such as limitations on agent capabilities, communication restrictions, and budget constraints. Our work is to applying CBBA for task allocation while considering budget constraints using various heuristics extensions to the bidding algorithm. In determining the most suitable heuristic extension, we introduce a Graph Convolutional Neural Network (GCN) model to extract and analyze features of constrained optimization problems presented as graphs, predicting the potential performance (i.e., global reward) of different heuristic extensions. Experimental results affirm a correlation exceeding 0.98 between predicted and actual rewards. The prediction-guided selection consistently identifies the most effective heuristic extension in 70% of cases for budget-constrained task allocation problems. In a MAS, agents share their local observations to gain global situational awareness for decision making and collaboration using a message passing system. When to send a message, how to encode a message, and how to leverage the received messages directly affect the effectiveness of the collaboration among agents. When employing Reinforcement Learning (RL) to train a multi-agent cooperative game, optimizing the message passing system becomes integral to agent policy enhancement. We propose the Belief-map Assisted Multi-agent System (BAMS), which leverages a neuro-symbolic belief map to enhance training. Compared to the sporadic and delayed feedback coming from the reward in RL, the feedback from the belief map is more consistent and reliable. Agents utilizing BAMS can learn a more effective message passing network, enhancing mutual understanding and improving overall game performance. We assess BAMS in a cooperative predator and prey game with varying map complexities, comparing its performance to previous multi-agent message passing models. Simulation results demonstrate that BAMS reduces training epochs by 66%, and agents employing the BAMS model complete the game with 34.62% fewer steps on average.

Access

Open Access

Download

Share

COinS