Date of Award
2011
Publication Type
Master Thesis
Degree Name
M.Sc.
Department
Computer Science
Keywords
Computer Science.
Supervisor
Goodwin, Scott (Computer Science)
Rights
info:eu-repo/semantics/openAccess
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
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.
Recommended Citation
Vermette, Jonathan, "Salient Search" (2011). Electronic Theses and Dissertations. 342.
https://scholar.uwindsor.ca/etd/342