Проектирование оптимальной траектории проведения мониторинга объектов

В статье рассматривается задача разработки системы для моделирования траекторий движения робота, проводящего мониторинг в замкнутой области с земли: осмотр помещений, съемка промышленных объектов, оценка состояния фруктовых деревьев и т.д. Во время мониторинга на пути робота могут возникнуть некоторые препятствия: временно возникшие и устранимые (люди, небольшая мебель, бытовая техника, зона чрезвычайной ситуации) или постоянные (стены, постоянно установленное оборудование, зафиксированная мебель). Управление роботом осуществляется с помощью разработанной авторами программы, в которой хранится база данных маршрутов, успешно преодоленных роботом ранее, для наиболее точного определения траектории движения робота с учетом препятствий, встречающихся вдоль построенного пути. В статье рассматривается алгоритм построения графовой модели области проведения мониторинга для последующего поиска кратчайшего маршрута робота, заключающийся в дискретизации исследуемой области, выявлении возможных путей перемещения робота, анализе имеющихся препятствий и задании расстояний между объектами исследования. Показано, что после построения такого графа возможно применить один из алгоритмов поиска гамильтонова пути. Он соединяет вершины графа, соответствующие точкам проведения мониторинга. Результатом применения алгоритма является кратчайший маршрут робота, либо сообщение о невозможности проведения мониторинга (частичной или полной неразрешимости задачи), если ряд возникших препятствий не позволяет проложить маршрут, проходящий через некоторые (либо через все) вершины.