More Like this

1. Response thresholds generalize across problem instances for a deterministic response multiagent system

   Mathias, H. David; Wu, Annie S.; and Dang, Daniel (January 2021, Proceedings of the Genetic and Evolutionary Computation Conference)

   null (Ed.)

   In this work, we use a multiobjective genetic algorithm to evolve agent response thresholds for a decentralized swarm and demonstrate that swarms with evolved thresholds outperform swarms with thresholds set using other methods. In addition, we provide evidence that the effectiveness of evolved thresholds is due in part to the evolutionary process being able to find, not just good distributions of thresholds for a given task across all agents, but also good combinations of thresholds over all tasks for individual agents. Finally, we show that thresholds evolved for some problem instances can effectively generalize to other problem instances with very different task demands. 

   more » « less
2. Dynamic response thresholds: heterogeneous ranges allow specialization while mitigating convergence to sink states

   Wu, Annie S.; Mathias, H. David (January 2020, Proceedings of the 12th International Conference on Swarm Intelligence)

   null (Ed.)

   We argue that heterogeneous threshold ranges allow agents in a decentralized swarm to effectively adapt thresholds in response to dynamic task demands while avoiding the pitfalls of positive feedback sinks. Dynamic response thresholds allow agents to dynamically evolve specializations which can improve the responsiveness and stability of a swarm. Dynamic thresholds that adapt in response to previous experience, however, are vulnerable to getting stuck in sink states due to the positive feedback nature of such systems. We show that heterogeneous threshold ranges result in comparable task allocation and improved stability as compared to homogeneous threshold ranges, and that simple static random thresholds should be considered in situations where agent resources are plentiful. 

   more » « less
3. Thompson Sampling for Robust Transfer in Multi-Task Bandits

   Wang, Z.; Zhang, C.; Chaudhuri, K. (January 2022, Proceedings of the 39th International Conference on Machine Learning)

   We study the problem of online multi-task learning where the tasks are performed within similar but not necessarily identical multi-armed bandit environments. In particular, we study how a learner can improve its overall performance across multiple related tasks through robust transfer of knowledge. While an upper confidence bound (UCB)-based algorithm has recently been shown to achieve nearly-optimal performance guarantees in a setting where all tasks are solved concurrently, it remains unclear whether Thompson sampling (TS) algorithms, which have superior empirical performance in general, share similar theoretical properties. In this work, we present a TS-type algorithm for a more general online multi-task learning protocol, which extends the concurrent setting. We provide its frequentist analysis and prove that it is also nearly-optimal using a novel concentration inequality for multi-task data aggregation at random stopping times. Finally, we evaluate the algorithm on synthetic data and show that the TS-type algorithm enjoys superior empirical performance in comparison with the UCB-based algorithm and a baseline algorithm that performs TS for each individual task without transfer. 

   more » « less
4. The Online Knapsack Problem with Departures

   https://doi.org/10.1145/3570618  

   Sun, Bo; Yang, Lin; Hajiesmaili, Mohammad; Wierman, Adam; Lui, John C.; Towsley, Don; Tsang, Danny H.K. (December 2022, Proceedings of the ACM on Measurement and Analysis of Computing Systems)

   The online knapsack problem is a classic online resource allocation problem in networking and operations research. Its basic version studies how to pack online arriving items of different sizes and values into a capacity-limited knapsack. In this paper, we study a general version that includes item departures, while also considering multiple knapsacks and multi-dimensional item sizes. We design a threshold-based online algorithm and prove that the algorithm can achieve order-optimal competitive ratios. Beyond worst-case performance guarantees, we also aim to achieve near-optimal average performance under typical instances. Towards this goal, we propose a data-driven online algorithm that learns within a policy-class that guarantees a worst-case performance bound. In trace-driven experiments, we show that our data-driven algorithm outperforms other benchmark algorithms in an application of online knapsack to job scheduling for cloud computing. 

   more » « less
5. Hybrid ACO for Blockchain-Managed Robotic Swarms*

   https://doi.org/10.1109/UR65550.2025.11078059  

   Mallikarachchi, Sanjaya; Abizov, Nuralem; T, Amanzhol Bektemessov; Ibrayev, Aidos; Vitharana, Sandun S; Godage, Isuru S (June 2025, IEEE)

   We present a dynamic multi-robot mapping framework that combines Blockchain technology for swarm management with a Hybrid Ant Colony Optimization (HACO) algorithm for path planning. Blockchain-based swarm contracts enable decentralized, transparent, and secure task allocation, acceptance, tracking, and reward distribution among multiple robots. HACO facilitates efficient path planning in complex environments through cooperative and competitive strategies. We deploy multiple LiDAR-equipped Unitree Go2 dog robots to collaboratively and competitively map divided sub-areas, with task reassignment based on real-time feedback and the selected strategy. In cooperative mode, robots share data to boost efficiency and accuracy; in competitive mode, they work independently to reduce redundancy and optimize resources. Swarm contracts also verify full sub-area coverage via the merged map. Results show that integrating blockchain-based management with HACO significantly enhances mapping performance, delivering a robust and scalable solution for realworld multi-robot systems. 

   more » « less