Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLarge-scale, Dynamic and Distributed Coalition Formation with Spatial and Temporal Constraints
79
0
0.0
(
0
)
Added by
Luca Capezzuto
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The Coalition Formation with Spatial and Temporal constraints Problem (CFSTP) is a multi-agent task allocation problem in which few agents have to perform many tasks, each with its deadline and workload. To maximize the number of completed tasks, the agents need to cooperate by forming, disbanding and reforming coalitions. The original mathematical programming formulation of the CFSTP is difficult to implement, since it is lengthy and based on the problematic Big-M method. In this paper, we propose a compact and easy-to-implement formulation. Moreover, we design D-CTS, a distributed version of the state-of-the-art CFSTP algorithm. Using public London Fire Brigade records, we create a dataset with $347588$ tasks and a test framework that simulates the mobilization of firefighters in dynamic environments. In problems with up to $150$ agents and $3000$ tasks, compared to DSA-SDP, a state-of-the-art distributed algorithm, D-CTS completes $3.79% pm [42.22%, 1.96%]$ more tasks, and is one order of magnitude more efficient in terms of communication overhead and time complexity. D-CTS sets the first large-scale, dynamic and distributed CFSTP benchmark.
rate research
Read More
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 typically much smaller than the number of tasks, thus the agents have to form coalitions in order to maximise the number of completed tasks. The current state-of-the-art CFSTP solver, the Coalition Formation with Look-Ahead (CFLA) algorithm, has two main limitations. First, its time complexity is exponential with the number of agents. Second, as we show, its look-ahead technique is not effective in real-world scenarios, such as open multi-agent systems, where new tasks can appear at any time. In this work, we study its design and define an extension, called Coalition Formation with Improved Look-Ahead (CFLA2), which achieves better performance. Since we cannot eliminate the limitations of CFLA in CFLA2, we also develop a novel algorithm to solve the CFSTP, the first to be anytime, efficient and with provable guarantees, called Cluster-based Coalition Formation (CCF). We empirically show that, in settings where the look-ahead technique is highly effective, CCF completes up to 30% (resp. 10%) more tasks than CFLA (resp. CFLA2) while being up to four orders of magnitude faster. Our results affirm CCF as the new state-of-the-art algorithm to solve the CFSTP.
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.
Participatory budgeting (PB) is a democratic process where citizens jointly decide on how to allocate public funds to indivisible projects. This paper focuses on PB processes where citizens may give additional money to projects they want to see funded. We introduce a formal framework for this kind of PB with donations. Our framework also allows for diversity constraints, meaning that each project belongs to one or more types, and there are lower and upper bounds on the number of projects of the same type that can be funded. We propose three general classes of methods for aggregating the citizens preferences in the presence of donations and analyze their axiomatic properties. Furthermore, we investigate the computational complexity of determining the outcome of a PB process with donations and of finding a citizens optimal donation strategy.
We study a setting in which a community wishes to identify a strongly supported proposal from a large space of alternatives, in order to change the status quo. We describe a process -- called deliberation -- in which agents dynamically form coalitions around proposals they prefer over the status quo. We formulate conditions (on the space of proposals and on the ways in which coalitions are formed) that guarantee deliberation to succeed, that is, to terminate by identifying a majority-supported proposal with largest possible support, as long as such a proposal exists. Our results provide theoretical foundations for the analysis of deliberative processes in systems for democratic deliberation support, such as, e.g., LiquidFeedback.
Optimization of resource distribution has been a challenging topic in current society. To explore this topic, we develop a Coalition Control Model(CCM) based on the Model Predictive Control(MPC) and test it using a fishing model with linear parameters. The fishing model focuses on the problem of distributing fishing fleets in certain regions to maximize fish caught using either exhaustive or heuristic search. Our method introduces a communication mechanism to allow fishing fleets to merge or split, after which new coalitions can be automatically formed. Having the coalition structure stabilized, the system reaches the equilibrium state through the Nash-Bargaining process. Our experiments on the hypothetical fishing model demonstrated that the CCM can dynamically distribute limited resources in complex scenarios.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
