Moving Target Search with Environment Abstraction

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.


Yorukcu, Alper




Moving Target Search (MTS) is a dynamic path planning problem, where an agent is trying to reach a moving entity with a minimum path cost. Problems of this nature can be found in video games and dynamic robotics, which require fast processing time (real time). In this thesis, we introduce a new algorithm for this problem - the Moving Target Search with Subgoal Graphs (MTSub). MTSub is based on environment abstraction and uses Subgoal Graphs to speed up searches without giving up cost minimal paths. The algorithm is optimal with respect to the knowledge that the agent has during the search. Experimental results show that MTSub meets the requirement of real time performance (e.g., 5 microseconds per step). Compared to G-FRA*, which is the best known dynamic algorithm so far, MTSub is up to 29 times faster in average time per step, and 186 times faster in maximum time per step.


Computer Science




Carleton University

Thesis Degree Name: 

Master of Computer Science: 

Thesis Degree Level: 


Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).