Abstract:
Algorithms for the control and monitoring of swarms of moving agents are important in a wide variety of real and virtual applications such as crowd control, livestock herding, and decentralized robot control architecture. In the presence of obstacles, these applications can be quite difficult, especially with large swarms. This thesis presents reusable and robust motion planning algorithms for the swarm control problem of shepherding, a task involving using a small set of mobile robots interact with a larger set of swarm agents; and the swarm monitoring problem of visibility-based pursuit, a task involving using a mobile robot to follow and maintain visibility of a moving swarm. For both problems, we developed algorithms to efficiently sample reusable geometric information in the environment to enable fast online planning and replanning. For the shepherding problem, we discuss several representations and abstractions for flocks to improve scalability and robustness to uncertainty. For the visibility-based pursuit problem, we discuss several methods for space decomposition that enable fast online planning to achieve visibility objectives. We validate our results with multi-agent simulation software to understand the tradeoffs between different techniques for these problems.
