MCTS Based Dispatch of Autonomous Vehicles under Operational Constraints for Continuous Transportation

• URL: http://arxiv.org/abs/2407.16200v1
• Date: Tue, 23 Jul 2024 06:06:16 GMT
• Title: MCTS Based Dispatch of Autonomous Vehicles under Operational Constraints for Continuous Transportation
• Authors: Milan Tomy, Konstantin M. Seiler, Andrew J. Hill,
• Abstract summary: This article incorporates operational constraint satisfaction into the dispatch planning by utilising the MCTS based dispatch planner Flow-Achieving Scheduling Tree (FAST) Explicit cost formulations are avoided by utilising MCTS generator models to derive opportunity costs. Experimental studies with four types of operational constraints demonstrate the success of utilising opportunity costs for constraint satisfaction.
• Score: 3.7550827441501844
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Continuous transportation of material in the mining industry is achieved by the dispatch of autonomous haul-trucks with discrete haulage capacities. Recently, Monte Carlo Tree Search (MCTS) was successfully deployed in tackling challenges of long-run optimality, scalability and adaptability in haul-truck dispatch. Typically, operational constraints imposed on the mine site are satisfied by heuristic controllers or human operators independent of the dispatch planning. This article incorporates operational constraint satisfaction into the dispatch planning by utilising the MCTS based dispatch planner Flow-Achieving Scheduling Tree (FAST). Operational constraint violation and satisfaction are modelled as opportunity costs in the combinatorial optimisation problem of dispatch. Explicit cost formulations are avoided by utilising MCTS generator models to derive opportunity costs. Experimental studies with four types of operational constraints demonstrate the success of utilising opportunity costs for constraint satisfaction, and the effectiveness of integrating constraints into dispatch planning.

Related papers

• SPOT: Spatio-Temporal Pattern Mining and Optimization for Load Consolidation in Freight Transportation Networks [13.121155604809372]
  An effective load consolidation plan relies on carefully chosen consolidation points to ensure alignment with transportation management processes. Traditional optimization-based approaches provide exact solutions, but their computational complexity makes them impractical for large-scale instances. This work proposes SPOT, an end-to-end approach that integrates the benefits of machine learning (ML) and optimization for load consolidation.
  arXiv  Detail & Related papers  (2025-04-13T18:14:38Z)
• Ride-Sourcing Vehicle Rebalancing with Service Accessibility Guarantees via Constrained Mean-Field Reinforcement Learning [42.070187224580344]
  Rapid expansion of services such as Uber, Lyft and Didi Chuxing has reshaped urban transportation by offering flexible, on-demand mobility via mobile applications. Inadequate rebalancing results in prolonged rider waiting times, inefficient vehicle utilization, and inequitable distribution services. We introduce continuous-state mean-field control (MFC) and reinforcement learning (MFRL) models that explicitly represent each vehicle's precise location and employ continuous repositioning actions guided by the distribution of other vehicles.
  arXiv  Detail & Related papers  (2025-03-31T15:00:11Z)
• Monte Carlo Tree Diffusion for System 2 Planning [57.50512800900167]
  We introduce Monte Carlo Tree Diffusion (MCTD), a novel framework that integrates the generative strength of diffusion models with the adaptive search capabilities of Monte Carlo Tree Search (MCTS) MCTD achieves the benefits of MCTS such as controlling exploration-exploitation trade-offs within the diffusion framework.
  arXiv  Detail & Related papers  (2025-02-11T02:51:42Z)
• Diffusion Predictive Control with Constraints [51.91057765703533]
  Diffusion predictive control with constraints (DPCC) An algorithm for diffusion-based control with explicit state and action constraints that can deviate from those in the training data. We show through simulations of a robot manipulator that DPCC outperforms existing methods in satisfying novel test-time constraints while maintaining performance on the learned control task.
  arXiv  Detail & Related papers  (2024-12-12T15:10:22Z)
• Towards Interactive and Learnable Cooperative Driving Automation: a Large Language Model-Driven Decision-Making Framework [79.088116316919]
  Connected Autonomous Vehicles (CAVs) have begun to open road testing around the world, but their safety and efficiency performance in complex scenarios is still not satisfactory. This paper proposes CoDrivingLLM, an interactive and learnable LLM-driven cooperative driving framework.
  arXiv  Detail & Related papers  (2024-09-19T14:36:00Z)
