Добрый день,

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

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

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

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

Спасибо

ИИВ

Читаем любой учебник по численным методам - поиск минимума (экстремума) . За метод Ньютона Нобелевскую премию дали(по экономике)

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

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

Здесь наверное ведь цель (целевая функция) как чаще всего - минимизация времени обработки?
А условия-ограничения - на скорости и ускорения.
И тогда оптимум - минимум длины траектории движения инструмента, если он один и не меняется.
Я в этой области не специалист, так, знакомился немного.
Но разве нет готовых алгоритмов оптимизирующих обработку при создании CNC?

Даже без учёта динамики двигателей, учитывая только расстояния между точками, Вы получаете известную "задачу коммивояжера".
А она NP-полная
Зато есть где разгуляться в поиске алгоритмов поиска квазиоптимальных решений.

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


не, последовательность задана, комивояжера не надо

Ant Colonies

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

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


статья классная, спасибо, но я не об этом, в моей задаче-то надо посетить только в определенной последовательности.

Вообще то, тут три задачи:

1. посетить точки в оптимальном порядке и сгенерировать прямыми и кривыми требуемый маршрут;
2. аппроксимировать все линейными перемещениями с заданной точностью;
3. сгенерировать последовательность управления шаговиками опираясь на максимально возможное ускорение и скорость перемещения.

По 3 пункту ищите по фразе cnc lookahead algoritm. Например https://hal.archives-ouvertes.fr/hal-00986174/document

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

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

стандартная общеизвестная информация:
управляющее ПО имеет настраиваемые ограничения для каждой оси. При конфигурировании роутера числовые параметры макс.скорости и ускорения задаются из известных значений на каждый двигатель или эмпирических.

команда типа x100 y100 z100 перемещает инструмент в точку 100:100:100 всеми тремя осями одновременно со скоростью и ускорением самой медленной оси.

почему прямое попадание инструментом в каждую точку не катит?

Катит-катит, только не обязательно в точке останавливаться.

Пусть Вам надо по циклу обежать 4 точки, которые находятся в вершинах квадрата, а у Вашего инструмента есть ограничение на производную и скорость. Пусть квадрат достаточно мал, что инструмент не успеет разогнаться и ограничение по скорости не играет роли. В этом случае обход этих точек по прямым линиям - суть сторонам квадрата будет в 1.7 раз дольше (2^{3/4}), чем если траектория инструмента будет окружность, в которую вписан этот квадрат.

Ну, а если надо фрезеровать все же квадрат, а не окружность?
Без ТЗ это просто болтовня.