Monday, July 21
10:00 am to 11:30 am
10:00 am to 11:30 am
Traveling Salesman Problems with Moving Targets and Obstacles
Abstract:
The moving target traveling salesman problem with obstacles (MT-TSP-O) seeks a trajectory for an agent that intercepts several moving targets within a particular time window for each target, all while avoiding stationary obstacles. The MT-TSP-O combines the combinatorial challenges of the standard TSP with the continuous decision over when and where to intercept each target, compounded with the classic difficulties of obstacle-free motion planning. The aim of this work is to develop algorithms with guarantees on completeness and optimality for variants of the MT-TSP-O. Under the assumption that the targets move along piecewise-linear trajectories and the agent can turn instantaneously, we present algorithms that guarantee finite-time completeness and optimality in 2D and 3D. For variants of the MT-TSP-O with generic nonlinear target trajectories and kinematic constraints on the agent (e.g. a minimum turning radius), we present algorithms that guarantee probabilistic completeness and asymptotic optimality, while additionally leveraging parallel computation to accelerate their convergence toward optimal solutions. Our proposed work considers the extension of our algorithms to the multi-agent, distributed setting, aiming to leverage the multiple computers distributed across multiple robots to enable scalability to large multi-robot systems. Additionally, our proposed work considers scenarios where obstacles may appear or disappear as the agent moves. For these scenarios with unpredictable dynamic obstacles, we propose methods to reuse as much search effort as possible when replanning.
Thesis Committee Members:
Howie Choset (Co-chair)
Matthew Travers (Co-chair)
Maxim Likhachev
Lydia Kavraki (Rice University)
Sivakumar Rathinam (Texas A&M University)