Coordinated motion planning: the warehouseman's problem with constraints on free space
Rajeev Sharma, Yiannis Aloimonos · IEEE Transactions on Systems Man and Cybernetics · 1992
The warehouseman's problem, namely, the coordinated motion planning for multiple independent objects confined in a room, is addressed. Several constraints are presented under which the problem becomes tractable, and polynomial time algorithms that guarantee a coordinated rearrangement under the given conditions are obtained. The concept of temporary storage space (TSS) is introduced as a general way of constraining free space. Each algorithm presented has a different set of constraints on the possible sizes and/or relative placements of the square blocks. For each case, an adequate TSS is proposed that guarantees rearrangement of n blocks through algorithms having O(n/sup 2/) running time. The practical utility of the presented techniques is also discussed in the light of the complexity of motion coordination.>