2023/12/08 by Jiawei Wang, Weiwei Wu, Wang, Jiawei +5 · 1 citation
Computer Science · Engineering · Mathematics · #Aerospace engineering #Algorithm #Artificial intelligence #Computer science #Constraint (computer-aided design) #Constraint programming #Dynamic programming #Engineering #Mathematical optimization #Mathematics #Motion planning #Object (grammar) #Optimization and Search Problems #Path (computing) #Quality (philosophy) #Range (aeronautics) #Robotic Path Planning Algorithms #Robotics and Sensor-Based Localization #Set (abstract data type) #Shortest path problem #Stochastic programming #Task (project management) #Theoretical computer science
paper · pdf · doi:10.48550/arxiv.2312.04943
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2023/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper addresses a UAV path planning task that seeks to observe a set of objects while satisfying the observation quality constraint. A dynamic programming algorithm is proposed that enables the UAV to observe the target objects with the shortest path while subjecting to the observation quality constraint. The objects have their own facing direction and restricted observation range. With an observing order, the algorithm achieves (1+ε)-approximation ratio in theory and runs in polynomial time. The extensive results demonstrate that the algorithm produces near-optimal solutions, the effectiveness of which is also tested and proved in the Airsim simulator, a realistic virtual environment.