Adaptive Probabilistic Planning for the Uncertain and Dynamic Orienteering Problem

Qiuchen Qian, Yanran Wang, David Boyle

TL;DR

Researchers have developed ADAPT, a framework that allows autonomous drones to navigate complex "prizes-vs-budget" missions (the Orienteering Problem) even when energy costs are unpredictable and changing. By using real-time Bayesian inference to update its "safety belief," ADAPT achieved a 100% mission success rate in simulations, significantly outperforming traditional heuristic and frequentist methods.

What Problem Does This Paper Address?

The Orienteering Problem (OP) is a classic optimization challenge: a vehicle must visit various locations to collect "prizes" and return to a depot before running out of a limited resource (like fuel or battery).

While the OP is well-studied, real-world applications—like Unmanned Aerial Vehicles (UAVs) recharging sensors in a forest—face a major hurdle: uncertainty. Wind gusts, turbulence, and hardware inefficiencies mean the energy cost to travel between two points isn't a fixed number; it’s a moving target. Most existing solutions assume we already know the probability distribution of these costs. In reality, these parameters are often unknown at the start and change during the mission.

The authors propose the Uncertain and Dynamic Orienteering Problem (UDOP) to model these real-world "unknown unknowns" and introduce a system to solve it on the fly.

Methods

The authors introduce ADAPT (ADaptive Approach for Probabilistic paThs), which operates in three iterative phases:

  1. Offline Planning: Before takeoff, the UAV generates an initial path using a modified Ant Colony System (ACS) metaheuristic based on prior (but likely inaccurate) knowledge.
  2. Execution: As the UAV flies, it continuously logs its actual power consumption. It doesn't just follow the path; it gathers data.
  3. Online Planning: This is the "brain" of the operation. ADAPT uses Bayesian Inference (BI) with a conjugate Normal-Gamma prior to update its estimate of the energy cost distribution.
  4. Safety Belief ($\Theta$): Instead of planning for the "average" cost, the planner uses a Cumulative Distribution Function (CDF) to ensure a specific probability (e.g., 75% or 99%) that the UAV can complete the path safely.
  5. Inherited ACS (IACS): To save computation time, the online re-planner "inherits" the pheromone matrix from the previous path, allowing it to find a new optimal route in seconds as it learns more about the environment.

Datasets

The framework was evaluated using:

  • Real-world Flight Data: Power consumption models were validated using data from a DJI M100 quadrotor.
  • Simulated WRSNs: Three test instances—California20, California30, and California40—representing Wireless Rechargeable Sensor Networks randomly deployed in a 1 $km^2$ area in California with 20, 30, and 40 nodes respectively.
  • Dynamic Scenarios: The researchers simulated "windy" conditions by shifting and scaling the actual power means and standard deviations by up to 20% relative to the UAV's initial estimates.

Key Insights and Ideas

  • Safety over Averages: Planning for the "mean" energy cost is a recipe for failure in stochastic environments. By using a Safety Belief ($\Theta$), the UAV can choose to be more conservative early in the mission when data is sparse and become more "ambitious" as its confidence in the energy model grows.
  • Learning on the Fly: The use of Bayesian Inference allows the system to bridge the gap between "prior knowledge" (lab-tested power models) and "online observations" (actual wind conditions). The posterior distribution narrows as the UAV completes more legs of its journey.
  • Efficiency through Inheritance: Re-solving an optimization problem from scratch at every node is computationally expensive. By "inheriting" the best path from the previous iteration to initialize the Ant Colony System, ADAPT maintains high-quality solutions with very low latency.

Key Results

  • 100% Mission Success Rate (MSR): Across all tested scenarios (including those with 20% higher-than-expected energy costs), ADAPT never failed to return the UAV safely to the depot.
  • Robustness vs. Heuristics: Comparable heuristic-based approaches (like ROMP or WeightedErr) failed up to 70% of the time in challenging conditions. Frequentist approaches (like Monte Carlo Greedy) averaged only a 67% MSR.
  • Solution Quality: Despite its conservative safety focus, ADAPT maintained prize collection levels comparable to or better than alternative methods that frequently crashed.
  • Speed: The system can complete re-planning within seconds, making it viable for real-time deployment on standard embedded hardware (tested on an Intel NUC).

Limitations and Future Work

  • Prize Uncertainty: Currently, ADAPT assumes the "prize" (the amount of energy a sensor needs) is known once the UAV arrives. In reality, the recharging efficiency (IPT link efficiency) can also be stochastic due to coil misalignment.
  • Multi-UAV Systems: The paper focuses on a single UAV. Extending this to a "Team Orienteering Problem" where multiple drones coordinate in the same uncertain environment is a logical next step.
  • Local vs. Global Coupling: The authors note that while they handle global mission planning, the interplay with local trajectory controllers (which handle immediate obstacle avoidance) could be further integrated to refine energy estimates.

Summary updated

BibTeX
@article{qian2025adaptive,
  author = {Qiuchen Qian and Yanran Wang and David Boyle},
  title = {{Adaptive Probabilistic Planning for the Uncertain and Dynamic Orienteering Problem}},
  journal = {IEEE Internet of Things Journal},
  year = {2025},
  doi = {10.1109/jiot.2025.3525985},
}
Figure