Fast moving but power hungry unmanned aerial vehicles (UAVs) can recharge on slow-moving unmanned ground vehicles (UGVs) to cooperatively perform tasks over wide areas. Such a cooperation can be achieved efficiently by solving a path planning problem. On top of solving a path planning problem, the problem of routing an heterogeneous set of vehicles in an optimal fashion is quite challenging. In order to solve the computationally expensive path-planning problem in a reasonable time, we created a two-level optimization approach with heuristics. At the outer level, the UGV route is parameterized by considering which set of locations to visit in the scenario and the UGV wait times to recharge UAVs and at the inner level, the UAV route is solved by formulating and solving a vehicle routing problem with capacity constraints, time windows, and dropped visits. The UGV free parameters need to be optimized judiciously in order to create high quality solutions. We explore two methods for tuning the free UGV parameters: (1) a Genetic Algorithm (GA), and (2) Asynchronous Multi-agent architecture (A-teams). The A-teams uses multiple agents to create, improve, and destroy solutions. The parallel asynchronous architecture enables A-teams to quickly optimize the parameters. Our results on test cases show that the A-teams produces similar solutions as GA but is 2-3 times faster.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Solving Vehicle Routing Problem for Unmanned Heterogeneous Vehicle Systems using Asynchronous Multi-Agent Architecture (A-teams)




    Publication date :

    2023-06-06


    Size :

    1271831 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Multi-agent platform for solving the dynamic vehicle routing problem

    Barbucha, Dariusz / Jedrzejowicz, Piotr | IEEE | 2008


    Heterogeneous multi-depot collaborative vehicle routing problem

    Zhang, Qihuan / Wang, Ziteng / Huang, Min et al. | Elsevier | 2022


    On Modelling and Solving Heterogeneous Vehicle Routing Problem with Multi-Trips and Multi-Products

    Setiawan, Fran / Masruroh, Nur Aini / Pramuditha, Zita Iga | BASE | 2019

    Free access

    Networked Unmanned Aerial Vehicle Teams (NUAVT)

    Ryan, Jack / Hanson, Curt / Jacobson, Steve | NTRS | 2006


    Solving Vehicle Routing Problem for Intelligent Systems using Delaunay Triangulation

    Sakthivel, M. / Kant Gupta, Shashi / Karras, Dimitrios A. et al. | IEEE | 2022