Deep Learning for Bipartite Assignment Problems

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.