EFFICIENT TOUR PLANNING FOR A MEASUREMENT VEHICLE BY COMBINING NEXT BEST VIEW AND TRAVELING SALESMAN

J. Gehrung, Marcus Hebel, Michael Arens, Uwe Stilla2021 · DOI

Abstract

Path planning for a measuring vehicle requires solving two popular problems from computer science, namely the search for the optimal tour and the search for the optimal viewpoint. Combining both problems results in a new variation of the Traveling Salesman Problem, which we refer to as the Explorational Traveling Salesman Problem (ETSP). The solution to this problem is the optimal tour with a minimum of observations. In this paper, we formulate the basic problem, discuss it in context of the existing literature and present an iterative solution algorithm. We demonstrate how the method can be applied directly to LiDAR data using an occupancy grid. The ability of our algorithm to generate suitably efficient tours is verified based on two synthetic benchmark datasets, utilizing a ground truth determined by an exhaustive search.

Introduction: The Explorational Traveling Salesman Problem

Mobile mapping vehicles often face a "chicken-and-egg" dilemma when tasked with scanning urban environments. To detect changes efficiently, one must solve two interdependent problems: Next Best View (NBV)—identifying locations that provide the best line-of-sight to points of interest (POIs)—and the Traveling Salesman Problem (TSP)—determining the shortest path to visit these locations.

In practice, these are not independent. The choice of a viewpoint alters the optimal tour, while the vehicle's current orientation and position constrain which viewpoints are accessible. This combined challenge, termed the Explorational Traveling Salesman Problem (ETSP), is computationally NP-hard. Finding an exact solution becomes unfeasible as the number of POIs grows, necessitating intelligent heuristic approaches.

The proposed solution employs an iterative algorithm that dynamically updates the path based on visibility and distance.

  1. Visibility Matrix: A 2D matrix is constructed where rows represent potential viewpoints and columns represent POIs. A binary value indicates whether a POI is visible from a specific viewpoint.
  2. Dynamic Weighting: Unlike a static TSP, the graph here is dynamic. When a vehicle visits a viewpoint and "sees" certain POIs, the weight (utility) of other viewpoints that cover the same POIs is reduced.
  3. Cost-Benefit Scoring: The algorithm selects the next destination by maximizing a score defined as Score = Weight / Distance. This prioritizes viewpoints that cover many unseen POIs while remaining close to the current position.
  4. Kinematic Path Planning: To ensure drivability, a Hybrid A-Star algorithm is used, accounting for vehicle turning radii and obstacles within a LiDAR-derived occupancy grid.
  5. Refinement: A "2-opt" local search is applied to the final tour to further minimize total distance.
Iterative algorithm workflow: (a) Visibility matrix, (b) initial state, (c) intermediate state with selected viewpoints, and (d) final optimized tour.

Experimental Evaluation and Results

The algorithm was tested against two synthetic benchmarks created in Blender and CloudCompare. For small-scale problems (Dataset A), results were compared against a true mathematical optimum found via exhaustive search.

  • Performance: In Dataset A, the algorithm achieved a tour length of 47.73 units, close to the 43.49-unit optimum. In the more complex Dataset B, the heuristic actually matched the ground truth optimal length of 151.67 units.
  • Computational Speedup: The most significant advantage is efficiency. For Dataset B, an exhaustive search required approximately 208 hours (12,509 minutes). The proposed iterative algorithm reached the same result in just 27 minutes—a massive reduction in runtime.
  • LiDAR Integration: The method successfully operates on occupancy grids, allowing for direct application to real-world sensor data.
A planned tour visualized on a LiDAR occupancy grid. The blue line represents the optimized path connecting selected viewpoints (red/green dots) to cover all required areas.

Conclusion and Future Directions

The ETSP framework successfully bridges the gap between viewpoint selection and path optimization. By prioritizing "indirect viewpoints" that cover multiple POIs simultaneously, the algorithm significantly reduces the number of required stops.

Future work will focus on optimizing the Hybrid A-Star component, which remains the primary computational bottleneck. Additionally, the researchers plan to adapt the model for "drive-by" scanning, where measurements are taken continuously while the vehicle is in motion, rather than at discrete stops. Scaling the approach to massive city-scale datasets with thousands of POIs remains the ultimate goal for real-world deployment.

Summary updated

Abstract

Path planning for a measuring vehicle requires solving two popular problems from computer science, namely the search for the optimal tour and the search for the optimal viewpoint. Combining both problems results in a new variation of the Traveling Salesman Problem, which we refer to as the Explorational Traveling Salesman Problem. The solution to this problem is the optimal tour with a minimum of observations. In this paper, we formulate the basic problem, discuss it in context of the existing literature and present an iterative solution algorithm. We demonstrate how the method can be applied directly to LiDAR data using an occupancy grid. The ability of our algorithm to generate suitably efficient tours is verified based on two synthetic benchmark datasets, utilizing a ground truth determined by an exhaustive search.
BibTeX
@inproceedings{gehrung2021efficient,
  author = {J. Gehrung and Marcus Hebel and Michael Arens and Uwe Stilla},
  title = {{EFFICIENT TOUR PLANNING FOR A MEASUREMENT VEHICLE BY COMBINING NEXT BEST VIEW AND TRAVELING SALESMAN}},
  booktitle = {˜The},
  year = {2021},
  doi = {10.5194/isprs-archives-xliii-b2-2021-729-2021},
}
Figure