Variants of the Quantized Visibility Graph for Efficient Path Planning

Abstract

We propose variants of the quantized visibility graph (QVG) for efficient path planning. Conventional visibility graphs have been used for path planning when the obstacles are polygonal. The QVG extends its usability to arbitrarily-shaped objects by representing the obstacles as polygons. We propose QVG variants which represent all combinations of three factors, each with two alternatives: (i) quantization level (fixed-level or multiple-level), (ii) object representation method (inner and boundary cells together or boundary cells only), and (iii) methods used to check whether pairs of points are mutually visible (rotational plane sweep algorithm or sign inequality discrimination (SID) algorithm). In the verification of the efficiency of the proposed QVGs, (i) all QVGs produced the same best path, which was shorter than the convectional algorithms, (ii) computational cost to find the shortest path is lower when using QVGs than when using the convectional algorithms and (iii) the QVG that uses multi-level quantization, partial obstacle representation and SID visibility checking provides the shortest best path and has lower computational cost than all other methods. (C) Koninklijke Brill NV, Leiden and The Robotics Society of Japan, 2011