Methods and apparatus related to autonomous vehicles (AVs) are provided. A mapping can be determined that tiles an environment having an AV using a plurality of cells; each cell having an environmental status. While the AV is in the environment: status data can be received relating to a location of the AV and obstacles at that location; environmental status for a cell can be updated based on the status data; a value for each cell can be determined based on the cell's environmental status; a waypoint of a coverage path that covers a region in the environment and is based on the AV's location can be determined; a determination whether the waypoint is reachable from the AV's location can be made; after determining that the waypoint is reachable, a command based on the mapping can be sent directing the AV toward the waypoint; and the waypoint can be updated.