Date of Award

2011

Degree Type

Thesis

Degree Name

M.Sc.

Department

Computer Science

First Advisor

Goodwin, Scott (Computer Science)

Keywords

Computer Science.

Rights

CC BY-NC-ND 4.0

Abstract

All real-time pathfinding algorithms suffer from some degree of suboptimal behaviour on the part of the agent. A consequence of the need to perform a move before it is guaranteed to be optimal, this is inversely proportional to the amount of effort given to planning between each move. Many real-time algorithms employ a constant-bounded local search to plan a single move at a time. However they need multiple trials to converge on an optimal solution. More recent hierarchical approaches produce good results after a single trial, but rely on extensive pre-processing, limiting their use in dynamic environments. A newer algorithm, Time Bounded A*, conducts a global A* to find an optimal path on the first trial, while creating partial paths for an agent to follow. However, harder search problems can induce the appearance of indecisiveness on the part of the agent as all of its time is spent moving back and forth between subgoals. To remedy this, we introduce Salient Search. This algorithm adds new features to TBA* to track and dedicate search effort to a given subsection of the open list. Experiments on maps taken from popular computer games show that for small planning slices, Salient Search reduces the indecisiveness shown by an agent. Further, the effect is stronger on more difficult problems.

Share

COinS