Please use this identifier to cite or link to this item:
Type: Thesis
Title: Deep Learning for Bipartite Assignment Problems
Author: Gibbons, Daniel Steve
Issue Date: 2019
School/Discipline: School of Electrical and Electronic Engineering
Abstract: A recurring problem in autonomy is the optimal assignment of agents to tasks. Often, such assignments cannot be computed efficiently. Therefore, the existing literature tends to focus on the development of handcrafted heuristics that exploit the structure of a particular assignment problem. These heuristics can find near-optimal assignments in real-time. However, if the problem specification changes slightly, a previously derived heuristic may not longer be applicable. Instead of manually deriving a heuristic for each assignment problem, this thesis considers a deep learning approach. Given a problem description, deep learning can be used to find near-optimal heuristics with minimal human input. The main contribution of this thesis is a deep learning architecture called Deep Bipartite Assignments (DBA), which can automatically learn heuristics for a large class of assignment problems. The effectiveness of DBA is demonstrated on two NP-Hard problems: the weapon-target assignment problem and the multi-resource generalised assignment problem. Without any expert domain knowledge, DBA is competitive with strong, handcrafted baselines.
Advisor: Lim, Cheng-Chew
Shi, Peng
Dissertation Note: Thesis (MPhil) -- University of Adelaide, School of Electrical and Electronic Engineering, 2019
Keywords: Deep learning
combinatorial optimisation
neural networks
reinforcement learning
Provenance: This electronic version is made publicly available by the University of Adelaide in accordance with its open access policy for student theses. Copyright in this thesis remains with the author. This thesis may incorporate third party material which has been used by the author pursuant to Fair Dealing exceptions. If you are the owner of any included third party copyright material you wish to be removed from this electronic version, please complete the take down form located at:
Appears in Collections:Research Theses

Files in This Item:
File Description SizeFormat 
Gibbons2019_MPhil.pdf701.13 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.