Date of Award

2007

Publication Type

Master Thesis

Department

Computer Science

Rights

info:eu-repo/semantics/openAccess

Abstract

Pathfinding is the search for a goal state given a start state, within either static or dynamic environments. Many pathfinding algorithms exist, including established algorithms such as A*, SMA*, and D*. These algorithms all provide optimal solution paths, using all available memory. Consequently, Algorithms such as A* and D* are known to be inefficient in terms of memory space usage. SMA* and similar algorithms provide a means by which optimal solution paths can be found while being memory efficient. SMA* and such algorithms are restricted to static environments, in which state traversal costs never change. This is a severe limitation, as one of the primary fields for search algorithms are games, many of which involve dynamic environments. Presented in this paper is a dynamic variant of the established D* Lite algorithm, that is able to provide an optimal solution path, if given sufficient memory, while using as little memory as possible. It is also the case that in some areas, an optimal solution is not needed. This may be the case for robotics. Many algorithms already exist in this area, such as Anytime algorithms for time-limited searches. Real-Time algorithms for when the agent needs to move while planning its path. Also presented is an algorithm for real-time planning when an agent does not have a priori knowledge of the environment, and also limited memory capacity. This algorithm sacrifices optimality, but in turn is highly memory efficient, even in comparison to other algorithms designed for memory efficiency.

Download

Share

COinS