Decision-Oriented Learning with Differentiable Submodular Maximization for Vehicle Routing Problem

• URL: http://arxiv.org/abs/2303.01543v2
• Date: Mon, 25 Sep 2023 15:40:56 GMT
• Title: Decision-Oriented Learning with Differentiable Submodular Maximization for Vehicle Routing Problem
• Authors: Guangyao Shi, Pratap Tokekar
• Abstract summary: We study the problem of learning a function that maps context observations (input) to parameters of a submodular function (output) In this paper, we propose a framework that incorporates task optimization as a differentiable layer in the prediction phase.
• Score: 23.211667169614227
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of learning a function that maps context observations (input) to parameters of a submodular function (output). Our motivating case study is a specific type of vehicle routing problem, in which a team of Unmanned Ground Vehicles (UGVs) can serve as mobile charging stations to recharge a team of Unmanned Ground Vehicles (UAVs) that execute persistent monitoring tasks. {We want to learn the mapping from observations of UAV task routes and wind field to the parameters of a submodular objective function, which describes the distribution of landing positions of the UAVs .} Traditionally, such a learning problem is solved independently as a prediction phase without considering the downstream task optimization phase. However, the loss function used in prediction may be misaligned with our final goal, i.e., a good routing decision. Good performance in the isolated prediction phase does not necessarily lead to good decisions in the downstream routing task. In this paper, we propose a framework that incorporates task optimization as a differentiable layer in the prediction phase. Our framework allows end-to-end training of the prediction model without using engineered intermediate loss that is targeted only at the prediction performance. In the proposed framework, task optimization (submodular maximization) is made differentiable by introducing stochastic perturbations into deterministic algorithms (i.e., stochastic smoothing). We demonstrate the efficacy of the proposed framework using synthetic data. Experimental results of the mobile charging station routing problem show that the proposed framework can result in better routing decisions, e.g. the average number of UAVs recharged increases, compared to the prediction-optimization separate approach.

Related papers

• Traj-Explainer: An Explainable and Robust Multi-modal Trajectory Prediction Approach [12.60529039445456]
  Navigating complex traffic environments has been significantly enhanced by advancements in intelligent technologies, enabling accurate environment perception and trajectory prediction for automated vehicles. Existing research often neglects the consideration of the joint reasoning of scenario agents and lacks interpretability in trajectory prediction models. An explainability-oriented trajectory prediction model is designed in this work, named Explainable Diffusion Conditional based Multimodal Trajectory Prediction Traj-Explainer.
  arXiv  Detail & Related papers  (2024-10-22T08:17:33Z)
• Truncating Trajectories in Monte Carlo Policy Evaluation: an Adaptive Approach [51.76826149868971]
  Policy evaluation via Monte Carlo simulation is at the core of many MC Reinforcement Learning (RL) algorithms. We propose as a quality index a surrogate of the mean squared error of a return estimator that uses trajectories of different lengths. We present an adaptive algorithm called Robust and Iterative Data collection strategy Optimization (RIDO)
  arXiv  Detail & Related papers  (2024-10-17T11:47:56Z)
• DiFSD: Ego-Centric Fully Sparse Paradigm with Uncertainty Denoising and Iterative Refinement for Efficient End-to-End Autonomous Driving [55.53171248839489]
  We propose an ego-centric fully sparse paradigm, named DiFSD, for end-to-end self-driving. Specifically, DiFSD mainly consists of sparse perception, hierarchical interaction and iterative motion planner. Experiments conducted on nuScenes dataset demonstrate the superior planning performance and great efficiency of DiFSD.
  arXiv  Detail & Related papers  (2024-09-15T15:55:24Z)
• Optimizing Diffusion Models for Joint Trajectory Prediction and Controllable Generation [49.49868273653921]
  Diffusion models are promising for joint trajectory prediction and controllable generation in autonomous driving. We introduce Optimal Gaussian Diffusion (OGD) and Estimated Clean Manifold (ECM) Guidance. Our methodology streamlines the generative process, enabling practical applications with reduced computational overhead.
  arXiv  Detail & Related papers  (2024-08-01T17:59:59Z)
• A Multi-Stage Goal-Driven Network for Pedestrian Trajectory Prediction [6.137256382926171]
  This paper proposes a novel method for pedestrian trajectory prediction, called multi-stage goal-driven network (MGNet) The network comprises three main components: a conditional variational autoencoder (CVAE), an attention module, and a multi-stage goal evaluator. The effectiveness of MGNet is demonstrated through comprehensive experiments on the JAAD and PIE datasets.
  arXiv  Detail & Related papers  (2024-06-26T03:59:21Z)
• Knowledge-aware Graph Transformer for Pedestrian Trajectory Prediction [15.454206825258169]
  Predicting pedestrian motion trajectories is crucial for path planning and motion control of autonomous vehicles. Recent deep learning-based prediction approaches mainly utilize information like trajectory history and interactions between pedestrians. This paper proposes a graph transformer structure to improve prediction performance.
  arXiv  Detail & Related papers  (2024-01-10T01:50:29Z)
• Control-Aware Prediction Objectives for Autonomous Driving [78.19515972466063]
  We present control-aware prediction objectives (CAPOs) to evaluate the downstream effect of predictions on control without requiring the planner be differentiable. We propose two types of importance weights that weight the predictive likelihood: one using an attention model between agents, and another based on control variation when exchanging predicted trajectories for ground truth trajectories.
  arXiv  Detail & Related papers  (2022-04-28T07:37:21Z)
• TAE: A Semi-supervised Controllable Behavior-aware Trajectory Generator and Predictor [3.6955256596550137]
  Trajectory generation and prediction play important roles in planner evaluation and decision making for intelligent vehicles. We propose a behavior-aware Trajectory Autoencoder (TAE) that explicitly models drivers' behavior. Our model addresses trajectory generation and prediction in a unified architecture and benefits both tasks.
  arXiv  Detail & Related papers  (2022-03-02T17:37:44Z)
• RoMA: Robust Model Adaptation for Offline Model-based Optimization [115.02677045518692]
  We consider the problem of searching an input maximizing a black-box objective function given a static dataset of input-output queries. A popular approach to solving this problem is maintaining a proxy model that approximates the true objective function. Here, the main challenge is how to avoid adversarially optimized inputs during the search.
  arXiv  Detail & Related papers  (2021-10-27T05:37:12Z)
• Divide-and-Conquer for Lane-Aware Diverse Trajectory Prediction [71.97877759413272]
  Trajectory prediction is a safety-critical tool for autonomous vehicles to plan and execute actions. Recent methods have achieved strong performances using Multi-Choice Learning objectives like winner-takes-all (WTA) or best-of-many. Our work addresses two key challenges in trajectory prediction, learning outputs, and better predictions by imposing constraints using driving knowledge.
  arXiv  Detail & Related papers  (2021-04-16T17:58: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.