Název:	Extending the VGRAPH algorithm for robot path planning
Autoři:	Tokuta, Alade
Citace zdrojového dokumentu:	Journal of WSCG. 1998, vol. 6, no. 1-3.
Datum vydání:	1998
Nakladatel:	Václav Skala - UNION Agency
Typ dokumentu:	článek article
URI:	http://hdl.handle.net/11025/15849
ISSN:	1213-6972 (print) 1213-6980 (CD-ROM) 1213-6964 (online)
Klíčová slova:	viditelný graf;plánování cesty;VGRAPH
Klíčová slova v dalším jazyce:	visibility graph;path planning;VGRAPH
Abstrakt v dalším jazyce:	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.
Práva:	© Václav Skala - UNION Agency
Vyskytuje se v kolekcích:	Volume 6, number 1-3 (1998)

Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.