Bigraph Matching Weighted with Learnt Incentive Function for Multi-Robot Task Allocation

• URL: http://arxiv.org/abs/2403.07131v1
• Date: Mon, 11 Mar 2024 19:55:08 GMT
• Title: Bigraph Matching Weighted with Learnt Incentive Function for Multi-Robot Task Allocation
• Authors: Steve Paul, Nathan Maurer, Souma Chowdhury
• Abstract summary: This paper develops a Graph Reinforcement Learning framework to learn the robustnesss or incentives for a bipartite graph matching approach to Multi-Robot Task Allocation. The performance of this new bigraph matching approach augmented with a GRL-derived incentive is found to be at par with the original bigraph matching approach.
• Score: 5.248564173595024
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Most real-world Multi-Robot Task Allocation (MRTA) problems require fast and efficient decision-making, which is often achieved using heuristics-aided methods such as genetic algorithms, auction-based methods, and bipartite graph matching methods. These methods often assume a form that lends better explainability compared to an end-to-end (learnt) neural network based policy for MRTA. However, deriving suitable heuristics can be tedious, risky and in some cases impractical if problems are too complex. This raises the question: can these heuristics be learned? To this end, this paper particularly develops a Graph Reinforcement Learning (GRL) framework to learn the heuristics or incentives for a bipartite graph matching approach to MRTA. Specifically a Capsule Attention policy model is used to learn how to weight task/robot pairings (edges) in the bipartite graph that connects the set of tasks to the set of robots. The original capsule attention network architecture is fundamentally modified by adding encoding of robots' state graph, and two Multihead Attention based decoders whose output are used to construct a LogNormal distribution matrix from which positive bigraph weights can be drawn. The performance of this new bigraph matching approach augmented with a GRL-derived incentive is found to be at par with the original bigraph matching approach that used expert-specified heuristics, with the former offering notable robustness benefits. During training, the learned incentive policy is found to get initially closer to the expert-specified incentive and then slightly deviate from its trend.

Related papers

• HGPROMPT: Bridging Homogeneous and Heterogeneous Graphs for Few-shot Prompt Learning [16.587427365950838]
  We propose HGPROMPT, a novel pre-training and prompting framework to unify not only pre-training and downstream tasks but also homogeneous and heterogeneous graphs. We thoroughly evaluate and analyze HGPROMPT through extensive experiments on three public datasets.
  arXiv  Detail & Related papers  (2023-12-04T13:20:15Z)
• Adapting to Change: Robust Counterfactual Explanations in Dynamic Data Landscapes [9.943459106509687]
  We introduce a novel semi-supervised Graph Counterfactual Explainer (GCE) methodology, Dynamic GRAph Counterfactual Explainer (DyGRACE) It leverages initial knowledge about the data distribution to search for valid counterfactuals while avoiding using information from potentially outdated decision functions in subsequent time steps. DyGRACE is quite effective and can act as a drift detector, identifying distributional drift based on differences in reconstruction errors between iterations.
  arXiv  Detail & Related papers  (2023-08-04T14:41:03Z)
• SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning [131.04781590452308]
  We present SimTeG, a frustratingly Simple approach for Textual Graph learning. We first perform supervised parameter-efficient fine-tuning (PEFT) on a pre-trained LM on the downstream task. We then generate node embeddings using the last hidden states of finetuned LM.
  arXiv  Detail & Related papers  (2023-08-03T07:00:04Z)
• Subgraph Matching via Query-Conditioned Subgraph Matching Neural Networks and Bi-Level Tree Search [33.9052190473029]
  Subgraph Matching is a core operation in graph database search, biomedical analysis, social group finding, etc. In this paper, we propose a novel encoder-decoder neural network architecture to dynamically compute the matching information between the query and the target graphs. Experiments on five large real-world target graphs show that N-BLS can significantly improve the subgraph matching performance.
  arXiv  Detail & Related papers  (2022-07-21T04:47:21Z)
• Multi-Robot Active Mapping via Neural Bipartite Graph Matching [49.72892929603187]
  We study the problem of multi-robot active mapping, which aims for complete scene map construction in minimum time steps. The key to this problem lies in the goal position estimation to enable more efficient robot movements. We propose a novel algorithm, namely NeuralCoMapping, which takes advantage of both approaches.
  arXiv  Detail & Related papers  (2022-03-30T14:03:17Z)
• MGAE: Masked Autoencoders for Self-Supervised Learning on Graphs [55.66953093401889]
  Masked graph autoencoder (MGAE) framework to perform effective learning on graph structure data. Taking insights from self-supervised learning, we randomly mask a large proportion of edges and try to reconstruct these missing edges during training.
  arXiv  Detail & Related papers  (2022-01-07T16:48:07Z)
• ROD: Reception-aware Online Distillation for Sparse Graphs [23.55530524584572]
  We propose ROD, a novel reception-aware online knowledge distillation approach for sparse graph learning. We design three supervision signals for ROD: multi-scale reception-aware graph knowledge, task-based supervision, and rich distilled knowledge. Our approach has been extensively evaluated on 9 datasets and a variety of graph-based tasks.
  arXiv  Detail & Related papers  (2021-07-25T11:55:47Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  Data association across frames is at the core of Multiple Object Tracking (MOT) task. Existing methods mostly ignore the context information among tracklets and intra-frame detections. We propose a novel learnable graph matching method to address these issues.
  arXiv  Detail & Related papers  (2021-03-30T08:58:45Z)
• Deep Reinforcement Learning of Graph Matching [63.469961545293756]
  Graph matching (GM) under node and pairwise constraints has been a building block in areas from optimization to computer vision. We present a reinforcement learning solver for GM i.e. RGM that seeks the node correspondence between pairwise graphs. Our method differs from the previous deep graph matching model in the sense that they are focused on the front-end feature extraction and affinity function learning.
  arXiv  Detail & Related papers  (2020-12-16T13:48:48Z)
• Self-supervised Auxiliary Learning with Meta-paths for Heterogeneous Graphs [21.617020380894488]
  We propose a novel self-supervised auxiliary learning method to learn graph neural networks on heterogeneous graphs. Our method can be applied to any graph neural networks in a plug-in manner without manual labeling or additional data.
  arXiv  Detail & Related papers  (2020-07-16T12:32:11Z)
• Learning to Hash with Graph Neural Networks for Recommender Systems [103.82479899868191]
  Graph representation learning has attracted much attention in supporting high quality candidate search at scale. Despite its effectiveness in learning embedding vectors for objects in the user-item interaction network, the computational costs to infer users' preferences in continuous embedding space are tremendous. We propose a simple yet effective discrete representation learning framework to jointly learn continuous and discrete codes.
  arXiv  Detail & Related papers  (2020-03-04T06:59:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.