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

Abstract

Long range route planning based on map data is an important component in the intelligent control system of an autonomous agent. Most attempts to solve this problem 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. The authors present a solution technique which utilizes a more intelligent representation of the problem environment. Topographical features are represented as homogeneous cost regions, greatly reducing storage requirements. Given this representation the A* search strategy is applied to a dynamically created graph that is constructed according to Snell's law. Testing has shown that this strategy reduces time requirements in many cases