Landmark Placement Algorithms for Multi-vehicle Path Planning with Localization Constraints

2019 by German Aerospace Center (DLR). Published by the American Institute of Aeronautics and Astronautics, Inc. When deploying unmanned vehicles to perform monitoring, data collection or delivery tasks, localization is a critical technology for successful navigation. Although most previous path planning algorithms rely on information from the Global Positioning System (GPS), GPS signals are often subjected to delay, jamming or spoofing. Hence, routing unmanned vehicles in harsh or indoor environments has been challenging and needs alternative solutions. Relative position measurements to known land-marks, using range or bearing angle sensors on-board, can be used to localize an autonomous vehicle. When the known landmarks are not sufficient, additional proxy landmarks can be suitably placed to provide the required information. This article addresses a fundamental problem of suitably placing landmarks in a region to enable a team of unmanned vehicles to travel their respective desired paths. The objective is to place a minimal number of landmarks as possible subject to the localization constraints specified by the paths. We present integer linear programs, upper-bounding algorithms and heuristics to solve several variants of this problem. Simulation results are also presented to corroborate the performance of the proposed algorithms in the vehicle routing context.

Landmark Placement Algorithms for Multi-vehicle Path Planning with Localization Constraints Conference Paper