Multi-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. To maximize profits while minimizing time penalties, agents need to cooperate by forming, disbanding and reforming coalitions. In this paper, we name this problem Multi-Agent Routing and Scheduling through Coalition formation (MARSC) and show that it generalizes the important Team Orienteering Problem with Time Windows. We propose a binary integer program and an anytime and scalable heuristic to solve it. Using public London Fire Brigade records, we create a dataset with 347588 tasks and a test framework that simulates the mobilization of firefighters. In problems with up to 150 agents and 3000 tasks, our heuristic finds solutions up to 3.25 times better than the Earliest Deadline First approach commonly used in real-time systems. Our results constitute the first large-scale benchmark for the MARSC problem.
Code (0)
등록된 구현이 없습니다.
Tasks
Disaster ResponseSchedulingSimilar Papers 제목 키워드 기반
Coalitional Bargaining via Reinforcement Learning: An Application to Collaborative Vehicle Routing
Collaborative Vehicle Routing is where delivery companies cooperate by sharing their delivery information and performing delivery requests on behalf of each other. This achieves economies of scale and thus reduces cost, …
reinforcement-learningBOHM: Zero-Cost Hierarchical Attribution for Compound AI Systems
Compound AI systems route tasks through hierarchies of specialised components. Attribution is dominated by Shapley-based methods (SHAP), which decompose a coalition value function into per-component marginal contribution…
Anytime and Efficient Coalition Formation with Spatial and Temporal Constraints
The Coalition Formation with Spatial and Temporal constraints Problem (CFSTP) is a multi-agent task scheduling problem where the tasks are spatially distributed, with deadlines and workloads, and the number of agents is …
SchedulingCoalition-based Planning of Military Operations: Adversarial Reasoning Algorithms in an Integrated Decision Aid
Use of knowledge-based planning tools can help alleviate the challenges of planning a complex operation by a coalition of diverse parties in an adversarial environment. We explore these challenges and potential contribut…
SchedulingFair collaborative vehicle routing: A deep multi-agent reinforcement learning approach
Collaborative vehicle routing occurs when carriers collaborate through sharing their transportation requests and performing transportation requests on behalf of each other. This achieves economies of scale, thus reducing…
Multi-agent Reinforcement Learningreinforcement-learning