Карпов Дмитрий Анатольевич, к.т.н., заведующий кафедрой общей информатики Института кибернетики
119454, Москва, пр-т Вернадского, д. 78
Dmitry A. Karpov, Cand. Sci. (Eng.), Head of the General Informatics Department, Institute of Cybernetics
78, Vernadskogo pr., Moscow, 119454
Струченков Валерий Иванович, д.т.н., профессор, кафедра общей информатики Института кибернетики
119454, Москва, пр-т Вернадского, д. 78
Valery I. Struchenkov, Dr. Sci. (Eng.), Professor, General Informatics Department, Institute of Cybernetics
78, Vernadskogo pr., Moscow, 119454
В статье компьютерное проектирование трасс линейных сооружений рассматривается как за-дача сплайн-аппроксимации. Принципиальной особенностью соответствующих проектных задач является то, что план и продольный профиль трассы состоят из элементов заданного вида. В зависимости от типа линейного сооружения используются отрезки прямых, дуги окружностей, парабол второй степени, клотоид и др. В любом случае результатом проектирования является кривая, состоящая из нужной последовательности элементов заданного вида. В точках сопряжения элементы, как правило, имеют общую касательную, а в наиболее сложном случае – и общую кривизну. Подобные кривые принято называть сплайнами. В отличие от других применений сплайнов в проектировании трасс линейных сооружений приходится учитывать многочисленные ограничения на параметры элементов сплайна, возникающие из необходимости соблюдения технических нормативов с целью обеспечения нормальной эксплуатации будущего сооружения. Технические ограничения формализуются в виде системы неравенств. Главная отличительная особенность рассматриваемых проектных задач состоит в том, что число элементов искомого сплайна неизвестно и должно быть определено в процессе решения задачи. Это обстоятельство принципиально усложняет задачу и не позволяет применить для ее решения математические модели и алгоритмы нелинейного программирования, так как неизвестна размерность задачи. В статье предлагается двухэтапная схема сплайн-аппроксимации плоской кривой, заданной последовательностью точек, при неизвестном числе элементов сплайна и наличии ограничений на параметры его элементов. На первом этапе определяется число элементов сплайна и приближенное решение задачи аппроксимации. Используется метод динамического программирования. На втором этапе выполняется оптимизация параметров элементов сплайна. Используются алгоритмы нелинейного программирования, разработанные с учетом особенностей системы ограничений. При этом на каждой итерации процесса оптимизации для соответствующего набора активных ограничений строится базис в нуль-пространстве матрицы ограничений. Это позволяет найти направление спуска и решить вопрос об исключении ограничений из активного набора без решения систем линейных уравнений вообще, а в наиболее сложных случаях − решая линейные системы малой размерности. В качестве целевой функции наряду с традиционно используемой суммой квадратов отклонений аппроксимируемых точек от сплайна в статье предлагаются другие функции с учетом специфики конкретной проектной задачи.
In the article, computer design of routes of linear structures is considered as a spline approximation problem. A fundamental feature of the corresponding design tasks is that the plan and longitudinal profile of the route consist of elements of a given type. Depending on the type of linear structure, line segments, arcs of circles, parabolas of the second degree, clothoids, etc. are used. In any case, the design result is a curve consisting of the required sequence of elements of a given type. At the points of conjugation, the elements have a common tangent, and in the most difficult case, a common curvature. Such curves are usually called splines. In contrast to other applications of splines in the design of routes of linear structures, it is necessary to take into account numerous restrictions on the parameters of spline elements arising from the need to comply with technical standards in order to ensure the normal operation of the future structure. Technical constraints are formalized as a system of inequalities. The main distinguishing feature of the considered design problems is that the number of elements of the required spline is usually unknown and must be determined in the process of solving the problem. This circumstance fundamentally complicates the problem and does not allow using mathematical models and nonlinear programming algorithms to solve it, since the dimension of the problem is unknown. The article proposes a two-stage scheme for spline approximation of a plane curve. The curve is given by a sequence of points, and the number of spline elements is unknown. At the first stage, the number of spline elements and an approximate solution to the approximation problem are determined. The method of dynamic programming with minimization of the sum of squares of deviations at the initial points is used. At the second stage, the parameters of the spline element are optimized. The algorithms of nonlinear programming are used. They were developed taking into account the peculiarities of the system of constraints. Moreover, at each iteration of the optimization process for the corresponding set of active constraints, a basis is constructed in the null space of the constraint matrix and in the subspace – its complement. This makes it possible to find the direction of descent and solve the problem of excluding constraints from the active set without solving systems of linear equations. As an objective function, along with the traditionally used sum of squares of the deviations of the initial points from the spline, the article proposes other functions taking into account the specificity of a particular project task.
The authors declare that there are no conflicts of interest present.