Oberlin, Paul V. (2009-05). Path Planning Algorithms for Multiple Heterogeneous Vehicles. Master's Thesis. Thesis uri icon

abstract

  • Unmanned aerial vehicles (UAVs) are becoming increasingly popular for surveillance in civil and military applications. Vehicles built for this purpose vary in their sensing capabilities, speed and maneuverability. It is therefore natural to assume that a team of UAVs given the mission of visiting a set of targets would include vehicles with differing capabilities. This paper addresses the problem of assigning each vehicle a sequence of targets to visit such that the mission is completed with the least "cost" possible given that the team of vehicles is heterogeneous. In order to simplify the problem the capabilities of each vehicle are modeled as cost to travel from one target to another. In other words, if a vehicle is particularly suited to visit a certain target, the cost for that vehicle to visit that target is low compared to the other vehicles in the team. After applying this simplification, the problem can be posed as an instance of the combinatorial problem called the Heterogeneous Travelling Salesman Problem (HTSP). This paper presents a transformation of a Heterogenous, Multiple Depot, Multiple Traveling Salesman Problem (HMDMTSP) into a single, Asymmetric, Traveling Salesman Problem (ATSP). As a result, algorithms available for the single salesman problem can be used to solve the HMDMTSP. To show the effectiveness of the transformation, the well known Lin-Kernighan-Helsgaun heuristic was applied to the transformed ATSP. Computational results show that good quality solutions can be obtained for the HMDMTSP relatively fast. Additional complications to the sequencing problem come in the form of precedence constraints which prescribe a partial order in which nodes must be visited. In this context the sequencing problem was studied seperately using the Linear Program (LP) relaxation of a Mixed Integer Linear Program (MILP) formulation of the combinatorial problem known as the "Precedence Constrained Asymmetric Travelling Salesman Problem" (PCATSP).
  • Unmanned aerial vehicles (UAVs) are becoming increasingly popular for surveillance
    in civil and military applications. Vehicles built for this purpose vary in their
    sensing capabilities, speed and maneuverability. It is therefore natural to assume
    that a team of UAVs given the mission of visiting a set of targets would include
    vehicles with differing capabilities. This paper addresses the problem of assigning
    each vehicle a sequence of targets to visit such that the mission is completed with
    the least "cost" possible given that the team of vehicles is heterogeneous. In order
    to simplify the problem the capabilities of each vehicle are modeled as cost to travel
    from one target to another. In other words, if a vehicle is particularly suited to visit
    a certain target, the cost for that vehicle to visit that target is low compared to
    the other vehicles in the team. After applying this simplification, the problem can be
    posed as an instance of the combinatorial problem called the Heterogeneous Travelling
    Salesman Problem (HTSP). This paper presents a transformation of a Heterogenous,
    Multiple Depot, Multiple Traveling Salesman Problem (HMDMTSP) into a single,
    Asymmetric, Traveling Salesman Problem (ATSP). As a result, algorithms available
    for the single salesman problem can be used to solve the HMDMTSP. To show the
    effectiveness of the transformation, the well known Lin-Kernighan-Helsgaun heuristic
    was applied to the transformed ATSP. Computational results show that good quality
    solutions can be obtained for the HMDMTSP relatively fast.
    Additional complications to the sequencing problem come in the form of precedence
    constraints which prescribe a partial order in which nodes must be visited. In this context the sequencing problem was studied seperately using the Linear Program
    (LP) relaxation of a Mixed Integer Linear Program (MILP) formulation of the
    combinatorial problem known as the "Precedence Constrained Asymmetric Travelling
    Salesman Problem" (PCATSP).

publication date

  • May 2009