• GPT-Augmented Reinforcement Learning with Intelligent Control for Vehicle Dispatching [82.19172267487998]
  GARLIC: a framework of GPT-Augmented Reinforcement Learning with Intelligent Control for vehicle dispatching. This paper introduces GARLIC: a framework of GPT-Augmented Reinforcement Learning with Intelligent Control for vehicle dispatching.
  arXiv  Detail & Related papers  (2024-08-19T08:23:38Z)
• Fair collaborative vehicle routing: A deep multi-agent reinforcement learning approach [49.00137468773683]
  Collaborative vehicle routing occurs when carriers collaborate through sharing their transportation requests and performing transportation requests on behalf of each other. Traditional game theoretic solution concepts are expensive to calculate as the characteristic function scales exponentially with the number of agents. We propose to model this problem as a coalitional bargaining game solved using deep multi-agent reinforcement learning.
  arXiv  Detail & Related papers  (2023-10-26T15:42:29Z)
• C-MCTS: Safe Planning with Monte Carlo Tree Search [2.8445375187526154]
  The Constrained Markov Decision Process (CMDP) formulation allows to solve safety-critical decision making tasks that are subject to constraints. We propose Constrained MCTS (C-MCTS), which estimates cost using a safety critic that is trained with Temporal Difference learning in an offline phase prior to agent deployment. C-MCTS satisfies cost constraints but operates closer to the constraint boundary, achieving higher rewards than previous work.
  arXiv  Detail & Related papers  (2023-05-25T16:08:30Z)
• Computation Offloading for Uncertain Marine Tasks by Cooperation of UAVs and Vessels [12.612678646691263]
  We focus on the decision of maritime task offloading by the cooperation of unmanned aerial vehicles (UAVs) and vessels. We formulate a Markov decision process, aiming to minimize the total execution time and energy cost. We leverage Lyapunov optimization to convert the long-term constraints of the total execution time and energy cost into their short-term constraints.
  arXiv  Detail & Related papers  (2023-02-13T02:24:25Z)
• Neural Optimal Transport with General Cost Functionals [66.41953045707172]
  We introduce a novel neural network-based algorithm to compute optimal transport plans for general cost functionals. As an application, we construct a cost functional to map data distributions while preserving the class-wise structure.
  arXiv  Detail & Related papers  (2022-05-30T20:00:19Z)
• Innovations in the field of on-board scheduling technologies [64.41511459132334]
  This paper proposes an onboard scheduler, that integrates inside an onboard software framework for mission autonomy. The scheduler is based on linear integer programming and relies on the use of a branch-and-cut solver. The technology has been tested on an Earth Observation scenario, comparing its performance against the state-of-the-art scheduling technology.
  arXiv  Detail & Related papers  (2022-05-04T12:00:49Z)
• An SMT Based Compositional Model to Solve a Conflict-Free Electric Vehicle Routing Problem [2.64699517152535]
  The Electric Conflict-Free Vehicle Routing Problem (CF-EVRP) involves constraints such as limited operating range of the vehicles, time windows on the delivery to the customers, and limited capacity on the number of vehicles the road segments can accommodate. We develop a compositional model that breaks down the problem into smaller and simpler sub-problems and provides sub-optimal, feasible solutions.
  arXiv  Detail & Related papers  (2021-06-10T20:37:46Z)
• Estimating the Robustness of Public Transport Systems Using Machine Learning [62.997667081978825]
  Planning public transport systems is a highly complex process involving many steps. Integrating robustness from a passenger's point of view makes the task even more challenging. In this paper, we explore a new way of such a scenario-based robustness approximation by using methods from machine learning.
  arXiv  Detail & Related papers  (2021-06-10T05:52:56Z)
• A Modular and Transferable Reinforcement Learning Framework for the Fleet Rebalancing Problem [2.299872239734834]
  We propose a modular framework for fleet rebalancing based on model-free reinforcement learning (RL) We formulate RL state and action spaces as distributions over a grid of the operating area, making the framework scalable. Numerical experiments, using real-world trip and network data, demonstrate that this approach has several distinct advantages over baseline methods.
  arXiv  Detail & Related papers  (2021-05-27T16:32:28Z)
• Real-time and Large-scale Fleet Allocation of Autonomous Taxis: A Case Study in New York Manhattan Island [14.501650948647324]
  Traditional models fail to efficiently allocate the available fleet to deal with the imbalance of supply (autonomous taxis) and demand (trips) We employ a Constrained Multi-agent Markov Decision Processes (CMMDP) to model fleet allocation decisions. We also leverage a Column Generation algorithm to guarantee the efficiency and optimality in a large scale.
  arXiv  Detail & Related papers  (2020-09-06T16:00:15Z)

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.