Route Finding by Huygens' Principle
Aivars Celmiņš · 1998
We consider the problem of finding optimal long-distance routes for robots in a terrain with approximate information. The terrain is characterized by the average speed that can be maintained by the robot in different parts of the landscape. Additional specified terrain properties might be, for instance, the level of threat or visibility. The robot is required to find a route that corresponds to an optimum in terms of the terrain conditions. Examples of optimal routes are those with shortest travel time, those with minimal exposure to danger, those with a lowest or highest visibility, etc. A complete solution of the problem is obtained by an algorithm that is based on Huygens' principle of wave propagation. The algorithm has been developed for static terrain with a fixed destination point, but, because of its simplicity, it can be used also when the terrain is dynamic. Possible application areas of the algorithm are path finding for scouting robots in a battlefield, finding optimal routes for aircraft in hostile or dangerous environments, finding optimal routes in street maps, and, generally, finding routes that satisfy some optimality condition in an environment represented by maps.