Author name cluster

Sofia Amador Nelke

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

IJCAI Conference 2023 Conference Paper

Asynchronous Communication Aware Multi-Agent Task Allocation

Ben Rachmut
Sofia Amador Nelke
Roie Zivan

Multi-agent task allocation in physical environments with spatial and temporal constraints, are hard problems that are relevant in many realistic applications. A task allocation algorithm based on Fisher market clearing (FMC_TA), that can be performed either centrally or distributively, has been shown to produce high quality allocations in comparison to both centralized and distributed state of the art incomplete optimization algorithms. However, the algorithm is synchronous and therefore depends on perfect communication between agents. We propose FMC_ATA, an asynchronous version of FMC_TA, which is robust to message latency and message loss. In contrast to the former version of the algorithm, FMC_ATA allows agents to identify dynamic events and initiate the generation of an updated allocation. Thus, it is more compatible for dynamic environments. We further investigate the conditions in which the distributed version of the algorithm is preferred over the centralized version. Our results indicate that the proposed asynchronous distributed algorithm produces consistent results even when the communication level is extremely poor.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Asynchronous Communication Aware Multi-Agent Task Allocation

Ben Rachmut
Sofia Amador Nelke
Roie Zivan

Multi-agent task allocation in physical environments with spatial and temporal constraints are hard problems relevant to many realistic applications. A task allocation algorithm based on Fisher market clearing (FMC_TA), which can be performed centrally or distributively, has been shown to produce high quality allocations compared to the centralized and distributed state of the art incomplete optimization algorithms. However, the algorithm is synchronous and thus depends on perfect communication between agents. We propose FMC_ATA, an asynchronous version of FMC_TA, which is robust to message latency and message loss. In contrast to the former version of the algorithm, FMC_ATA allows agents to identify events and initiate the generation of an updated allocation. Thus, it is more compatible with dynamic environments.

PDF

AAMAS Conference 2022 Conference Paper

Towards Addressing Dynamic Multi-agent Task Allocation in Law Enforcement

Itshak Tkach
Sofia Amador Nelke

To deal with the underlying heterogeneous law enforcement problem (LEPH), one needs to allocate police officers to dynamic tasks whose locations, arrival times, and importance levels are unknown a priory. Addressing this challenge and inspired by real police logs, this research aims to solve the LEPH problem by using and comparing three methods: Fisher market-based FMC_TAH+, swarm intelligence HDBA, and Simulated Annealing SA algorithms. The three methods were compared in this study for the performance measures that are commonly used by law enforcement authorities. The results indicate an advantage for FMC_TAH+ both in total utility and in the average arrival time to tasks. Also, compared respectively to HDBA and SA, FMC_TAH+ leads to 34% and 32% higher team utility in the highest shift workload.

PDF

TIST Journal 2020 Journal Article

Market Clearing–based Dynamic Multi-agent Task Allocation

Sofia Amador Nelke
Steven Okamoto
Roie Zivan

Realistic multi-agent team applications often feature dynamic environments with soft deadlines that penalize late execution of tasks. This puts a premium on quickly allocating tasks to agents. However, when such problems include temporal and spatial constraints that require tasks to be executed sequentially by agents, they are NP-hard, and thus are commonly solved using general and specifically designed incomplete heuristic algorithms. We propose FMC_TA, a novel such incomplete task allocation algorithm that allows tasks to be easily sequenced to yield high-quality solutions. FMC_TA first finds allocations that are fair (envy-free), balancing the load and sharing important tasks among agents, and efficient (Pareto optimal) in a simplified version of the problem. It computes such allocations in polynomial or pseudo-polynomial time (centrally or distributedly, respectively) using a Fisher market with agents as buyers and tasks as goods. It then heuristically schedules the allocations, taking into account inter-agent constraints on shared tasks. We empirically compare our algorithm to state-of-the-art incomplete methods, both centralized and distributed, on law enforcement problems inspired by real police logs. We present a novel formalization of the law enforcement problem, which we use to perform our empirical study. The results show a clear advantage for FMC_TA in total utility and in measures in which law enforcement authorities measure their own performance. Besides problems with realistic properties, the algorithms were compared on synthetic problems in which we increased the size of different elements of the problem to investigate the algorithm’s behavior when the problem scales. The domination of the proposed algorithm was found to be consistent.

Details DOI

AAMAS Conference 2017 Conference Paper

Incentivizing Cooperation between Heterogeneous Agents in Dynamic Task Allocation

Sofia Amador Nelke
Roie Zivan

Market Clearing is an economic concept that features attractive properties when used for resource and task allocation, e. g. , Pareto optimality and Envy Freeness. Recently, an algorithm based on Market Clearing, FMC_TA, has been shown to be most effective for realistic dynamic multi agent task allocation, outperforming general optimization methods, e. g. , Simulated annealing, and dedicated algorithms, specifically designed for task allocation. That been said, FMC_TA was applied to a homogeneous team of agents and used linear personal utility functions for representing agents’ preferences. These properties limited the settings on which the algorithm could be applied. In this paper we advance the research on task allocation methods based on market clearing by enhancing the FMC_TA algorithm such that it: 1) can use concave personal utility functions as its input and 2) can apply to applications which require the collaboration of heterogeneous agents, i. e. agents with different capabilities. We demonstrate that the use of concave functions indeed encourages collaboration among agents. Our results on both homogeneous and heterogeneous scenarios indicate that the use of personal utility functions with small concavity is enough to achieve the desired incentivized cooperation result, and on the other hand, in contrast to functions with increased concavity, does not cause a severe delay in the execution of tasks.

PDF