Minimal Exposure Dubins Orienteering Problem
Douglas G. Macharet, Armando Alves Neto, Daigo Shishika
Abstract
Visiting and observing specified locations is a fundamental task for various applications including environmental monitoring and military operations. The Orienteering Problem (OP) is a variant of routing problems in which the goal is to maximize the objective function by visiting the most rewarding locations while respecting a limited travel budget (e.g., distance or time). However, traditional formulations of routing problems generally neglect some environmental peculiarities, such as obstacles or threatening zones. In this letter, we tackle the OP considering Dubins vehicles in the presence of a known deployed sensor field. We propose a novel multi-objective formulation called the Minimal Exposure Dubins Orienteering Problem (MEDOP), whose goals are to (i) maximize the collected reward, while (ii) minimizing the exposure of the agent, i.e., the probability of being detected. The solution is based on an evolutionary algorithm that iteratively varies the subset and sequence of locations to be visited, the orientations on each location, and the turning radii on the connecting segments. Results show that our approach is consistent and can efficiently find a diverse set of solutions that simultaneously optimize both objectives.
BibTeX
@inproceedings{ral2021_minimalexposured,
title = {Minimal Exposure Dubins Orienteering Problem},
author = {Douglas G. Macharet and Armando Alves Neto and Daigo Shishika},
booktitle = {RA-L 2021},
year = {2021}
}