Dynamical Vehicle Orienteering Problem for Multi-Rotor Unmanned Aerial Vehicles

• URL: http://arxiv.org/abs/2607.13789v1
• Date: Wed, 15 Jul 2026 12:48:18 GMT
• Title: Dynamical Vehicle Orienteering Problem for Multi-Rotor Unmanned Aerial Vehicles
• Abstract summary: The Dynamical Vehicle Orienteering Problem (DVOP) is a generalization of the Orienteering Problem (OP)<n>We study the DVOP in the context of multi-rotor Aerial Unmanned Vehicle (UAV) flight planning.
• Score: 3.5945543871230274
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: This paper introduces the Dynamical Vehicle Orienteering Problem (DVOP), a generalization of the Orienteering Problem (OP). The OP maximizes the reward collected from spatial targets under a limited travel budget; the DVOP extends it by accounting for both external and vehicle-actuated forces. We study the DVOP in the context of multi-rotor Unmanned Aerial Vehicle (UAV) flight planning, using a three-dimensional Point-Mass Model (PMM) constrained by maximum velocity and acceleration magnitudes and subject to gravitational acceleration, with the travel budget expressed as a maximum flight time. Because the DVOP couples reward maximization with time-optimal trajectory planning, it cannot be formulated as a simple graph problem and solved exactly without relaxing or under-actuating the vehicle dynamics. We therefore propose two solution approaches: a Branch-and-Bound (BnB) procedure that combines Non-Linear Programming (NLP) and Mixed-Integer Linear Programming (MILP) to provide high-quality solutions, and a Large Neighborhood Search (LNS) metaheuristic that supplies an initial reward bound and scales to instances intractable for the BnB. The BnB relies on a novel MILP formulation of travel costs based on minimum-time trajectory primitives through target triplets, yielding a tight reward upper bound, while the LNS uses limited thrust decomposition to compute fast, high-quality PMM trajectories. Experiments on benchmark instances show improvements of up to 37 % over state-of-the-art solutions for the Kinematic Orienteering Problem, and a real-world deployment on a multi-rotor UAV verifies the proposed PMM solution trajectories.

Related papers

• Reward-Density Heuristic for Dynamic Multi-Vehicle Routing: Performance and Computational Efficiency [0.0]
  We address a dynamic, online variant combining elements of the Vehicle Problem (VRP) and the Orienteering Problem (OP)<n>We propose and evaluate a reward-density for dynamic multi-vehicle assignment, referred to as the Efficiency Routing.<n>Across all tested configurations, the Efficiency matches the solution quality of the best metaheuristic algorithms while requiring two to three orders of magnitude less planning time.
  arXiv  Detail & Related papers  (2026-07-07T09:37:46Z)
• HAD: Combining Hierarchical Diffusion with Metric-Decoupled RL for End-to-End Driving [51.268878540511054]
  We propose HAD, an end-to-end planning framework with a Hierarchical Diffusion Policy.<n>We show that HAD achieves new state-of-the-art performance on both NAVSIM and HUGSIM.
  arXiv  Detail & Related papers  (2026-04-04T04:12:47Z)
• Multi UAVs Preflight Planning in a Shared and Dynamic Airspace [4.802862639452379]
  We propose DTAPP-IICR: a Delivery-Time Aware Prioritized Planning method with Incremental and Iterative Conflict Resolution.<n>Our framework first generates an initial solution by prioritizing missions based on urgency.<n>It computes roundtrip trajectories using SFIPP-ST, a novel 4D single-agent planner.<n>On benchmarks with temporal NFZs, DTAPP-IICR achieves near-100% success with fleets of up to 1,000 UAVs.
  arXiv  Detail & Related papers  (2026-02-12T15:18:46Z)
