Efficient and Fair Decentralized Task Allocation Algorithms for Autonomous Vehicles: A Machine Learning Based Approach
Abstract
The proposed project aims at improving the efficiency of the multi-agent decentralized allocation with considerations in computation, communication, strategic, fairness and adaptability for real-life applications. Auction-based method such as the Consensus-based auction algorithm (CBAA) are effective methods for decentralized task assignment with bounded optimality and guaranteed convergence. The methods have very few theoretical guarantees in terms of approximation of the global objectives such as maximizing welfare or minimizing costs. The goals of the project include extending existing approaches to cater for more general feasibility constraints and achieving desirable approximation guarantees. Within the framework of auction-based approaches, there can be multiple ways that allocation decisions can be made. We will also take a data-driven domain-specific approach and try to learn which combination of allocation heuristics that work best for Autonomous Vehicle applications. The overall procedure relies on a cost and reward function of each task that is locally known by an agent. The cost and reward function are application specific and its quality directly affects the performance of the algorithm. In many real-life applications, the reward and cost relationship between agents and tasks is not constant but a function of the set of allocated tasks, their execution order and the environment. The greedy algorithm used in the original CBBA does not guarantee to find the optimal execution order with the lowest cost and highest reward, neither can it find the optimal trade-off between the reward and cost. Deep reinforcement learning has widely been used to learn a control policy that maximizes the long term discounted reward of a dynamic system. However, it is a centralized procedure that assumes the decision maker has the knowledge of the entire environment. We propose to investigate techniques to integrate these two approaches. We will enhance the existing CBAA using deep reinforcement learning, so that the cost/reward can be better estimated using a model constructed through machine learning. As a typical application with delayed reward/penalty, multi-agent task allocation with autonomous vehicle route planning and resource management will be considered as a showcase problem to evaluate and demonstrate our research results. In addition to a learned cost/reward function, formal analysis of the trade offs between computation and communication requirements will be addressed. The expected outcomes from the project include novel algorithms that extend the state-of the-art models for decentralized task allocation for autonomous vehicles. The algorithms will be assessed based on performance and robustness as well as how they perform as compared to existing baseline algorithm.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 07, 2021
- Source ID
- FA23862014062
Entities
People
- Qinru Qiu
Organizations
- Air Force Office of Scientific Research
- Syracuse University
- United States Air Force