Florida Atlantic University (FAU) and Carnegie Mellon University (CMU) are pleased to cooperate in a three-year program of research on autonomous underwater robots. The use of remotely controlled, tethered underwater vehicles to routinely perform critical underwater tasks in offshore and ocean situations has clearly demonstrated both the utility and importance of these systems. Recent developments in autonomous vehicle and robot technology now form the basis for projecting that significant expansions are possible in the capabilities of underwater vehicles and robotics. The technologies involved are wide ranging and include sensors, controls, power, computing, architectures and data representation. The coordinated research program will focus on map-based knowledge representation to directly address several of these central issues of autonomous underwater vehicles. We will develop methods to build, store, and use the knowledge that autonomous vehicles need to execute useful missions. Specifically, we will develop "annotated maps", which index information to particular objects and locations in the map. The annotations can be used for a wide variety of purposes: describing objects, providing hints for perception or control, or specifying particular actions to be taken. We will provide a query mechanism to retrieve annotations based on their map locations. We will also build "triggers", which will cause a specified message to be delivered to a particular process when the vehicle reaches a given location in the map. These annotated maps will serve a crucial role in enabling missions that are currently beyond the reach of autonomous systems.