• Optimal Safety-Aware Scheduling for Multi-Agent Aerial 3D Printing with Utility Maximization under Dependency Constraints [16.61271813421072]
  An optimization problem takes a construction mission divided into sub-tasks and a team of autonomous UAVs, along with limited volume and battery.<n>It generates an optimal mission plan comprising task assignments and scheduling while accounting for task dependencies.<n>An importance prioritization is proposed to accelerate the computation by guiding the solution toward more important tasks.
  arXiv  Detail & Related papers  (2025-12-05T15:34:43Z)
• Dependency-Aware Task Offloading in Multi-UAV Assisted Collaborative Mobile Edge Computing [53.88774113545582]
  This paper presents a novel multi-unmanned aerial vehicle (UAV) assisted collaborative mobile edge computing (MEC) framework.<n>It aims to minimize the system cost, and thus realize an improved trade-off between task consumption and energy consumption.<n>We show that the proposed scheme can significantly reduce the system cost, and thus realize an improved trade-off between task consumption and energy consumption.
  arXiv  Detail & Related papers  (2025-10-23T02:55:40Z)
• Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning [56.240199425429445]
  Multi-Robot Motion Planning (MPMP) involves generating trajectories for multiple robots operating in a shared continuous workspace.<n>While discrete multi-agent finding (MAPF) methods are broadly adopted due to their scalability, their coarse discretization trajectory quality.<n>This paper tackles limitations of two approaches by introducing discrete MAPF solvers with constrained generative diffusion models.
  arXiv  Detail & Related papers  (2025-08-27T17:59:36Z)
• Task Delay and Energy Consumption Minimization for Low-altitude MEC via Evolutionary Multi-objective Deep Reinforcement Learning [52.64813150003228]
  The low-altitude economy (LAE), driven by unmanned aerial vehicles (UAVs) and other aircraft, has revolutionized fields such as transportation, agriculture, and environmental monitoring.<n>In the upcoming six-generation (6G) era, UAV-assisted mobile edge computing (MEC) is particularly crucial in challenging environments such as mountainous or disaster-stricken areas.<n>The task offloading problem is one of the key issues in UAV-assisted MEC, primarily addressing the trade-off between minimizing the task delay and the energy consumption of the UAV.
  arXiv  Detail & Related papers  (2025-01-11T02:32:42Z)
• Learn to Solve Vehicle Routing Problems ASAP: A Neural Optimization Approach for Time-Constrained Vehicle Routing Problems with Finite Vehicle Fleet [0.0]
  We propose an NCO approach to solve a time-constrained capacitated VRP with a finite vehicle fleet size. The method is able to find adequate and cost-efficient solutions, showing both flexibility and robust generalizations.
  arXiv  Detail & Related papers  (2024-11-07T15:16:36Z)
• Integrating Higher-Order Dynamics and Roadway-Compliance into Constrained ILQR-based Trajectory Planning for Autonomous Vehicles [3.200238632208686]
  Trajectory planning aims to produce a globally optimal route for Autonomous Passenger Vehicles. Existing implementations utilizing the vehicle bicycle kinematic model may not guarantee controllable trajectories. We augment this model by higher-order terms, including the first and second-order derivatives of curvature and longitudinal jerk.
  arXiv  Detail & Related papers  (2023-09-25T22:30:18Z)
• Motion Planning and Control for Multi Vehicle Autonomous Racing at High Speeds [100.61456258283245]
  This paper presents a multi-layer motion planning and control architecture for autonomous racing. The proposed solution has been applied on a Dallara AV-21 racecar and tested at oval race tracks achieving lateral accelerations up to 25 $m/s2$.
  arXiv  Detail & Related papers  (2022-07-22T15:16:54Z)
• Data Freshness and Energy-Efficient UAV Navigation Optimization: A Deep Reinforcement Learning Approach [88.45509934702913]
  We design a navigation policy for multiple unmanned aerial vehicles (UAVs) where mobile base stations (BSs) are deployed. We incorporate different contextual information such as energy and age of information (AoI) constraints to ensure the data freshness at the ground BS. By applying the proposed trained model, an effective real-time trajectory policy for the UAV-BSs captures the observable network states over time.
  arXiv  Detail & Related papers  (2020-02-21T07:29: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.