Variants of the Quantized Visibility Graph for Efficient Path Planning

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...

Full description

Saved in:
Bibliographic Details
Published in:Advanced robotics 2011-01, Vol.25 (18), p.2341-2360
Main Authors: Kim, Jungtae, Kim, Munsang, Kim, Daijin
Format: Article
Language:English
Subjects:
ADAPTIVE CELL DECOMPOSITION
Algorithms
Boundaries
Computational efficiency
FIXED CELL DECOMPOSITION
Graphs
Obstacles
PATH PLANNING
QUANTIZED VISIBILITY GRAPH
Representations
Visibility
VISIBILITY GRAPH
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0169-1864
1568-5535
DOI:10.1163/016918611X603855