Алгоритм наискорейшего обхода точек 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 я вопрошаю не по численным методам, а по постановке, применительно к указанной постановке тот численный метод, который я описал будет одним из наилучших, но меня не устраивает. Возможно чем-то для такого типа задачи можно пренебречь и получить более простой метод, только что в этом случае необходимо поменять в постановке?

Спасибо

ИИВ

[blackfin]

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

Если пренебречь «N точек в 3-х или 4-х мерном пространстве» и ограничиться «N точек в 2-х мерном пространстве», и рассматривать частный случай равномерного движения, то получается классическая задача коммивояжёра, о которую за последние 200 лет было сломано немало копий..

Упс.. Пардон, уже было..

[_pv]

Если пренебречь «N точек в 3-х или 4-х мерном пространстве» и ограничиться «N точек в 2-х мерном пространстве», и рассматривать частный случай равномерного движения, то получается классическая задача коммивояжёра

В 3D ничем принципиально не отличается, только как уже было отмечено, линейное перемещение с постоянным (максимальным) ускорением половину пути и торможением вторую половину пути от точки к точке, с остановкой в ней - самый простой, но не самый оптимальный по общей средней скорости обхода метод.
тут наверное действительно можно назначить каждой точке некий момент времени t[i], между каждой парой точек проложить кубический сплайн, Xi(t) = Ax0 + Ax1 * t + Ax2 * t^2 + Ax3* t^3. y(t), z(t)..., с требованием непрерывности производных в точках. После нахождения коэффициентов проверить не вышли ли скорости/ускорения за заданные пределы, и
потом подвинуть в нужную сторону назначенные параметры t[i] у соответствующих точек и повторить.

[iiv]

тут наверное действительно можно назначить каждой точке некий момент времени t[i], между каждой парой точек проложить кубический сплайн, Xi(t) = Ax0 + Ax1 * t + Ax2 * t^2 + Ax3* t^3. y(t), z(t)..., с требованием непрерывности производных в точках. После нахождения коэффициентов проверить не вышли ли скорости/ускорения за заданные пределы, и
потом подвинуть в нужную сторону назначенные параметры t[i] у соответствующих точек и повторить.

да, именно это решение я сейчас и использую, и именно с ним я открыл 2 апреля этот топик.

[_pv]

да, именно это решение я сейчас и использую, и именно с ним я открыл 2 апреля этот топик.

чукча - писатель.

[iiv]

чукча - писатель.

да не, не в обиду! Мне это решение как раз и не понравилось, так как я применил для его решения достаточно продвинутый математический аппарат (методы БФГС, Бройдена, Бауэра-Штрассена), то есть мне это конечно не сложно, и я могу гарантировать как вычислительный математик достигаемую точность и однозначность решения.

Кстати, для тех, кому интересно для чего все это, есть пример на пальцах в 2Д случае: на столе лежат детальки, надо их перетасовать, порядок перетасовки уже вычислен, фактически сверху над столом летает присоска, которая пролетая над деталькой ее присасывает, летит в нужное место, и там бросает, и так далее. Если каждый раз полностью останавливаться перед присасыванием/отсасыванием, то время работы на реальной задаче получалось в полтора раза больше, чем если пролетать не останавливаясь, а на качество работы аппарата это не влияло, так как присос/отсос идет в вертикальной оси.

В моем случае исходная задача похожа, но формулируется на вогнутой поверхности, и присоска может быть еще правильно направлена (еще две оси), поэтому я и искал решение на >2D, и, не такое крокодилистое, как у меня получилось... С другой стороны, работает, ну и ладно, по крайней мере время вычисления коэффициентов таких оптимальных сплайнов мною полученным алгоритмом даже на арме существенно меньше время полета присоски, но ведь всегда хочется элегантности, а не элефантности, решения!

[_pv]

(методы БФГС, Бройдена, Бауэра-Штрассена)

даже как-то лень смотреть кто все эти люди.
а нельзя после того как нашли коэффициенты сплайнов и увидели что максимальная скорость на участке между двумя любыми точками отличается на dV заданной максимальной, просто подвинуть моменты времени посещения всех последующих точек на dt = Si / dV.
за несколько проходов оно в результате сойдётся к траектории с нужной максимальной скоростью, ну и с ускорением также.