Introduction
The Orienteering Problem (OP) is a fundamental challenge in robotics and logistics: a vehicle must visit a set of locations to collect rewards ("prizes") and return to a starting depot within a strict resource budget, such as battery life. In real-world Unmanned Aerial Vehicle (UAV) missions—such as recharging remote sensors—this problem is complicated by environmental uncertainty. Factors like wind, turbulence, and hardware degradation mean that the energy cost of traveling between nodes is not a fixed value but a stochastic variable.
To address this, researchers have introduced the Uncertain and Dynamic Orienteering Problem (UDOP) and a novel solution framework called ADAPT (ADaptive Approach for Probabilistic paThs).
The ADAPT Framework
ADAPT is designed to handle "unknown unknowns" by iteratively refining its energy models during mission execution. The framework consists of three distinct phases that form a continuous feedback loop.
- Offline Planning: Using initial (often inaccurate) prior knowledge, the UAV generates a baseline path using a modified Ant Colony System (ACS) metaheuristic.
- Execution: As the UAV flies, it monitors its real-time power consumption across different flight phases (takeoff, cruise, landing). This data serves as the ground truth for updating environmental models.
- Online Planning: This is the core innovation. ADAPT uses Bayesian Inference to update the probability distributions of energy costs. If the updated model suggests the current path is too risky, the system triggers a re-planning phase. To maintain computational efficiency, the new planner "inherits" the pheromone matrix from the previous iteration, allowing for rapid path optimization in flight.
Probabilistic Safety and Learning
A key feature of ADAPT is the Safety Belief ($\Theta$). Rather than planning for the average expected cost—which often leads to mission failure in volatile conditions—ADAPT uses a Cumulative Distribution Function (CDF). This allows operators to set a specific confidence threshold (e.g., 95% or 99%) that the UAV will return safely.
As shown in the figure above, the framework dynamically adjusts the mission scope based on this belief. Early in a mission, when data is sparse and uncertainty is high, a high safety belief leads to more conservative paths. As the UAV gathers more data and the Bayesian posterior distribution narrows, the system gains confidence, potentially allowing for more ambitious prize collection if conditions are favorable.
Results and Performance
The framework was validated using real flight data from a DJI M100 quadrotor and simulated large-scale sensor networks. Key findings include:
- Reliability: ADAPT achieved a 100% Mission Success Rate (MSR) across all tested scenarios, even when actual energy costs were 20% higher than initial estimates.
- Superiority over Heuristics: Traditional heuristic methods failed up to 70% of the time in the same uncertain conditions because they could not adapt to shifting energy requirements.
- Efficiency: The "Inherited ACS" approach allowed the UAV to re-calculate optimal paths in seconds on standard embedded hardware, making it suitable for real-time deployment.
Conclusion
ADAPT represents a significant step forward in autonomous mission planning for uncertain environments. By shifting from deterministic "average-case" planning to a probabilistic "safety-first" approach powered by real-time Bayesian learning, it ensures that UAVs can complete complex orienteering tasks without the risk of mid-mission power failure. Future work will explore extending this framework to multi-UAV teams and accounting for uncertainty in the rewards (prizes) themselves.
Summary updated