Abstract: We will discuss the classical Art Gallery Problem first proposed by Klee in 1973 from a mobile multi-agents perspective. Specifically, we require an optimally small number of agents (also called guards) to navigate and position themselves in the interior of an unknown simple polygon with n vertices such that the collective view of all the agents covers the polygon. We consider the visibly connected setting wherein agents must remain connected through line-of-sight links -- a requirement particularly relevant to multi-agent systems.

We will first discuss a centralized algorithm for the visibly connected setting that runs in time O(n), which is of course optimal. We will then discuss algorithms for two different distributed settings. In the first setting, agents can only perceive relative proximity (i.e., can tell which of a pair of objects is closer) whereas they can perceive exact distances in the second setting. Our distributed algorithms work despite agents having no prior knowledge of the polygon. Furthermore, we will discuss lower bounds to show that our distributed algorithms are near-optimal.