Spatial autonomy enables autonomous agents to interact with the environment intelligently and smoothly. This dissertation considers two particular scenarios to realize and improve the spatial autonomy for robots. In the first scenario, the cooperation among multiple robots to localize themselves is studied. I propose a new multirobot localization algorithm with observation and communication steps separated. This algorithm uses far less communication than other algorithms, which improves the efficiency and robustness. I furthermore develop a framework to optimize the observation and communication rates of the algorithm. I also study an online solution for simultaneous localization and mapping (SLAM). Current SLAM algorithms solve the trajectory and the map via an optimization problem, especially after loop closure. However, these algorithms are offline, whose computational cost increases significantly with time. Instead, we formulate the SLAM problem as an inference problem over a hidden Markov model, and this structure allows an online implementation. Therefore, the comparable accuracy can be achieved with far less computation. Both scenarios show more efficient spatial autonomy algorithms for robots when the information usage is carefully designed, and pave a way for robots with stronger autonomy.