Geometric algorithms for analyzing and controlling swarms of robots and groups of aircraft.

摘要

The first two parts of the dissertation focuses on the dispersion problem of robot swarms: Given an unknown environment, expand a swarm of robots in the environment such that the area of the environment visible to the robots is maximized, while the swarm remains connected.; We first discuss the dispersion problem in the case where robots move along discrete directions, then propose and compare different algorithms in the case of continuous movement. In both cases the robots are assumed to have limited capabilities of sensing, communicating, and computing.; In the discrete dispersion, the swarm is initially outside the environment and robots enter the environment through multiple doors. We proposed optimal algorithms for the case where at most one robot can enter the environment at any time. When there can be multiple robots enter the doors, we proposed an algorithm that completes dispersion in a log factor time compared to the offline optimal situation. We also provide a matching lower bound for any algorithm using strictly local information.; In the continuous dispersion, the robots start as a dense swarm that is placed somewhere inside the environment. We propose and compare different algorithms with various performance metrics through simulation. These algorithms assume no direct communications among robots and all moving decisions are made strictly from gathered sensory information.; The last part of the dissertation studies an airplane rerouting problem: The airspace is often partially blocked by some hazardous weather and airplanes can only fly using the remained safe region. We would like to efficiently utilize the flyable region to minimize the number of flights that may be canceled due to the weather situation. We compare the performance of free flight resolution and another method using organized flow of flights.