UC San Diego

Due to recent technological advances, robotic swarms are currently a large

interest for surveillance, disaster response, and exploration. In order to solve this

problem, we develop distributed deployment strategies for 1.5D and 2.5D polyhedral

terrains that are inuenced by research in computational geometry, graph theory,

and distributed controls. Similarly to the guarding of art gallery problems, we guard

an environment through the collective visibility of a team of robots. We consider

scenarios where the robots are constrained to moving on the ground in 1.5D and 2.5D

polyhedral terrains. Our objective is to determine strategies for deploying robots in polyhedral terrains that guarantees complete visibility of the terrain.

In the 1.5D polyhedral terrain, we determine a set of locations, that guarantees

that the terrain is completely visible when occupied. We then develop a set

of instructions that each robot distributively executes in order to occupy the set of

locations. Finally, we nd a closed-form expression for the time required for the 1.5D

deployment strategy to complete that scales with the size of the terrain.

In the 2.5D polyhedral terrain, we develop a set of instructions for the robots to

follow that collectively explores, colors, and guards the polyhedral terrain. We dene

rules for the agents to label certain locations that must be occupied in order to achieve

complete visibility, inspired by coloring of planar graphs. Finally, we characterize the

best and worse time complexity for the algorithm