TOP-Former: A Multi-Agent Transformer Approach for the Team Orienteering Problem
Route planning for a fleet of vehicles is an important task in applications such as package delivery, surveillance, or transportation, often integrated within larger Intelligent Transportation Systems (ITS). This problem is commonly formulated as a Vehicle Routing Problem (VRP) known as the Team Orienteering Problem (TOP). Existing solvers for this problem primarily rely on either linear programming, which provides accurate solutions but requires computation times that grow with the size of the problem, or heuristic methods, which typically find suboptimal solutions in a shorter time. In this paper, we introduce TOP-Former, a multi-agent route planning neural network designed to efficiently and accurately solve the Team Orienteering Problem. The proposed algorithm is based on a centralized Transformer neural network capable of learning to encode the scenario (modeled as a graph) and analyze the complete context of all agents to deliver fast, precise, and collaborative solutions. Unlike other neural network-based approaches that adopt a more local perspective, TOP-Former is trained to understand the global situation of the vehicle fleet and generate solutions that maximize long-term expected returns. Extensive experiments demonstrate that the presented system outperforms most state-of-the-art methods in terms of both accuracy and computation speed.
Code (1)
Tasks
Combinatorial OptimizationMulti-agent Reinforcement LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Solving routing problems for multiple cooperative Unmanned Aerial Vehicles using Transformer networks, vol. 122, pp. 106085, 2023
Missions involving Unmanned Aerial Vehicle usually consist of reaching a set of regions, performing some actions in each region, and returning to a determined depot after all the regions have been successfully visited or…
Combinatorial OptimizationDeep Reinforcement LearningMulti-agent Reinforcement LearningA Benchmark for Multi-UAV Task Assignment of an Extended Team Orienteering Problem
A benchmark for multi-UAV task assignment is presented in order to evaluate different algorithms. An extended Team Orienteering Problem is modeled for a kind of multi-UAV task assignment problem. Three intelligent algori…
Learning Ordinal Response Policies in Rank-Based Stochastic Prize-Collecting Games
The Team Orienteering Problem (TOP) generalizes many real-world multi-agent scheduling and routing tasks that occur in autonomous mobility, aerial logistics, and surveillance applications. While many flavors of the TOP e…
Transformer Guided Coevolution: Improved Team Selection in Multiagent Adversarial Team Games
We consider the problem of team selection within multiagent adversarial team games. We propose BERTeam, a novel algorithm that uses a transformer-based deep neural network with Masked Language Model training to select th…
Deep Reinforcement LearningLanguage ModelingLanguage ModellingMulti-Agent Routing and Scheduling Through Coalition Formation
In task allocation for real-time domains, such as disaster response, a limited number of agents is deployed across a large area to carry out numerous tasks, each with its prerequisites, profit, time window and workload. …
Disaster ResponseScheduling