Aspects of the disclosure relate to delivery systems including unmanned aerial vehicles (UAVs). For instance, a UAV may have one or more computing devices. These computing devices may be configured to receive sensor data for a predetermined delivery area and use the sensor data to identify one or more grid cells of a grid corresponding to a map of the predetermined delivery area. The identified grid cells correspond to locations acceptable for delivery by the UAV. The computing devices may also be configured to receive, from a mobile receptacle unit (MRU), information identifying a set of grid cells of the grid identified by the MRU as being acceptable for delivery, determine a delivery location by identifying a common grid cell between the identified one or more grid cells and the set of grid cells, and send the common grid cell to the MRU in order to attempt a delivery.