Heuristics for determining a patrol path of an unmanned combat vehicle

We consider a problem of finding a path of an unmanned combat vehicle that patrols a given area by visiting a given set of checkpoints with the objective of minimizing possibility of enemy’s infiltration. In this study, we focus on a situation in which the possibility of enemy’s infiltration at (through) each checkpoint is increased nonlinearly as time passes and the checkpoint may be patrolled multiple times during a planning horizon. We develop two-phase heuristics in which an initial path is constructed in the first phase and then it is improved in the second phase. For evaluation of the performance of the proposed heuristics, computational experiments are performed on randomly generated problem instances, and results show that the heuristics give good solutions in a reasonably short time.

► We consider a patrol path planning problem for an unmanned combat vehicle (UCV).
► The UCV visits given checkpoints and each checkpoint can be visited multiple times.
► Risk of enemy’s infiltration increases according to a nonlinear function of time.
► We develop two-phase heuristics to minimize risk of enemy’s infiltration.
► Computational experiments show that heuristics give good solutions in a short time.