Abstract: We introduce a new model for cooperative agents that seek to optimize a common goal without communication or coordination. Given a universe of elements V, a set of agents, and a set function f, we ask each agent i to select a subset S_i ⊂ V such that the size of S_i is constrained (i.e., |S_i| < k). The goal is for the agents to cooperatively choose the sets Si to maximize the function evaluated at the union of these sets, U_i S_i; we seek max f(U_i S_i). We assume the agents can neither communicate nor coordinate how they choose their sets. This model arises naturally in many real-world settings such as swarms of surveillance robots and colonies of foraging insects. Even for simple classes of set functions, there are strong lower bounds on the achievable performance of coordinating deterministic agents. We show, surprisingly, that for the fundamental class of submodular set functions, there exists a near-optimal distributed algorithm for this problem that does not require communication. We demonstrate that our algorithm performs nearly as well as recently published algorithms that allow full coordination.
Story of Contribution: With my team, I developed two novel algorithms: Greedy-Sampling and Adaptive-Sampling and proved their approximation ratios. I implemented both algorithms in MATLAB and later parallelized them to reduce their runtime. To test these algorithms, I first selected seven large data sets from DBpedia, which represented subgraphs from Wikipedia, with varying graph properties. Then I ran both Greedy-Sampling and Adaptive-Sampling on these graphs alongside algorithms that either allowed communication between agents or allowed for a central planner to coordinate agents. The expected reward over multiple instances were computed and then compared.
Lessons Learned: Beyond the opportunity to explore new computing topics, such as optimization and mult-iagent systems, or to learn new tools such as MATLAB, this project allowed me to gain critical research skills. By collaborating with two professors and two graduate students, and by continuing to work on this project at my home institution for a semester, I learned to work as part of a team, even from a remote location. Simultaneously, I learned to work independently as I led the experimental portion of the project.
The project itself taught me to consider both the proven theoretical bounds as well as the real world performance of algorithms. And by leading the experiments portion of the project, I gained experience in choosing datasets that address the average case as well special cases in which the algorithms could perform in exceptional ways. When selecting previously published algorithms to test against, I gained experience in finding and analyzing literature.
Finally, by presenting my work at multiple venues, applying for travel grants, and drafting and revising a paper for publication, I learned to communicate my methods and results both to the scientific community and the general public.
Presenting at the Washington University in St. Louis NSF REU Poster Session.