PLANNING SHORTEST PATHS AMONG 2D AND 3D WEIGHTED REGIONS USING FRAMED-SUBSPACES

The standard shortest path planning problem determines a collision-fre e path of shortest distance between two distinct locations in an envir onment scattered with obstacles. This problem, in:fact, corresponds to a special case of the weighted region problem, in which the environme nt is partitioned into a set of regions, with some regions (obstacles) having an associated weight of infinity and other regions (free space ) having a weight of 1. For the general weighted region problem, the e nvironment consists of regions, each of which is associated with a cer tain weight factor A path through the weighted region incurs a cost th at is determined by the geometric distance of the path in that region times that region's weight factor. The weighted region problem can be used to model path planning for autonomous vehicles over different env ironmental terrains. This paper studies the problem of computing a sho rtest path between two distinct locations through a 2D or 3D environme nt consisting of weighted regions. The authors propose a novel cell de composition approach based on new framed-subspace data structures: the weighted framed-quadtree and the weighted framed-octree.