On constructing the fastest collision-free routes in dynamic environments with moving obstacles

A. L. Kazakov^a, A. A. Lempert^a, T. V. Tran<sup>b

a</sup> Matrosov Institute for System Dynamics and Control Theory of Siberian Branch of Russian Academy of Sciences, Irkutsk
^b Irkutsk National Research Technical University

Abstract: The article addresses the problem of constructing time-optimal routes for one or several moving objects in a dynamic environment with obstacles. We propose an approach based on the optical-geometrical analogy and the principles of Fermat and Huygens, which reduces the problem to solving the eikonal equation. A series of algorithms (including modifications of the fast marching method) is developed. They allow one to construct collision-free trajectories and correct them when the situation changes. The effectiveness of the proposed methods is confirmed by computational experiments, demonstrating their superiority in route length and computation time compared to existing approaches such as CFM, PRIMAL, and DHC.

Keywords: routing problem, dynamic environment, optical-geometric approach, eikonal equation, fast marching method.

UDC: 519.853.6, 517.958

MSC: 05B40, 52C17, 35A18

Received: 15.10.2025
Revised: 21.10.2025
Accepted: 27.10.2025

DOI: 10.21538/0134-4889-2025-31-4-115-131

Bibliographic databases:

•