Journal
ADVANCED ROBOTICS
Volume 25, Issue 18, Pages 2341-2360Publisher
TAYLOR & FRANCIS LTD
DOI: 10.1163/016918611X603855
Keywords
Path planning; fixed cell decomposition; adaptive cell decomposition; visibility graph; quantized visibility graph
Categories
Funding
- Ministry of Knowledge Economy, Korea [NIPA-2010-C7000-1001-0006]
- Intelligent Robotics Development Program, one of the 21st Century Frontier RD Programs
- Ministry of Commerce, Industry and Energy
Ask authors/readers for more resources
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
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available