Карпов Дмитрий Анатольевич – кандидат технических наук, заведующий кафедрой общей информатики Института искусственного интеллекта.
119454, Москва, пр-т Вернадского, д. 78.
SPIN-код РИНЦ 2619-7100
Dmitry A. Karpov - Cand. Sci. (Eng.), Head of the General Informatics Department, Institute of Artificial Intelligence, MIREA - Russian Technological University.
78, Vernadskogo pr., Moscow, 119454.
RSCI SPIN-code 2619-7100
Струченков Валерий Иванович – доктор технических наук, профессор кафедры общей информатики Института искусственного интеллекта.
119454, Москва, пр-т Вернадского, д. 78.
SPIN-код РИНЦ 4581-4698
Valery I. Struchenkov - Dr. Sci. (Eng.), Professor, General Informatics Department, Institute of Artificial Intelligence, MIREA - Russian Technological University.
78, Vernadskogo pr., Moscow, 119454.
RSCI SPIN-code 4581-4698
Цели. В настоящее время наблюдается бурное развитие теории и методов сплайн-аппроксимации плоских кривых, заданных последовательностью точек. Проведенные исследования, первые результаты которых были опубликованы ранее, показали возможность применения сплайн-аппроксимации в проектировании трасс линейных сооружений, несмотря на принципиальные отличия используемых сплайнов от рассматриваемых в теории и ее приложениях. Главное отличие состоит в том, что в проектировании трасс нельзя заранее считать известным число элементов сплайна. Кроме того, в отличие от получивших широкое распространение полиномиальных сплайнов, повторяющимся элементом является связка «отрезок прямой + + дуга окружности» или «отрезок прямой + дуга клотоиды + дуга окружности + дуга клотоиды». Ранее была предложена двухэтапная схема: определение числа элементов искомого сплайна, затем - оптимизация его параметров. Алгоритм решения задачи применительно к проектированию продольного профиля реализован и опубликован. Но этот алгоритм непригоден для проектирования плана трассы, т.к. план трассы, в отличие от профиля, в общем случае является многозначной функцией. Цель работы - обобщить алгоритм на случай сплайн-аппроксимации многозначных функций с учетом особенностей проектирования трасс линейных сооружений.
Методы. На первом этапе используется новая математическая модель, позволяющая применить метод динамического программирования с учетом ограничений на параметры искомого сплайна. На втором этапе используется нелинейное программирование. При этом удается вычислять аналитически производные целевой функции по параметрам сплайна при отсутствии ее аналитического выражения через эти параметры.
Результаты. Разработаны алгоритм аппроксимации многозначных функций, заданных дискретным рядом точек, сплайном, состоящим из дуг окружностей, сопрягаемых отрезками прямых, для решения задачи на первом этапе и алгоритм нелинейного программирования для оптимизации параметров полученного сплайна как начального приближения. В настоящей статье рассматривается только первый этап, т.к. сложный алгоритм второго этапа и его обоснование требуют отдельного рассмотрения.
Выводы. Двухэтапная схема сплайн-аппроксимации при неизвестном числе элементов сплайна пригодна и для аппроксимации многозначных функций, заданных последовательностью точек на плоскости, в частности для проектирования плана трасс линейных сооружений.
Objectives. The theory and methods of spline approximation of plane curves given by a sequence of points are currently undergoing rapid development. Despite fundamental differences between used splines and those considered in the theory and its applications, results published earlier demonstrate the possibility of using spline approximation when designing routes of linear structures. The main difference here consists in the impossibility of assuming in advance the number of spline elements when designing the routes. Here, in contrast to widely use polynomial splines, the repeating element is the link “segment of a straight line + arc of a circle” or “segment of a straight line + arc of a clothoid + arc of a circle + arc of a clothoid.” Previously, a two-stage scheme consisting of a determination of the number of elements of the desired spline and subsequent optimization of its parameters was proposed. Although an algorithm for solving the problem in relation to the design of a longitudinal profile has been implemented and published, this is not suitable for designing a route plan, since, unlike a profile, a route plan is generally a multivalued function. The present paper aims to generalize the algorithm for the case of spline approximation of multivalued functions making allowance for the design features of the routes of linear structures.
Methods. At the first stage, a novel mathematical model is developed to apply the dynamic programming method taking into account the constraints on the desired spline parameters. At the second stage, nonlinear programming is used. In this case, it is possible to analytically calculate the derivatives of the objective function with respect to the spline parameters in the absence of its analytical expression through these parameters.
Results. An algorithm developed for approximating multivalued functions given by a discrete series of points using a spline consisting of arcs of circles conjugated by line segments for solving the first stage of the problem is presented. An additional nonlinear programming algorithm was also used to optimize the parameters of the resulting spline as an initial approximation. However, in the present paper, the first stage is considered only, since the complex algorithm of the second stage and its justification require separate consideration.
Conclusions. The presented two-stage spline approximation scheme with an unknown number of spline elements is also suitable for approximating multivalued functions given by a sequence of points on a plane, in particular, for designing a route plan for linear structures.
The authors declare that there are no conflicts of interest present.