A Caltech Library Service

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


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.


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.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:coverage; inspection; postman problem; surveillance; swarm
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Burdick, Joel Wakeman (advisor)
  • Martinoli, Alcherio (advisor)
Thesis Committee:
  • Burdick, Joel Wakeman (chair)
  • Martinoli, Alcherio
  • Perona, Pietro
  • Murray, Richard M.
  • Abu-Mostafa, Yaser S.
Defense Date:5 May 2006
Record Number:CaltechETD:etd-05192006-063455
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1876
Deposited By: Imported from ETD-db
Deposited On:30 May 2006
Last Modified:06 May 2020 22:30

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page