"Performance Prediction for Hub-Based Swarms" by Puneet Jain

Abstract

Optimization problems lie at the core of improving performance in various tasks, ranging from day-to-day work scheduling to coordinating robots in a warehouse fulfillment center. Distributed swarm systems provide a robust and adaptive solution approach to many optimization problems. Instead of using one really sophisticated agent, multiple smaller less sophisticated agents can provide the flexibility to evaluate more options and still provide a "good" answer. This dissertation uses graphs to model, analyze, and simulate swarm behavior, primarily to predict the time-to-converge (TTC) and success probability. First, we use a bipartite model for the distributed best-of-N problem, and show how the model can be represented as a Discrete Time Markov Chain (DTMC). Second, we analyze useful theoretical properties of DTMCs, and parameters from DTMCs are tuned to mimic behavior in existing agent-based simulations, enabling more precise analysis of these algorithms and verifying the usefulness of the graph-based abstraction. We then use Graph Neural Networks to take these DTMCs as input and learn the structure of the graphs. These structures allow us to see relationships between different states of the swarm, like the success or the failure state. The performance of these graph neural networks is then analyzed for classification tasks, specifically whether the swarm is slow or fast, and how successful the swarm is likely to be. We see that inductive learning on efficiently sampled ABMs can lead to high F1 scores on performance classification.

Degree

PhD

College and Department

Computational, Mathematical, and Physical Sciences; Computer Science

Rights

https://lib.byu.edu/about/copyright/

Date Submitted

2024-12-16

Document Type

Dissertation

Handle

http://hdl.lib.byu.edu/1877/etd13483

Keywords

swarms, best-of-N, graphs, neural networks

Language

english

Share

COinS