An autonomous mobile device (AMD) moves through a physical space without human intervention. Data from sensors on the AMD is used to determine an occupancy map indicative of obstacles and their locations in the physical space. Obstacles may be static, variable, or dynamic. For example, walls are static, doors which open and close are variable, and people moving through the environment are dynamic. Regions in the occupancy map that the AMD has visited but which are shown by the occupancy map as containing obstacles are identified as being variable regions. To determine possible paths through the physical space during autonomous movement, the variable regions are considered to be unoccupied by obstacles and traversable. Information about how often the variable region transitions between traversable and impassible states may also be used to determine the possible paths.