Embodiments of the present invention provide methods and systems for ensuring that mobile robots are able to detect and avoid positive obstacles in a physical environment that are typically hard to detect because the obstacles do not exist in the same plane or planes as the mobile robot's horizontally-oriented obstacle detecting lasers. Embodiments of the present invention also help to ensure that mobile robots are able to detect and avoid driving into negative obstacles, such as gaps or holes in the floor, or a flight of stairs. Thus, the invention provides positive and negative obstacle avoidance systems for mobile robots.