Incremental Search-Based Path Planning for Moving Target Search

In this dissertation, I demonstrate how to speed up path planning for moving target search, which is a problem where an agent needs to move to a target and the target can move over time. It is assumed that the current locations of the agent and the target are known to the agent at all times. The information about the terrain that an agent has is the action costs of the agent in any particular location of the terrain. The information about the terrain that the agent has can change over time depending on different applications: For example, when a robot is deployed in a new terrain without any map a priori, the robot initially does not have any information about the terrain and it has to acquire information about the terrain during navigation. However, a character in a computer game may have complete information about the terrain that remains unchanged over time given that the whole game map is loaded in memory and is available to the character. I use the following movement strategy for the agent that is based on assumptive planning: The agent first finds a cost-minimal path to the target with the information about the terrain that is currently available to it. The agent then starts moving along the path. Whenever new information about the terrain is acquired or the target moves off the path, the agent performs a new search to find a new cost-minimal path from the agent to the target. The agent uses this movement strategy until either the target is caught or the agent finds that there does not exist any path from the agent to the target after a search (and in any future searches), upon which the agent stops navigation. Since the agent's information about the terrain can change and the target can move over time, the agent needs to repeatedly perform searches to find new cost-minimal paths to the target. Path planning for moving target search by using this movement strategy is thus often a repeated search process. Additionally, agents need to find new cost-minimal paths as fast as possible, such that they move smoothly and without delay.;Many path planning algorithms have been developed, among which incremental search algorithms reuse information from previous searches to speed up the current search and are thus often able to find cost-minimal paths for series of similar search problems faster than by solving each search problem from scratch. Incremental search algorithms have been demonstrated to be very successful in path planning for many important applications in robotics. However, it is assumed that the target does not move over time during navigation for most incremental search algorithms, and they are either inapplicable or run more slowly than A* to solve moving target search. Thus, I demonstrate how to speed up search-based path planning for moving target search by developing new incremental search algorithms.;In my dissertation, I make the following contributions: (1) I develop Generalized Adaptive A* (GAA*), that learns h-values (= heuristic values) to make them more informed for moving target search. GAA* applies to moving target search in terrains where the action costs of the agent can change between searches. (2) I develop Generalized Fringe-Retrieving A* (G-FRA*), that transforms the search tree of the previous search to the search tree of the current search for moving target search. Though G-FRA* applies only to moving target search in terrains where the action costs of the agent do not change between searches, it creates a new way of transforming the search tree of the previous search to the search tree of the current search. (3) I develop Moving Target D* Lite (MT-D* Lite), that transforms the search tree of the previous search to the search tree of the current search for moving target search. MT-D* Lite combines the principles of G-FRA* and D* Lite, an existing incremental search algorithm. MT-D* Lite applies to moving target search in terrains where the action costs of the agent can change between searches. (4) I compare the new incremental search algorithms, discuss their strengths and weaknesses and provide guidelines for when to choose a particular algorithm over another. Simulation results show that the developed incremental search algorithms run up to one order of magnitude faster than A* for moving target search.