Point seeking: a family of dynamic path finding algorithms
Andrew Fanton · RIT Scholar Works (Rochester Institute of Technology) · 2007
In the field of Artificial Intelligence, calculating the best route from one point to another, known as “path finding,” has become a common problem. If an agent cannot effectively navigate through an environment – be it real or virtual – it will often not be able to perform even the most routine tasks. For example, a Martian rover can't collect samples if it can't get to them; meanwhile, a computer game is not much of a challenge if your opponents can't find their way around. The problem of path finding has three basic aspects: map representation, path generation, and locomotion. First, the environment must be interpreted into a form which can be processed algorithmically. Afterward, a path through this environment is planned out. A list of movement instructions or locations to travel to are then produced in order to guide the agent. During both the planning and movement of the agent, an algorithm may consider the agent's limitations with regards to changes in velocity and orientation. Together, these steps serve to move an agent from its initial position to the desired location.