Algorithms for an Unmanned Vehicle Path Planning Problem

Abstract

Unmanned Vehicles (UVs) have been significantly utilized in military and civil applications over the last decade. Path-planning of UVs plays an important role in effectively using the available resources such as the UVs and sensors as efficiently as possible. The main purpose of this thesis is to address two path planning problems involving a single UV.

The two problems we consider are the quota problem and the budget problem. In the quota problem, the vehicle has to visit a sufficient number of targets to satisfy the quota requirement on the total prize collected in the tour. In the budget problem, the vehicle has to comply with a constraint of the distance traveled by the UV. We solve both these problems using a practical heuristic called the prize-multiplier approach. This approach first uses a primal-dual algorithm to first assign the targets to the UV. The Lin – Kernighan Heuristic (LKH) is then applied to generate a tour of the assigned targets for the UV. We tested this approach on two different vehicle models. One model is a simple vehicle which can move in any direction without a constraint on its turning radius. The other model is a Reeds-Shepp vehicle. We also modeled both problems in C++ using the multi-commodity flow formulations, and solved them to optimality by using the Concert Technology of CPLEX.

We used the results generated by CPLEX to determine the quality of the solutions produced by the heuristics. By comparing the objective values of the obtained solutions and the running times of the heuristics and CPLEX, one can conclude that the proposed heuristics produce solutions with good quality to our problems within our desired time limits.