Abstract:
We study the problem of finding a trajectory for an agent to intercept a number of moving targets while avoiding obstacles. Applications include resupplying naval ships at sea and recharging aerial vehicles with a ground vehicle. We model the problem as an extension of the traveling salesman problem, which we refer to as the moving target traveling salesman motion planning problem with obstacles (MT-TS-MP-O). Prior approaches to this problem can find feasible solutions, but do not provide bounds on the suboptimality of these solutions, due to a lack of a lower bound on the optimal cost. We develop two methods of providing lower bounds. The first method relaxes the continuity requirement on the agent’s trajectory, and the second method relaxes the agent’s collision avoidance constraints. We present the benefits and drawbacks of each method, as well as future directions.

Committee:
Howie Choset
Matt Travers
Maxim Likhachev
Charles Noren