We describe localization-space trails (LOST), a method that enables a team of robots to navigate between places of interest in an initially unknown environment using a trail of landmarks. The landmarks are not physical; they are waypoint coordinates generated online by each robot and shared with teammates. Waypoints are specified in each robot's local coordinate system, and contain references to features in the world that are relevant to the team's task and common to all robots. Using these task-level references, robots can share waypoints without maintaining a global coordinate system. The method is tested in a series of real-world multirobot experiments. The results demonstrate that the method: 1) copes with accumulating odometry error; 2) is robust to the failure of individual robots; 3) converges to the best route discovered by any robot in the team. In one experiment, a team of four autonomous mobile robots performs a resource transportation task in our uninstrumented ofrice building. Despite significant divergence of their local coordinate systems, the robots are able to share waypoints, forming and following a common trail between two predetermined locations for more than three hours, traveling a total of 8.2 km (5.1 miles) before running out of power. Designed to scale to large populations, LOST is fully distributed, with low costs in processing, memory, and bandwidth. It combines metric data about the position of features in the world with instructions on how to get from one place to another; producing something between a map and a plan. [ABSTRACT FROM AUTHOR]