Global Path Planning Approaches for Material Movements in a Worksite

In various environments (e.g., manufacturing shopfloors, civil engineering construction sites, space) there is an increasing need to efficiently transport objects from locations to other locations. Although most practical material transportation robotic system built so far have been quite primitive, we believe that in many areas one can significantly gain in efficiency, reliability and flexibility by automatically planning the motions of the transportation devices. While process planning provides a high-level 'logical' and possibly 'temporal' specification of material movements, motion planning says how these movements are to be 'physically' carried out. Thus, motion planning is the natural intermediate stage between process planning and task execution. In this paper, we survey techniques for planning mobile robot paths among obstacles, which have been developed over the last few years. We focus on the so-called 'global' techniques. We describe in detail the three most common approaches, which are based on the notions of cell decomposition, free space retraction, and visibility graph, respectively. Within the first two approaches, we survey both the so-called exact and approximate techniques. Although this paper is far from exploring all the facets of motion planning, it gives a fundamental and detailed presentation of issues, which are of general interest to all motion planning problems. These issues are likely to be of prime importance in future material transportation systems.