В. И. Бердышев, В. Б. Костоусов, А. А. Попов. Оптимальная траектория в ℝ^2 в условиях наблюдения ... С. 40-52

УДК 519.62

MSC: 00A05

DOI: 10.21538/0134-4889-2018-24-1-40-52

Результаты первого раздела установлены В. И. Бердышевым за счет гранта Российского научного фонда (проект 14-11-00702). Остальные результаты получены В. Б. Костоусовым и А. А. Поповым при финансовой поддержке комплексной программы ФНИ УрО РАН (проект 18-1-1-14).

Исследуется задача формирования траектории в заданном "коридоре" из $\mathbb{R}^2$, минимум расстояния которой от наблюдателей максимален. Каждый наблюдатель расположен вне коридора и имеет открытый выпуклый конус наблюдения, который перекрывает коридор. Положение наблюдателей и конусов фиксировано. Расстояние до движущегося по траектории объекта наблюдатель измеряет, когда объект находится внутри его конуса. В статье дано описание "оптимального коридора" - множества всех оптимальных траекторий с заданными начальной и конечной точками. Аналогичная задача решена в случае, когда движущийся объект - телесный - является замкнутым кругом. Для практических расчетов в работе предлагаются алгоритмы построения оптимального коридора и кратчайшей оптимальной траектории в дискретной постановке для телесного объекта. Исходные непрерывные условия задачи, такие как границы коридора и конусы наблюдения, проектируются на дискретную регулярную сетку, и на ней строятся дискретная реализация оптимального коридора, его границы в виде 8-связных последовательностей узлов сетки, а также с помощью алгоритма Дейкстры находится кратчайшая оптимальная траектория телесного объекта.

Ключевые слова: движущийся объект, наблюдатель, оптимальная траектория, кратчайший путь.

СПИСОК ЛИТЕРАТУРЫ

1.   Бердышев В.И. Движущийся объект и наблюдатель // Докл. АН. 2015. Т. 464, № 4. С. 411–413.

2.   Попов А.А., Костоусов В.Б., Бердышев В.И. Траектория объекта, наиболее удаленная от наблюдателей // CEUR Workshop Proceedings. Vol. 1894: Proc. of the 48th Internat. Youth School-Conf. “Modern Problems in Mathematics and its Applications” (Yekaterinburg, Russia, February 5 – February 11, 2017). 2017. С. 129–136. URL: http://ceur-ws.org/Vol-1894 .

3.   Rogers D.F. Procedural elements for computer graphics. N Y: McGraw-Hill, 1985. 430 p. ISBN: 0-07-053534-5 .

4.   Introduction to algorithms: 3rd ed. / T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Cambridge; London: The MIT Press, 2009. 1312 p. ISBN: 978-0-262-03384-8 .

Поступила 29.12.2017

Бердышев Виталий Иванович
академик РАН
научный руководитель
Институт математики и механики им. Н.Н.Красовского УрО РАН, г. Екатеринбург
e-mail: bvi@imm.uran.ru

Костоусов Виктор Борисович
канд. физ.-мат. наук
зав. отд.
Институт математики и механики им. Н.Н.Красовского УрО РАН, г. Екатеринбург
e-mail: vkost@imm.uran.ru

Попов Александр Андреевич
ведущий программист
Институт математики и механики им. Н.Н.Красовского УрО РАН, г. Екатеринбург
e-mail: aap@imm.uran.ru

V.I. Berdyshev, V.B. Kostousov, A.A. Popov. Optimal trajectory in $\mathbb{R}^2$ under observation.

We study the problem of forming a trajectory in a given "corridor" from $\mathbb{R}^2$ such that the minimum distance from this trajectory to observers is maximal. Each observer is located outside the corridor and has an open convex observation cone overlapping the corridor. The positions of the observers and the cones are fixed.
An observer can measure the distance to an object moving along the trajectory when the object is inside its cone. We describe an "optimal corridor", i.e., the set of all optimal trajectories with given initial and terminal points. A similar problem is solved in the case when the moving object is a solid body, more exactly, a disk. For practical calculations, we propose algorithms that construct an optimal corridor and a shortest optimal trajectory for a solid object in a discrete statement. The initial continuous conditions of the problem, such as the boundaries of the corridor and the observation cones, are projected onto a discrete regular grid, and a discrete realization of the optimal corridor and its boundaries are constructed on the grid in the form of 8-connected sequences of grid nodes. The shortest optimal trajectory of the solid object is found using Dijkstra's algorithm.

Keywords: moving object, observer, optimal trajectory, shortest path.