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.
As a result of tremendous advances in computation, communication, sensor, and actuator technology, it is now possible to build teams of hundreds and even thousands 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 robots provide increased robustness to individual failures, the possibility to cover wide regions, and improved computational power through parallelism. However, planning and controlling such large teams of agents with limited communication and computation capabilities is a very difficult problem that received a lot of attention in the past two decades. It is currently believed that inspiration should be taken from the behavior of biological systems such as flocks of birds, schools of fish, swarms of bees, or crowds of people. Researchers from several areas, including biology, social sciences, physics, and computer graphics tried to understand how local interaction rules in distributed multi-agent systems can produce emergent global behavior. Even though in some interesting convergence results have been established, the fundamental questions still remain to be answered. What is a good description that captures the essential features of a large group? How do we plan its behavior? How can we prove that it satisfies given safety properties? How can we generate provably correct control laws for each agent so that a desired group behavior is achieved? In order to answer the above questions, in this project we developed an interdisciplinary research and educational plan centered at coordination and control of distributed multi-agent systems. The theory developed in this completed project exploits the interplay between the "continuous" world of geometric nonlinear control and the traditionally "discrete" world of formal analysis. In this framework, robotic swarms can be automatically deployed from rich, high level, temporal logic specifications over a set of "essential" features of the swarm such as its centroid, shape, and orientation. We also developed a top down approach in which control and communication strategies for a robotic team can be generated from specifications given as general temporal logic statements about servicing requests in an environment (see attached figure of the Robotic Urban-Like Environment (RULE)). This project involved a rich educational and outreah plan, ranging from the development of graduate classes to the involvement of minorities and outreach students in research. In particular, we developed a freshman class on robotics, which covers basic concepts in mobile robotics such as actuation, sensing, motion planning, and control. A relatively small class (16 students) was divided into four teams competing for the grand challenge: using an-off-the-shelf robotic kit, build and program a robot to reach a light source in an environment cluttered with obstacles. For most students, this was their first contact with robotics, and for more than half of them, the first introduction to programming. As part of Research Experience for Teachers (RET) and Research Experience for Undergraduates (REU) programs, we mentored high school teachers and students in the area of robotics. We were involved in several regional robotics competions.
