Extending the VGRAPH algorithm for robot path planning

Abstract

This paper presents an O(nlogm) method to incorporate start and goal points of a
\nrobot into the roadmap of a two-dimensional workspace to form a VGRAPH. A VGRAPH
\nPoint Incorporation Algorithm(VPIA) incorporates a point in free-space into a
\nroadmap. This VPIA divides the free space around an obstacle vertex into an
\nordered set of areas. A search is used to determine the containment of the point.
\nContainment implies visibility of the point from the vertex. A point is
\nincorporated by determining its visibility from all obstacle vertices. The VPIA is
\ninherently parallel and the implementation can reduce this complexity from
\nO(nlogm) to O(logm). Most existing techniques for incorporating points into a
\nroadmap perform in O(n2). The roadmap's data structure is modified to support the
\nVPIA. The VPIA, employing the VGRAPH approach should enhance the worst case
\nruntime of find-path algorithms closer to real-time for 2-D workspaces cluttered
\nwith obstacles. Sample VGRAPH diagram generated by an implementation of the VPIA
\nis shown in Appendix A.