There is a strong demand for covering a large area autonomously by multiple UAVs (Unmanned Aerial Vehicles) supported by a ground vehicle. Limited by UAVs' battery life and communication distance, complete coverage of large areas typically involves multiple take-offs and landings to recharge batteries, and the transportation of UAVs between operation areas by a ground vehicle. In this paper, we introduce a novel large-area-coverage planning framework which collectively optimizes the paths for aerial and ground vehicles. Our method first partitions a large area into sub-areas, each of which a given fleet of UAVs can cover without recharging batteries. UAV operation routes, or trails, are then generated for each sub-area. Next, the assignment of trials to different UAVs and the order in which UAVs visit their assigned trails are simultaneously optimized to minimize the total UAV flight distance. Finally, a ground vehicle transportation path which visits all sub-areas is found by solving an asymmetric traveling salesman problem (ATSP). Although finding the globally optimal trail assignment and transition paths can be formulated as a Mixed Integer Quadratic Program (MIQP), the MIQP is intractable even for small problems. We show that the solution time can be reduced to close-to-real-time levels by first finding a feasible solution using a Random Key Genetic Algorithm (RKGA), which is then locally optimized by solving a much smaller MIQP.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Constrained Heterogeneous Vehicle Path Planning for Large-area Coverage


    Beteiligte:
    Deng, Di (Autor:in) / Jing, Wei (Autor:in) / Fu, Yuhe (Autor:in) / Huang, Ziyin (Autor:in) / Liu, Jiahong (Autor:in) / Shimada, Kenji (Autor:in)

    Erscheinungsdatum :

    2019


    Medientyp :

    Preprint


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    Clustering-Based Multi-Region Coverage-Path Planning of Heterogeneous UAVs

    Peng Xiao / Ni Li / Feng Xie et al. | DOAJ | 2023

    Freier Zugriff

    Coverage path planning method within convex polygon sea area

    LI JI HONG / KANG HYUNGJOO / KIM MIN GYU et al. | Europäisches Patentamt | 2024

    Freier Zugriff

    Coverage path planning method within convex polygon sea area

    Europäisches Patentamt | 2024

    Freier Zugriff

    A Clustering-Based Coverage Path Planning Method for Autonomous Heterogeneous UAVs

    Chen, Jinchao / Du, Chenglie / Zhang, Ying et al. | IEEE | 2022