针对动态不确定的路径规划问题，提出自适应概率规划方法，提升无人机充电任务成功率。
Adaptive Probabilistic Planning for the Uncertain and Dynamic Orienteering Problem
- 基于贝叶斯在线更新，动态调整路径与能耗估计
- 在所有场景下实现100%任务成功率，优于传统方法最多70%失败率
- 适合无人机、传感器网络等实时动态环境下的可靠路径决策
定向旅行问题（OP）是经典路径优化问题，已被扩展以包含不确定性，反映随机或动态的行程成本、奖赏获取成本及奖赏本身。现有方法在真实场景中可能因建模知识不足和在线参数未知而效率低下。为此，我们提出不确定且动态的定向旅行问题（UDOP），将行程成本建模为参数未知且随时间变化的分布，并将不确定行程成本与动态奖赏及奖赏获取成本关联，用于目标与预算约束。为应对UDOP，我们开发了自适应概率路径方法（ADAPT），基于初始离线解，迭代执行‘执行’与‘在线规划’。执行阶段更新系统状态并记录在线成本观测；在线规划器采用贝叶斯方法，基于安全信念自适应估计能耗并优化路径序列。我们在无线可充电传感网络中的无人机充电调度任务中评估了ADAPT。实验表明，该方法在保持相近求解质量与计算时间的同时，显著提升鲁棒性。大量仿真显示，ADAPT在所有测试场景下均达到100%任务成功率（MSR），而对比的启发式与频率派方法最高失败率达70%，平均仅67% MSR。本工作推动了带不确定性的OP研究，为不确定动态环境中的实际应用提供了高效可靠的解决方案。
原文摘要 · Abstract (English)
The Orienteering Problem (OP) is a well-studied routing problem that has been extended to incorporate uncertainties, reflecting stochastic or dynamic travel costs, prize-collection costs, and prizes. Existing approaches may, however, be inefficient in real-world applications due to insufficient modeling knowledge and initially unknowable parameters in online scenarios. Thus, we propose the Uncertain and Dynamic Orienteering Problem (UDOP), modeling travel costs as distributions with unknown and time-variant parameters. UDOP also associates uncertain travel costs with dynamic prizes and prize-collection costs for its objective and budget constraints. To address UDOP, we develop an ADaptive Approach for Probabilistic paThs - ADAPT, that iteratively performs 'execution' and 'online planning' based on an initial 'offline' solution. The execution phase updates system status and records online cost observations. The online planner employs a Bayesian approach to adaptively estimate power consumption and optimize path sequence based on safety beliefs. We evaluate ADAPT in a practical Unmanned Aerial Vehicle (UAV) charging scheduling problem for Wireless Rechargeable Sensor Networks. The UAV must optimize its path to recharge sensor nodes efficiently while managing its energy under uncertain conditions. ADAPT maintains comparable solution quality and computation time while offering superior robustness. Extensive simulations show that ADAPT achieves a 100% Mission Success Rate (MSR) across all tested scenarios, outperforming comparable heuristic-based and frequentist approaches that fail up to 70% (under challenging conditions) and averaging 67% MSR, respectively. This work advances the field of OP with uncertainties, offering a reliable and efficient approach for real-world applications in uncertain and dynamic environments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。