Neural Weighted A*: Learning Graph Costs and Heuristics with Differentiable Anytime A*

• URL: http://arxiv.org/abs/2105.01480v1
• Date: Tue, 4 May 2021 13:17:30 GMT
• Title: Neural Weighted A*: Learning Graph Costs and Heuristics with Differentiable Anytime A*
• Authors: Alberto Archetti, Marco Cannici, Matteo Matteucci
• Abstract summary: Recent works related to data-driven planning aim at learning either cost functions or planner functions, but not both. We propose Neural Weighted A*, a differentiable anytime planner able to produce improved representations of planar maps as graph costs and planners. We experimentally show the validity of our claims by testing Neural Weighted A* against several baselines, introducing a novel, tile-based navigation dataset.
• Score: 12.117737635879037
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recently, the trend of incorporating differentiable algorithms into deep learning architectures arose in machine learning research, as the fusion of neural layers and algorithmic layers has been beneficial for handling combinatorial data, such as shortest paths on graphs. Recent works related to data-driven planning aim at learning either cost functions or heuristic functions, but not both. We propose Neural Weighted A*, a differentiable anytime planner able to produce improved representations of planar maps as graph costs and heuristics. Training occurs end-to-end on raw images with direct supervision on planning examples, thanks to a differentiable A* solver integrated into the architecture. More importantly, the user can trade off planning accuracy for efficiency at run-time, using a single, real-valued parameter. The solution suboptimality is constrained within a linear bound equal to the optimal path cost multiplied by the tradeoff parameter. We experimentally show the validity of our claims by testing Neural Weighted A* against several baselines, introducing a novel, tile-based navigation dataset. We outperform similar architectures in planning accuracy and efficiency.

Related papers

• DataSP: A Differential All-to-All Shortest Path Algorithm for Learning Costs and Predicting Paths with Context [4.202961704179733]
  This paper introduces DataSP, a differentiable all-to-all shortest path algorithm to facilitate learning latent costs from trajectories. Complex latent cost functions from contextual features can be represented in the algorithm through a neural network approximation. We show that DataSP outperforms state-of-the-art machine learning approaches in predicting paths on graphs.
  arXiv  Detail & Related papers  (2024-05-08T09:45:54Z)
• Joint Feature and Differentiable $ k $-NN Graph Learning using Dirichlet Energy [103.74640329539389]
  We propose a deep FS method that simultaneously conducts feature selection and differentiable $ k $-NN graph learning. We employ Optimal Transport theory to address the non-differentiability issue of learning $ k $-NN graphs in neural networks. We validate the effectiveness of our model with extensive experiments on both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-05-21T08:15:55Z)
• One-Pass Learning via Bridging Orthogonal Gradient Descent and Recursive Least-Squares [8.443742714362521]
  We develop an algorithm for one-pass learning which seeks to perfectly fit every new datapoint while changing the parameters in a direction that causes the least change to the predictions on previous datapoints. Our algorithm uses the memory efficiently by exploiting the structure of the streaming data via an incremental principal component analysis (IPCA) Our experiments show the effectiveness of the proposed method compared to the baselines.
  arXiv  Detail & Related papers  (2022-07-28T02:01:31Z)
• Condensing Graphs via One-Step Gradient Matching [50.07587238142548]
  We propose a one-step gradient matching scheme, which performs gradient matching for only one single step without training the network weights. Our theoretical analysis shows this strategy can generate synthetic graphs that lead to lower classification loss on real graphs. In particular, we are able to reduce the dataset size by 90% while approximating up to 98% of the original performance.
  arXiv  Detail & Related papers  (2022-06-15T18:20:01Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• 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)
• A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks [20.170140039052455]
  We propose a radically different approach in that no data is required for training the neural networks that produce the solution. In particular, we reduce the optimization problem to a neural network and employ a dataless training scheme to refine the parameters of the network such that those parameters yield the structure of interest.
  arXiv  Detail & Related papers  (2022-03-15T19:21:31Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  Pairwise learning refers to learning tasks where the loss function depends on a pair instances. Online descent (OGD) is a popular approach to handle streaming data in pairwise learning. In this paper, we propose simple and online descent to methods for pairwise learning.
  arXiv  Detail & Related papers  (2021-11-23T18:10:48Z)
• Learning Time-Varying Graphs from Online Data [39.21234914444073]
  This work proposes an algorithmic framework to learn time-varying graphs from online data. It renders it model-independent, i.e., it can be theoretically analyzed in its abstract formulation. We specialize the framework to three well-known graph learning models, namely, the Gaussian graphical model (GGM), the structural equation model (SEM), and the smoothness-based model (SBM)
  arXiv  Detail & Related papers  (2021-10-21T09:46:44Z)
• Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
  We use a pruning machine learning as a pre-processing step followed by an exact Programming approach to sparsify the travelling salesman problem. Our learning approach requires very little training data and is amenable to mathematical analysis.
  arXiv  Detail & Related papers  (2021-04-19T14:35:14Z)
• 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)

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.