Задачи, связанные с задачей охраны акватории, которые решаются на данный момент.

Задача 1

Постановка

Задана геометрическая область \(D\) (в двумерном пространстве), в виде полигона с ”дырками”. В поле зрения аппарата в любой момент времени попадает круг с центром в положении аппарата и заданным радиусом \(R_{v}\). Сам аппарат имеет форму круга радиуса \(R_{a}\) (в более простом варианте можно считать аппарат точкой). Требуется построить циклическую траекторию, проходя по которой, в поле зрения аппарата окажутся все точки области \(D\)(Более формально сумма минковского такой траектории и области зрения аппарата (круга радиуса \(R_{v}\)) будет содержать область \(D\)). У области \(D\) есть ”жесткие границы” – которые аппарат не может пересекать, и ”нежесткие”, которые аппарат может пересечь. Задача оптимизации – построить вышеописанную траекторию, удовлетворяющую всем границам (жестким и нежестким), кратчайшей длины.

Обоснованием такой задачи может послужить следующая мысль. Двигаясь по вышеописанной траектории аппарат с наибольшей возможной частотой будет посещать каждую точку области \(D\), а значит и максимизирует свою вероятностью зафиксировать наличие злоумышленника при детерминированном обходе. Группу аппаратов можно равномерно распределить по этому циклу и также заставить патрулировать вдоль него.

Именно в такой постановке задача обладает следующей проблемой. Если рассматривать различные способы построения ”покрывающих” траекторий, можно заметить, что их длина не так уже сильно будет отличаться друг от друга. В частности, один из распростраенных методов решения – декомпозиция области на выпуклые части (например на трапеции) и меандр в каждой из них дадут не такую уж длинную траекторию. Хотя теоретическую оценку я здесь привести затрудняюсь.

Поэтому было решено рассмотреть еще одну характеристику траектории – суммарное изменение курса аппарата при прохождении вдоль траектории. Может показаться, что время, которое аппарат будет тратить на повороты, можно считать пренебрежимо малым в сравнении с временем прямых участков. Однако, если рассмотреть различные способы построить тот же меандр в рамаках одной и той же области, можно понять что разные способы его построения будут очень сильно отличаться по количеству поворотов, что уже может значительно сказаться на общем времени прохождения траектории (заметим также, что в тривиальной модели движения, при повороте аппарат не исследует новой части области, т.к. его поле зрения – это круг. В итоге хотим оптимизировать траекторию не только по длине, но и по суммарному изменению курса.

Здесь уже есть несколько идей.

Решение

Для построения траектории можно покрыть область графом-решеткой и решить задачу коммивояжера для тех вершин, окружности с центрами в которых, пересекают нашу область \(D\).