Approximately Shortest Paths in Terrains

Dr. David Mould Department of Computer Science University of Saskatchewan

DEPARTMENT SEMINAR DATE: Monday, January 26, 2004 TIME: 3:30 p.m. PLACE: 2E25 Agriculture *** Everyone is welcome ***

Abstract

Approximately Shortest Paths in Terrains

Path planning through terrains is a problem often seen in areas such as robotics and computer games. Existing methods such as A* generally concentrate on finding an optimal path, but for many applications we will be satisfied with a path which is "good enough" -- having cost not too much worse than the optimal path cost.

We precompute a multiresolution representation of an initial graph. The new representation allows us to process shortest path queries in O(n) time in the path length, as compared with O(n²) for A*. We do not guarantee optimality, but with high probability (>95%) we return a path that is not drastically worse than optimal (within a factor of 1.3). The talk will describe details of the algorithm and show some experimental results.

This talk represents joint work with Dr. Michael Horsch of the University of Saskatchewan.

About the speaker

Dr. Mould became a faculty member of the Department of Computer Science at the University of Saskatchewan in June 2002. His academic background includes a B.Sc. from UBC, an M.Sc. from the University of Saskatchewan, and a Ph.D. from the University of Toronto. His research is chiefly in the field of computer graphics, where he works on physical simulation, procedural textures and models, and non-photorealistic rendering, among other topics.

[an error occurred while processing this directive]