Heuristics for Multi-Vehicle Routing Problem Considering Human-Robot Interactions

Venkata Sirimuvva Chirala, Kaarthik Sundar, Saravanan Venkatachalam, Jonathon M. Smereka, Sam KassoumehIEEE Trans. Intell. veh 2023 · DOI

TL;DR

This paper tackles the complex challenge of optimizing routes for teams of human-operated vehicles (MGVs) and autonomous ground vehicles (UGVs) working together. They introduce a novel heuristic algorithm, Skewed Variable Neighborhood Search (SVNS), that effectively balances travel costs, human-robot interaction (HRI) costs, and team deployment costs, outperforming traditional optimization methods for larger, more realistic scenarios.

What Problem Does This Paper Address?

The increasing integration of autonomous systems, particularly Unmanned Ground Vehicles (UGVs), into civilian and military operations presents a significant logistical challenge. This paper focuses on the "Multi-Vehicle Routing Problem" (MVRP) specifically when these UGVs operate in teams with manned vehicles (MGVs) under a leader-follower framework. The core problem is to determine optimal routes, team compositions (how many UGVs per MGV), and replenishment strategies for these mixed teams to execute missions efficiently. This is complicated by the "human-robot interaction" (HRI) costs, which represent the cognitive and physical burden on human operators managing autonomous teammates. Existing optimization models struggle to scale to realistic problem sizes, necessitating more efficient heuristic approaches.

Methods

The authors propose a two-pronged approach:

  • Optimization Model: They first present a mixed-integer linear programming (MILP) model that captures the problem's complexity, including routing, replenishment, HRI costs, and team deployment costs. This model can find optimal solutions for small instances but is computationally prohibitive for larger ones.
  • Skewed Variable Neighborhood Search (SVNS): To address the scalability issue, they develop a heuristic algorithm based on the Variable Neighborhood Search (VNS) meta-heuristic. SVNS is designed to explore "valleys" of potential solutions that are far from the current best-known solution, allowing it to escape local optima. The SVNS algorithm involves:
  • Construction Heuristic: Generating an initial feasible solution using a combination of a multi-traveling salesman problem (mTSP) solver and two assignment strategies (asgn-rule1 and asgn-rule2) to determine team compositions and replenishment plans.
  • Shaking: Using the "POI-swap-intra" neighborhood to perturb the current solution and escape local optima.
  • Local Search: Employing a suite of neighborhoods (2-opt-intra, POI-remove-insert, POI-swap-inter, POI-SequenceExchange-inter, and a new "asgn-rule3" neighborhood) to systematically explore the solution space and find better solutions.
  • Recentering: A key feature of SVNS that allows it to accept solutions that are not immediately better but are significantly different, aiding in escaping deep local optima.

Datasets

The paper does not use pre-existing datasets. Instead, they generate three sets of synthetic instances for evaluation:

  • Small Scale: 80 instances with 5 POIs and 2 vehicles.
  • Medium Scale: 80 instances with 20 POIs and 3-5 vehicles.
  • Large Scale: 80 instances with 40 POIs and 6-8 vehicles.

Path traversal and replenishment costs are derived from Euclidean distances. HRI costs are based on findings from existing HRI studies (referenced as Fig. 1).

Key Insights and Ideas

  • HRI is a Critical Cost Factor: The paper emphasizes that human-robot interaction costs are not negligible and must be explicitly modeled to achieve realistic and efficient multi-vehicle operations.
  • SVNS for Scalability: The SVNS heuristic demonstrates a significant improvement in computational efficiency compared to the MILP model, making it feasible to solve larger and more complex routing problems.
  • Neighborhood Design Matters: The performance of the SVNS algorithm is highly dependent on the chosen neighborhoods. Inter-route neighborhoods (POI-remove-insert, POI-swap-inter, POI-SequenceExchange-inter) generally outperform intra-route neighborhoods for this problem.
  • Weighting Objectives is Crucial: The multi-objective nature of the problem means that the "best" solution is subjective and depends on the priorities (weights) assigned to travel costs, HRI costs, and team costs. The paper shows how varying these weights can lead to different optimal trade-offs.
  • Assignment Strategies Impact Solutions: The choice between different assignment strategies (e.g., prioritizing replenishment vs. minimizing HRI) significantly affects the overall cost and solution characteristics.

Key Results

  • Optimal for Small Instances: The SVNS algorithm finds optimal solutions for all 80 small-scale instances.
  • High-Quality Sub-optimal for Larger Instances: For medium and large-scale instances, SVNS consistently finds high-quality sub-optimal solutions within reasonable timeframes.
  • Medium scale instances: Average improvement of 25.51% over the initial heuristic solution.
  • Large scale instances: Average improvement of 25.48% over the initial heuristic solution.
  • Computational Efficiency: SVNS runs significantly faster than the MILP model, with average run times of 2.02 seconds for small instances compared to 4.28 seconds for the MILP.
  • Neighborhood Performance: Inter-route neighborhoods like POI-remove-insert and POI-swap-inter showed superior performance in improving solutions for small-scale instances.

Limitations and Future Work

  • Deterministic Model: The current model assumes deterministic travel times, demands, and HRI costs. Future work could incorporate uncertainties in these factors.
  • Vehicle Refueling: The model does not currently account for vehicle refueling needs, which is a practical consideration for real-world deployments.
  • Weight Optimization: While the paper discusses sensitivity to weights, it suggests that machine learning algorithms could be used to automatically find appropriate weight values for different scenarios.
  • Extending to Other Autonomy Levels: The current framework focuses on a specific leader-follower setup. Future work could explore more complex human-robot teaming structures and varying levels of autonomy.

Summary updated

BibTeX
@article{chirala2023heuristics,
  author = {Venkata Sirimuvva Chirala and Kaarthik Sundar and Saravanan Venkatachalam and Jonathon M. Smereka and Sam Kassoumeh},
  title = {{Heuristics for Multi-Vehicle Routing Problem Considering Human-Robot Interactions}},
  journal = {IEEE Trans. Intell. veh},
  year = {2023},
  doi = {10.1109/tiv.2023.3261274},
}
Figure