As a result of recent advances in computation, communication, sensor, and actuator technology, it is now possible to build teams of hundreds of small and inexpensive ground, air, and underwater robots. They are light, easy to transport and deploy, and can fit into small places. Such swarms of autonomous agents provide increased robustness to individual failures, the possibility to cover wide regions, and improve computational power through parallelism. However, planning and controlling such large teams of agents with limited communication and computation capabilities is a difficult problem that received a lot of attention in the past decade. To accommodate large numbers of robots with nontrivial kinematics or dynamics moving in complicated environments, this project proposes hierarchical abstractions. At a lower level, continuous abstractions reduce the dimension of the problem by extracting a set of essential features of the swarm, while correctly capturing the robot constraints. At a higher level, discrete abstractions focus on the complexity of the environment and map the planning and control problem from the infinite dimensional world of continuous systems to the decidable world of finite state automata. The proposed algorithms lead to the development of HILLS, a High Level Specification Language for Swarms, and LARAD, a LAnguage for Robot Automated Deployment. In these frameworks, robotic motion plans are formulated in a high level language in terms of strings or temporal logic formulas in the language of a discrete system capturing the complexity of the environment. HILLS and LARAD are implemented as simulation packages and also used in experimental platforms for swarming robotics. While aimed to providing a solution to the swarming problem, this project addresses fundamental issues in shape theory and the well-known "n-body problem," which are traditionally studied in theoretical physics and find applications in areas such as atomic physics and celestial mechanics. On the other hand, using a unique approach to discrete abstractions, this work attempts to enlarge the class of known decidable continuous and hybrid systems. Finally, the hierarchical abstraction architectures of this project open a new direction in planning and control of mobile robots by creating a framework in which powerful discrete algorithms dealing with the complexity of the environment can be seamlessly combined with continuous control laws for nontrivial robot dynamics. This research is highly interdisciplinary, covering topics ranging from traditionally "continuous" areas, such as geometric nonlinear control, to "discrete" areas such as formal analysis, as well as application areas at the boundary between robotics and biology. The educational plan is focused on building bridges among the above areas by introducing graduate and undergraduate courses on Hybrid Systems, Systems Biology, Geometric Planning and Control, and Bioinformatics. It also involves a rich spectrum of outreach activities, including mentoring of high school teachers, judging and advising high school students participating in robotics competitions, and mentoring under-represented minority undergraduate students.
