Many mobile robot applications require robots to act safely and intelligently in complex unfamiliarenvironments with little structure and limited or unavailable human supervision. As arobot is forced to operate in an environment that it was not engineered or trained for, various aspectsof its performance will inevitably degrade. Roboticists equip robots with powerful sensorsand data sources to deal with uncertainty, only to discover that the robots are able to make onlyminimal use of this data and still find themselves in trouble. Similarly, roboticists develop andtrain their robots in representative areas, only to discover that they encounter new situations thatare not in their experience base. Small problems resulting in mildly sub-optimal performance areoften tolerable, but major failures resulting in vehicle loss or compromised human safety are not.This thesis presents a series of online algorithms to enable a mobile robot to better deal withuncertainty in unfamiliar domains in order to improve its navigational abilities, better utilizeavailable data and resources and reduce risk to the vehicle. We validate these algorithms throughextensive testing onboard large mobile robot systems and argue how such approaches can increasethe reliability and robustness of mobile robots, bringing them closer to the capabilitiesrequired for many real-world applications.