Salient Search

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.

Name thesis:degree_name

M.Sc.

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Windsor

Year dc:date.issued

2011

Author dc:creator

• Vermette, Jonathan

Advisor dc:contributor.advisor

• Goodwin, Scott (Computer Science)

Licence

• http://creativecommons.org/licenses/by-nc-nd/4.0/

Language dc:language.iso

en_CA

Handle dc:identifier.uri

https://hdl.handle.net/20.500.14776/3108

OAI identifier oai:identifier

oai:uwindsor.scholaris.ca:20.500.14776/3108