Lazy Anytime Planning for the Dubins Moving Target Traveling Salesman Problem with Obstacles
Anoop Bhat, Geordan Gutow, Surya Singh, Zhongqiang Ren, Sivakumar Rathinam, Howie Choset
AI summary
Problem
Planning obstacle-free trajectories for a Dubins vehicle to intercept multiple moving targets is NP-hard, with existing methods struggling to balance combinatorial sequencing costs and expensive kinematic feasibility checks.
Approach
Lazy IRG alternates between solving a Generalized TSP for a candidate interception sequence and lazily validating edges with an obstacle-aware planner, only computing collision checks when necessary to prune infeasible paths.
Key results
- Median solution cost 3x lower than IRG-PGLNS on 20-target instances
- Successfully plans and improves solutions for instances with up to 200 targets
- Consistently outperforms predecessors across varying obstacle densities and turning radii
- Delivers high-quality anytime solutions within a strict 1-minute time budget
Why it matters
Enables real-time, feasible mission planning for autonomous underwater and aerial vehicles performing time-critical interception tasks in cluttered environments.
Abstract
The Dubins Moving Target Traveling Salesman Problem with Obstacles (Dubins MT-TSP-O) seeks an obstacle- free trajectory for an agent with a fixed speed and minimum turning radius that intercepts several moving targets. To tackle this NP-hard problem, we introduce the Lazy Iterated Random Generalized TSP (Lazy IRG) algorithm. Each iteration of Lazy IRG samples a set of possible interception points in space- time along the trajectories of the targets. Lazy IRG then manages the high computational cost of motion planning by alternating between two steps: first, it optimistically selects a sequence of interception points by solving a Generalized TSP (GTSP) assuming an obstacle-free world; second, it searches for obstacle-free trajectories between consecutive points in the sequence using an obstacle-aware RRT-Connect planner. If a trajectory is not found, Lazy IRG solves the GTSP again; otherwise, Lazy IRG enters its next iteration and samples new interception points. By deferring expensive collision-checking, our method efficiently focuses computational effort on the most promising solutions. Numerical results show that Lazy IRG finds significantly lower-cost solutions within a 1-minute time budget compared to the existing IRG-PGLNS algorithm.