Scalable Probabilistic Routes

• URL: http://arxiv.org/abs/2306.10736v1
• Date: Mon, 19 Jun 2023 07:10:34 GMT
• Title: Scalable Probabilistic Routes
• Authors: Suwei Yang, Victor C. Liang, Kuldeep S. Meel
• Abstract summary: One promising approach for predicting routes uses decision diagrams that are augmented with probability values. We introduce a relaxed encoding that uses a linear number of variables to significantly reduce the size of resultant decision diagrams. Instead of a stepwise sampling procedure, we propose a single pass sampling-based route prediction.
• Score: 33.119667669694216
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Inference and prediction of routes have become of interest over the past decade owing to a dramatic increase in package delivery and ride-sharing services. Given the underlying combinatorial structure and the incorporation of probabilities, route prediction involves techniques from both formal methods and machine learning. One promising approach for predicting routes uses decision diagrams that are augmented with probability values. However, the effectiveness of this approach depends on the size of the compiled decision diagrams. The scalability of the approach is limited owing to its empirical runtime and space complexity. In this work, our contributions are two-fold: first, we introduce a relaxed encoding that uses a linear number of variables with respect to the number of vertices in a road network graph to significantly reduce the size of resultant decision diagrams. Secondly, instead of a stepwise sampling procedure, we propose a single pass sampling-based route prediction. In our evaluations arising from a real-world road network, we demonstrate that the resulting system achieves around twice the quality of suggested routes while being an order of magnitude faster compared to state-of-the-art.

Related papers

• Less is More: Non-uniform Road Segments are Efficient for Bus Arrival Prediction [11.203654925279439]
  We propose a Reinforcement Learning (RL)-based approach to efficiently and adaptively learn non-uniform road segments for arrival time prediction.<n>Our method ensures optimal segment selection while maintaining computational efficiency, offering a significant improvement over traditional uniform approaches.
  arXiv  Detail & Related papers  (2025-12-08T06:25:06Z)
• Generalizable Trajectory Prediction via Inverse Reinforcement Learning with Mamba-Graph Architecture [6.590896800137733]
  This paper presents a novel Inverse Reinforcement Learning framework that captures human-like decision-making.<n>The learned reward function is utilized to maximize the likelihood of output by the encoder-decoder architecture.
  arXiv  Detail & Related papers  (2025-06-14T12:18:19Z)
• HetGL2R: Learning to Rank Critical Road Segments via Attributed Heterogeneous Graph Random Walks [1.015962377068103]
  HetGL2R is an attributed heterogeneous graph learning approach for ranking node importance in road networks. HetGL2R significantly outperforms baselines in incorporating OD demand and route choice information, achieving more accurate and robust node ranking.
  arXiv  Detail & Related papers  (2025-04-27T11:32:41Z)
• Enhancing Path Planning Performance through Image Representation Learning of High-Dimensional Configuration Spaces [0.4143603294943439]
  We present a novel method for accelerating path-planning tasks in unknown scenes with obstacles. We approximate the distribution of waypoints for a collision-free path using the Rapidly-exploring Random Tree algorithm. Our experiments demonstrate promising results in accelerating path-planning tasks under critical time constraints.
  arXiv  Detail & Related papers  (2025-01-11T21:14:52Z)
• Efficient Data Representation for Motion Forecasting: A Scene-Specific Trajectory Set Approach [12.335528093380631]
  This study introduces a novel approach for generating scene-specific trajectory sets tailored to different contexts. A deterministic goal sampling algorithm identifies relevant map regions, while our Recursive In-Distribution Subsampling (RIDS) method enhances trajectory plausibility. Experiments on the Argoverse 2 dataset demonstrate that our method achieves up to a 10% improvement in Driving Area Compliance.
  arXiv  Detail & Related papers  (2024-07-30T11:06:39Z)
