Title:	Extending the VGRAPH algorithm for robot path planning
Authors:	Tokuta, Alade
Citation:	Journal of WSCG. 1998, vol. 6, no. 1-3.
Issue Date:	1998
Publisher:	Václav Skala - UNION Agency
Document type:	článek article
URI:	http://hdl.handle.net/11025/15849
ISSN:	1213-6972 (print) 1213-6980 (CD-ROM) 1213-6964 (online)
Keywords:	viditelný graf;plánování cesty;VGRAPH
Keywords in different language:	visibility graph;path planning;VGRAPH
Abstract in different language:	This paper presents an O(nlogm) method to incorporate start and goal points of a robot into the roadmap of a two-dimensional workspace to form a VGRAPH. A VGRAPH Point Incorporation Algorithm(VPIA) incorporates a point in free-space into a roadmap. This VPIA divides the free space around an obstacle vertex into an ordered set of areas. A search is used to determine the containment of the point. Containment implies visibility of the point from the vertex. A point is incorporated by determining its visibility from all obstacle vertices. The VPIA is inherently parallel and the implementation can reduce this complexity from O(nlogm) to O(logm). Most existing techniques for incorporating points into a roadmap perform in O(n2). The roadmap's data structure is modified to support the VPIA. The VPIA, employing the VGRAPH approach should enhance the worst case runtime of find-path algorithms closer to real-time for 2-D workspaces cluttered with obstacles. Sample VGRAPH diagram generated by an implementation of the VPIA is shown in Appendix A.
Rights:	© Václav Skala - UNION Agency
Appears in Collections:	Volume 6, number 1-3 (1998)

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.