Solving Vehicle Routing Problem for Unmanned Heterogeneous Vehicle Systems using Asynchronous Multi-Agent Architecture (A-teams)
Authors:
- 6 June 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 95-102
Abstract
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.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- A Two-Stage Approach for Routing Multiple Unmanned Aerial Vehicles with Stochastic Fuel ConsumptionSensors, 2018
- Optimal Dynamic Coverage Infrastructure for Large-Scale Fleets of Reconnaissance UAVs2017
- Reinforcement Learning Strategy for Solving the Resource-Constrained Project Scheduling Problem by a Team of A-TeamsLecture Notes in Computer Science, 2014
- Algorithms for Routing an Unmanned Aerial Vehicle in the Presence of Refueling DepotsIEEE Transactions on Automation Science and Engineering, 2013
- Team of A-Teams - A Study of the Cooperation between Program Agents Solving Difficult Optimization Problems2013
- A multi-agent system to solve the production–distribution planning problem for a supply chain: a genetic algorithm approachThe International Journal of Advanced Manufacturing Technology, 2008
- Routing a Heterogeneous Fleet of Vehicles2008
- Convex Optimization2004
- Using A-Teams to optimize automatic insertion of electronic componentsAdvanced Engineering Informatics, 2003
- A-Teams: An Agent Architecture for Optimization and Decision-SupportLecture Notes in Computer Science, 1999