More Like this

1. A Comparison of New Swarm Task Allocation Algorithms in Unknown Environments with Varying Task Density

   Cai, Grace; Harasha, Noble; Lynch, Nancy (May 2023, Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2023))

   Task allocation is an important problem for robot swarms to solve, allowing agents to reduce task completion time by performing tasks in a distributed fashion. Existing task allocation algorithms often assume prior knowledge of task location and demand or fail to consider the effects of the geometric distribution of tasks on the completion time and communication cost of the algorithms. In this paper, we examine an environment where agents must explore and discover tasks with positive demand and successfully assign themselves to complete all such tasks. We first provide a new discrete general model for modeling swarms. Operating within this theoretical framework, we propose two new task allocation algorithms for initially unknown environments – one based on N-site selection and the other on virtual pheromones. We analyze each algorithm separately and also evaluate the effectiveness of the two algorithms in dense vs. sparse task distributions. Compared to the Levy walk, which has been theorized to be optimal for foraging, our virtual pheromone inspired algorithm is much faster in sparse to medium task densities but is communication and agent intensive. Our site selection inspired algorithm also outperforms Levy walk in sparse task densities and is a less resource-intensive option than our virtual pheromone algorithm for this case. Because the performance of both algorithms relative to random walk is dependent on task density, our results shed light on how task density is important in choosing a task allocation algorithm in initially unknown environments. 

   more » « less
2. Hierarchical Task Assignment and Path Finding with Limited Communication for Robot Swarms

   https://doi.org/10.3390/app11073115  

   Albani, Dario; Hönig, Wolfgang; Nardi, Daniele; Ayanian, Nora; Trianni, Vito (April 2021, Applied Sciences)

   null (Ed.)

   Complex service robotics scenarios entail unpredictable task appearance both in space and time. This requires robots to continuously relocate and imposes a trade-off between motion costs and efficiency in task execution. In such scenarios, multi-robot systems and even swarms of robots can be exploited to service different areas in parallel. An efficient deployment needs to continuously determine the best allocation according to the actual service needs, while also taking relocation costs into account when such allocation must be modified. For large scale problems, centrally predicting optimal allocations and movement paths for each robot quickly becomes infeasible. Instead, decentralized solutions are needed that allow the robotic system to self-organize and adaptively respond to the task demands. In this paper, we propose a distributed and asynchronous approach to simultaneous task assignment and path planning for robot swarms, which combines a bio-inspired collective decision-making process for the allocation of robots to areas to be serviced, and a search-based path planning approach for the actual routing of robots towards tasks to be executed. Task allocation exploits a hierarchical representation of the workspace, supporting the robot deployment to the areas that mostly require service. We investigate four realistic environments of increasing complexity, where each task requires a robot to reach a location and work for a specific amount of time. The proposed approach improves over two different baseline algorithms in specific settings with statistical significance, while showing consistently good results overall. Moreover, the proposed solution is robust to limited communication and robot failures. 

   more » « less
3. Many-to-many matching based task allocation for dispersed computing

   https://doi.org/10.1007/s00607-023-01160-2  

   Hui, Hongwen; Lin, Fuhong; Meng, Lei; Yang, Lei; Zhou, Xianwei (January 2023, Computing)

   Dispersed computing is a new resource-centric computing paradigm, which makes use of idle resources in the network to complete the tasks. Effectively allocating tasks between task nodes and networked computation points (NCPs) is a critical factor for maximizing the performance of dispersed computing. Due to the heterogeneity of nodes and the priority requirements of tasks, it brings great challenges to the task allocation in dispersed computing. In this paper, we propose a task allocation model based on incomplete preference list. The requirements and permissions of task nodes and NCPs are quantitatively measured through the preference list. In the model, the task completion rate, response time, and communication distance are taken as three optimizing parameters. To solve this NP-hard optimization problem, we develop a new many-to-many matching algorithm based on incomplete preference list. The unilateral optimal and stable solution of the model are obtained. Taking into account the needs for location privacy-preserving, we use the planar Laplace mechanism to produce obfuscated locations instead of real locations. The mechanism satisfies ε-differential privacy. Finally, the efficacy of the proposed model is demonstrated through extensive numerical analysis. Particularly, when the number of task nodes and NCPs reaches 1:2, the task completion rate can reach 99.33%. 

   more » « less
4. Lower Bounds for Dynamic Distributed Task Allocation

   Su, Hsin-Hao; Wein, Nicole (January 2019, 7th Workshop on Biological Distributed Algorithms (BDA))

   We study the problem of distributed task allocation in multi-agent systems e.g. the division of labor in an ant colony or robot swarm. Suppose there is a collection of agents, a collection of tasks, and a demand vector, which specifies the number of agents required to perform each task.The goal of the agents is to collectively allocate themselves to the tasks to satisfy the demand vector. We study the dynamic version of the problem where the demand vector changes overtime. Here, the goal is to minimize the switching cost, which is the number of agents that change tasks in response to a change in the demand vector. The switching cost is an important metric since changing tasks may incur significant overhead.We study a mathematical formalization of the above problem introduced by Su, Su, Dornhaus, and Lynch [21]. We prove the first non-trivial lower bounds for the switching cost. 

   more » « less
5. Lower Bounds for Dynamic Distributed Task Allocation

   Su, H.; Wein, N. (January 2020, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020))

   We study the problem of distributed task allocation in multi-agent systems. Suppose there is a collection of agents, a collection of tasks, and a demand vector, which specifies the number of agents required to perform each task. The goal of the agents is to cooperatively allocate themselves to the tasks to satisfy the demand vector. We study the dynamic version of the problem where the demand vector changes over time. Here, the goal is to minimize the switching cost, which is the number of agents that change tasks in response to a change in the demand vector. The switching cost is an important metric since changing tasks may incur significant overhead. We study a mathematical formalization of the above problem introduced by Su, Su, Dornhaus, and Lynch [Su et al., 2017], which can be reformulated as a question of finding a low distortion embedding from symmetric difference to Hamming distance. In this model it is trivial to prove that the switching cost is at least 2. We present the first non-trivial lower bounds for the switching cost, by giving lower bounds of 3 and 4 for different ranges of the parameters. 

   more » « less