Алгоритм наискорейшего обхода точек CNC/ЧПУ роутером Опции

[iiv]

Добрый день,

возник вопрос, и простого решения не увидел...

Пусть есть N точек в 3-х или 4-х мерном пространстве осей ЧПУ-шного станка. Необходимо их последовательно посетить, так чтобы скорость и ускорение каждой оси не превышали заданные - фактически такие ограничения связаны с тем, что мотор не может очень быстро крутиться и очень быстро разгоняться. Задача вроде бы должна быть очень распространенная, но решение у меня получается достаточно не тривиальным.

Пусть для простоты у нас 3-х координатный станок, начальное и конечное значения скоростей равны 0. Для решения я взял неизвестную временнУю сетку t_0=0 < t_1 < t_2 < ... < t_N, на ней строю три кубических сплайна по одному на каждую ось. Коэффициенты этих сплайнов зависят от t_1, ..., t_N и от соответствующих координат точек обхода (которые даны) и их легко за 15N арифметических операций можно вычислить методом прогонки. Нам надо минимизировать t_N с учетом ограниченности первой и второй производных всех трех сплайнов. Понятно метод отжига (simulated annealing) успешно эту задачу решит, но как-то немного громоздко выходит...

Скажите, пожалуйста, а есть ли что-то проще? EDIT я вопрошаю не по численным методам, а по постановке, применительно к указанной постановке тот численный метод, который я описал будет одним из наилучших, но меня не устраивает. Возможно чем-то для такого типа задачи можно пренебречь и получить более простой метод, только что в этом случае необходимо поменять в постановке?

Спасибо

ИИВ

[Guest_TSerg_*]

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

Если бы мы в эпоху слабых бортовых машин в 60..70-е годы (50..500 коп/сек, 8..64 кб памяти) использовали бы теоретические изыски, которые предлагаете Вы, то не было бы и страны, уж поверьте.

Итак:
Пока упрощаем до 2D, но без ограничения общности:

Двух-координатный планшет - это два двигателя, в первом приближении - апериодические звенья.
Управление вектором скорости в нацеливании на очередную точку сводится, в таком случае, к аналогу движения динамической точки с ограничением на угловую скорость, которая зависит от инерционности двух каналов.
Что означает ограниченная угловая скорость?
Она означает ограниченный радиус циркуляции объекта.
Очевидно, что он зависит от линейной скорости - чем выше линейная скорость, тем больше радиус циркуляции.

Какие выводы отсюда?
Если нам удалось набрать макс. скорость, то известен радиус циркуляции при любом повороте.
Это означает, что известна геометрия движения между точками.
И, в общем случае: при любой скорости движения известен предполагаемый радиус циркуляции, что позволяет строить траекторию, нацеленную на касание окружности циркуляции, в точке касания с которой начнется поворот по допустимым для динамической системы параметрам.

Дальше - обычная школьная геометрия в построении траектории + курс физики "динамика".

[iiv]

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

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

Если бы таки со второй производной удалось что-то аналитическое получить, тогда да, было бы очень-очень классно, это я собственно и искал, больше чисто из спортивного интереса, так как громоздкое, но надежное решение еще в при открытии этой темы у меня было.

А словам, которые я описал выше, боятся не следует, асимптотика у всех этих алгоритмов линейная, то есть имея N точек, арифметическая сложность вычисления тоже будет около N на некоторую, хоть и большую, но константу, конечно АВРка не потянет, но кортекс М3 думаю сможет, хотя я на пс-дуино это все сделал, на нем оно летает.