Multi-robot Systems: Modeling Swarm Dynamics and Designing Inspection Planning Algorithms

Citation

Williams, Kjerstin Irja (2006) Multi-robot Systems: Modeling Swarm Dynamics and Designing Inspection Planning Algorithms. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/G1T2-FB74. https://resolver.caltech.edu/CaltechETD:etd-05192006-063455

Abstract

For a variety of applications, the capability of simultaneous sensing and action in multiple locations that is inherent to multi-robot approaches offers potential advantages over single robot systems in robustness, efficiency, and application feasibility.

At the fully distributed and reactive end of the multi-robot system spectrum, I present mathematical modeling methodologies developed to predict and optimize a self-organized robotic swarm’s performance for several tasks. These models allow us to better understand the relationship between agent and group behavior by capturing the dynamics of these highly stochastic, nonlinear, asynchronous systems at various levels of abstraction, in some cases even achieving mathematical tractability. The models deliver qualitatively and quantitatively correct predictions several orders of magnitude more quickly than an embodied simulator can. Swarm modeling lays the foundation for more generalized SI system design methodology by saving time, enabling generalization to different robotic platforms, and estimating optimal design and control parameters.

In considering more complex target tasks and behaviors, efficiency and completeness of execution may be of concern, and a swarm approach may not be appropriate. In such cases a more deliberative approach may be warranted. In that context, I introduce the multi-robot boundary coverage problem, in which a group of robots is required to completely inspect the boundary of all two-dimensional objects in a specified environment. To make such a guarantee, I present a centralized planning approach that constructs a two-component abstraction of the problem: a graph representing the particular instance of the inspection task and a graph problem whose solution represents a complete plan for inspection. Using the building blocks of this approach, related inspection tasks that require the robotic system to adapt to a changes in team size and task assignment are also explored. The application of these planning methods to the case of long-term deployment for surveillance applications that require repetitive coverage is also discussed.

The recurring theme of this thesis is that we must look beyond implementation and validation of a particular system and ask how its design can contribute to the development of a more general design methodology.

Thesis Files