Online multidimensional multiple choice knapsack path planner for UAVs

Manisha Wadhwa

doi:10.1016/j.robot.2026.105560

2026-06-08

PRE

Manisha Wadhwa *

Neelima Gupta

Sanjay Madria

DOI：10.1016/j.robot.2026.105560

原文链接

原文求助

摘要

En 中文

无人机的快速普及在安全关键且时间敏感的应用中（如灾害管理、战场侦察、城市监控和基础设施检查）要求在线路径规划策略。此类任务的基本要求是生成通过某些预指定航点的飞行路径，同时服务于动态请求的时空任务点（如捕捉空中图像）。现有的无人机路径规划方法，包括A*及其变体、元启发式算法和动态规划，寻找从起点到终点的最短距离路径，但它们主要离线运行并假设完全先验环境知识，因此，在产生解决方案前处理整个问题空间会产生显著更高的计算成本。因此，它们不适用于动态现实场景，其中任务不可预测地到达，环境条件持续演变。此外，由于拥堵或其他环境条件（如风速），最短距离并不总是意味着最快或最安全的路线。本文通过提出第一个完全在线、奖励最大化的无人机路径规划框架来填补这一关键空白，该框架同时处理动态到达的任务请求、预先分配的航点以及无需完全先验知识或定期重新优化的环境不确定性。本文提出了一种贪婪在线动态路径规划算法（ODP），将其建模为多重选择背包问题，其中任务在满足航点并有限制总遍历时间的情况下完成时获得奖励。接下来，我们将ODP扩展为多维在线动态路径规划算法（MODP），这是一种既受时间约束又受距离约束的贪婪在线动态路径规划算法。我们将问题建模为在线多重选择多维背包问题，其中低可达性的任务点具有更高的关联奖励。我们分析了ODP（一种在线方法）的效率，并经验性地将其性能与最优离线（暴力搜索）算法进行了比较。发现ODP提供了竞争比cr(alg) 2为0.8，表明接近最优的性能。也就是说，ODP返回的路径可获得约80%的最优奖励。接下来，我们分析了MODP的效率，并经验性地将其性能与最优离线（暴力搜索）算法进行了比较。发现MODP在与暴力搜索的性能比较中提供了近0.7的竞争比。此外，我们还比较了MODP与ODP的性能，发现MODP在添加有限距离约束以及有限时间约束时，可以返回获得96%奖励的路径。统计比较和大规模可扩展性评估进一步证实了所提出框架在现实世界无人机任务规划中的鲁棒性、重要性和实用性。

Keyword:

Multidimensional knapsack

Path planning

UAV

Online algorithm