Solving global two dimensional routing problems using Snell's law and A* search

Abstract

Long-range route planning is an important component in the intelligent control system of an autonomous agent. Most attempts to solve it with map data rely on applying simple search strategies to high-resolution, node-and-link representations of the map. These techniques have several disadvantages including large time and space requirements. We present an alternative which utilizes a more intelligent representation of the problem environment. Topographical features are represented as homogeneous-cost regions, greatly reducing storage requirements. Then, the A* search strategy is applied to a dynamically created graph, constructed according to Snell's law. Testing has shown significant speed improvements over competing techniques.