Over the past decades we have seen robots move from constrained and heavily designed industrial environments out into the world. Along with this shift there is a need for smaller, safer, and less expensive robots which can complete tasks autonomously in teams, sometimes covering large areas. Multi-robot teams can expand the capabilities of a single robot, however working with teams presents its own set of challenges. Robots must be able to reach a shared understanding of their task as well as gracefully recover from single member failures, often while having no centralized coordination.

In many task assignment and coordination applications, it is assumed that the robots begin with a shared understanding of the environment, often in the form of a map. In small application spaces, such maps could be made by hand, but in the case of large or potentially hazardous environments, it will be necessary to have the robots themselves create the map. To this end, in this thesis we present two map representations designed specifically for autonomous mapping by robots with high-noise sensors. For each method, we develop an information theoretic value function which can be used to autonomously maximize the information gained about the map. This is a principled approach which accounts for both information gained by exploring new areas, as well as information gained by further inspection of the existing map to account for sensor uncertainty.

Additionally, in applications where inexpensive robots are operating autonomously in large and potentially hazardous areas, the likelihood increases that a robot on the team can become non-cooperative, either through unintentional damage or through tampering. To be able to autonomously cooperate as a team it is important that the system can recover gracefully from such failures. Consensus algorithms are ubiquitous in distributed systems as they provide a mechanism for reaching agreement within a team using only local communications. We extend a highly distributed approach to resilient consensus for static networks to applications with multi-robot teams. This approach has been largely limited to small static networks because verification that the network is sufficiently connected is formally hard. First we develop a method which can be used for teams with time-varying range-based communication which is suitable for tasks where robots are not required to spread out in the environment. We then present a method that is well suited to mapping and coverage applications which uses a well known communication structure to guarantee successful resilient consensus.

The methods presented in this thesis lay the groundwork for a class of resilient active information gathering algorithms which can be used for low cost teams. Such algorithms have wide ranging applicability, from persistent monitoring tasks such as those found in agriculture to time critical tasks such as search and rescue.