LOWER BOUNDS FOR A VEHICLE ROUTING PROBLEM WITH MOTION CONSTRAINTS

Given a set of targets that needs to be monitored and a vehicle, we consider a combinatorial motion planning problem where the objective is to find a path for the vehicle such that each target is visited at least once by the vehicle: the path satisfies the motion constraints of the vehicle and the length of the path is a minimum. This is an NP-hard problem, and currently, there are no algorithms that can find an optimal solution to this problem. In this paper, we model the motion of the vehicle as a Dubins car and develop a method that can provide lower bounds to the motion planning problem. Lower bounds are important because they can be used to corroborate the quality of the solutions produced by the heuristics or the approximation algorithms. We obtain a lower bound by relaxing the constraints corresponding to the angle of approach at each of the targets and then penalizing them whenever they are violated. The solution to the Lagrangian relaxation gives a lower bound, and this lower bound is maximized over the penalty variables using sub-gradient optimization. Simulation results to compare the proposed lower bound with the existing lower bounds are presented.