• 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)
• Predicting Drivers' Route Trajectories in Last-Mile Delivery Using A Pair-wise Attention-based Pointer Neural Network [5.092311422459955]
  In last-mile delivery, drivers deviate from planned routes because of their tacit knowledge of the road and curbside infrastructure. Being able to predict the actual stop sequence that a human driver would follow can help to improve route planning in last-mile delivery. This paper proposes a pair-wise attention-based pointer neural network for this prediction task using drivers' historical delivery trajectory data.
  arXiv  Detail & Related papers  (2023-01-10T06:11:20Z)
• GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
  We propose a learnable network to approximate geodesic paths on 3D surfaces. The proposed method provides efficient approximations of the shortest paths and geodesic distances estimations.
  arXiv  Detail & Related papers  (2022-05-30T16:22:53Z)
• Large-Scale Sequential Learning for Recommender and Engineering Systems [91.3755431537592]
  In this thesis, we focus on the design of an automatic algorithms that provide personalized ranking by adapting to the current conditions. For the former, we propose novel algorithm called SAROS that take into account both kinds of feedback for learning over the sequence of interactions. The proposed idea of taking into account the neighbour lines shows statistically significant results in comparison with the initial approach for faults detection in power grid.
  arXiv  Detail & Related papers  (2022-05-13T21:09:41Z)
• Road Extraction from Overhead Images with Graph Neural Networks [18.649284163019516]
  We propose a method that directly infers the final road graph in a single pass. The key idea consists in combining a Fully Convolutional Network in charge of locating points of interest and a Graph Neural Network which predicts links between these points. We evaluate our method against existing works on the popular RoadTracer dataset and achieve competitive results.
  arXiv  Detail & Related papers  (2021-12-09T21:10:27Z)
• Trajectory Prediction with Graph-based Dual-scale Context Fusion [43.51107329748957]
  We present a graph-based trajectory prediction network named the Dual Scale Predictor. It encodes both the static and dynamical driving context in a hierarchical manner. Thanks to the proposed dual-scale context fusion network, our DSP is able to generate accurate and human-like multi-modal trajectories.
  arXiv  Detail & Related papers  (2021-11-02T13:42:16Z)
• 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)
• Congestion-aware Multi-agent Trajectory Prediction for Collision Avoidance [110.63037190641414]
  We propose to learn congestion patterns explicitly and devise a novel "Sense--Learn--Reason--Predict" framework. By decomposing the learning phases into two stages, a "student" can learn contextual cues from a "teacher" while generating collision-free trajectories. In experiments, we demonstrate that the proposed model is able to generate collision-free trajectory predictions in a synthetic dataset.
  arXiv  Detail & Related papers  (2021-03-26T02:42:33Z)
• The Importance of Prior Knowledge in Precise Multimodal Prediction [71.74884391209955]
  Roads have well defined geometries, topologies, and traffic rules. In this paper we propose to incorporate structured priors as a loss function. We demonstrate the effectiveness of our approach on real-world self-driving datasets.
  arXiv  Detail & Related papers  (2020-06-04T03:56:11Z)
• CARPe Posterum: A Convolutional Approach for Real-time Pedestrian Path Prediction [3.883460584034766]
  We propose a convolutional approach for real-time pedestrian path prediction, CARPe. It utilizes a variation of Graph Isomorphism Networks in combination with an agile convolutional neural network design to form a fast and accurate path prediction approach. Results in both inference speed and prediction accuracy are achieved, improving FPS considerably in comparison to current state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-05-26T01:10:01Z)
• Joint Multi-Dimension Pruning via Numerical Gradient Update [120.59697866489668]
  We present joint multi-dimension pruning (abbreviated as JointPruning), an effective method of pruning a network on three crucial aspects: spatial, depth and channel simultaneously. We show that our method is optimized collaboratively across the three dimensions in a single end-to-end training and it is more efficient than the previous exhaustive methods.
  arXiv  Detail & Related papers  (2020-05-18T17:57:09Z)

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.