Voxelized Cut-and-Fill Models for Deadlock-Free Site Excavation Under Accessibility Constraints

The Cut-and-Fill Problem (CFP) is about the excavation and relocation of earth material in an optimal manner from one location (the Cut) to another (the Fill). The cut- and fill volumes are partitioned into equinumerous, identical, volumetric elements, or voxels. The relocation task can be decomposed to several subtasks, where a cut-voxel is assigned a corresponding voxel in the fill. The cost associated with each subtask could reflect the effort it takes to transport the cut-voxel to its intended destination. The CFP is modeled as a Linear Assignment Problem (LAP) with additional constraints that arise in the context of earth-moving. These constraints concern positional requirements that must be satisfied when moving soil volume-elements (voxels). For instance, the earthmoving activity cannot access voxels that are surrounded by other voxels. These inaccessible voxels can only be moved after some of its neighbors have been removed. An assignment of cut-to-fill voxels proceeds towards completion in waves. Each wave consists of a set of accessible cut-voxels relocated to (an equinumerous) set of accessible fill-voxels. A new set of accessible voxels result from the completion of a wave, and it is followed by the next wave, and the process repeats as often as necessary. If this process results in a situation where every accessible cut-voxel is assigned to some inaccessible fill-voxel, we have a deadlock. There can be no progress following a deadlock. This paper presents a sufficient condition on the cut- and fill-set geometries that guarantee the existence of a deadlock-free solution for a CFP-instance. Following this, we present a collection of results on deadlock-free solutions for CFP-instances whose cut- and fill-set geometries cannot guarantee deadlock-freedom.