Accelerating Graph-based Path Planning Through Waypoint Clustering

Wardhana, Nicholas Mario; Johan, Henry; Seah, Hock-Soon

Accelerating Graph-based Path Planning Through Waypoint Clustering

Files

059-063.pdf (947.32 KB)

Date

2015

Authors

Wardhana, Nicholas Mario
Johan, Henry
Seah, Hock-Soon

Publisher

The Eurographics Association

Abstract

Modern Computer Graphics applications commonly feature very large virtual environments and diverse characters which perform different kinds of motions. To accelerate path planning in such scenario, we propose subregion graph data structure. It consists of subregions, which are clusters of locally connected waypoints inside a region, as well as their connectivities. We also present a fast algorithm to automatically generate subregion graph from enhanced waypoint graph map representation, which also supports various motion types and can be created from large virtual environments. Nevertheless, subregion graph can also be generated from any graph-based map representation. Our experiments showed that subregion graph is very compact relative to the input waypoint graph. By firstly planning subregion path, and then limiting waypoint-level planning to the subregion path, up to 8 times average speedup can be achieved, while average length ratios are maintained at as low as 102.5%.

        @inproceedings{10.2312:pg.20151282
,
booktitle = {Pacific Graphics Short Papers
},
editor = {Stam, Jos and Mitra, Niloy J. and Xu, Kun
},
title = {{Accelerating Graph-based Path Planning Through Waypoint Clustering
}},
author = {Wardhana, Nicholas Mario and 
Johan, Henry and 
Seah, Hock-Soon
},
year = {2015
},
publisher = {The Eurographics Association
},
ISBN = {978-3-905674-96-5
},
DOI = {10.2312/pg.20151282
}
}