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

Спасибо

ИИВ

[mcheb]

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

[iiv]

Читаем любой учебник...

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

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

[fider]

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

[SSerge]

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

[iiv]

И тогда оптимум - минимум длины траектории движения инструмента, если он один и не меняется.
Но разве нет готовых алгоритмов оптимизирующих обработку при создании CNC?

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

А она NP-полная

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

[Fat Robot]

Ant Colonies

[iiv]

Скажите, что значит 'посетить'?

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

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

Ant Colonies

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

[halfdoom]

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

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

[dpss]

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

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

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

[Guest_TSerg_*]

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

[MiklPolikov]

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

[Ydaloj]

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

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

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

[iiv]

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

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

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

[Guest_TSerg_*]

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

[iiv]

Вот я Вас большинство тут не понимаю...
Написано:
1. последовательно обойти точки, а народ советует как мне оптимизировать или решать задачу поиска последовательности...
2. вот спрашиваю о наименьшем времени, а тут какие-то вопросы что да как мне фрезеровать.

Вот зачем сотрясать воздух советами не по теме? Что не ясно?

Ну, а если надо фрезеровать все же квадрат, а не окружность?

я хоть где-то говорил, что надо квадрат фрезеровать? Вот как например этот комментарий согласуется с постановкой?

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

DPSS огромное спасибо за путевую ссылку, всем остальным, спасибо за ля-ля.

[Guest_TSerg_*]

Для того и надо "ля-ля", чтобы в общей массе у кого-то сработала телепатия.

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

http://elar.urfu.ru/bitstream/10995/24848/...-2006-46-03.pdf

P.S.
Пример для 2D
Убегающих считать неподвижными.

[RCray]

У меня вопрос к постановке, a не к решению. Mожно ли представить все точки узлами, а каждому ребру задать вес (исходя из доп параметров - скорость и тд)? Тут про графы уже правда упоминали.

[Guest_TSerg_*]

ТС, похоже, сам не понимает, что же он хочет.
Сделать открытие в математике или реализовать инженерное решение.

[iiv]

ТС, похоже, сам не понимает, что же он хочет.
Сделать открытие в математике или реализовать инженерное решение.

у меня и без этого есть открытия, суммарный индекс цитирования моих статей за 70 уже перевалил, среди них и Нейчер, и Джаксы. А вот чтобы так в сердцах ка Вы написали, мне такое писать, я ожидаю, что и у Вас хотя бы такие же публикации и открытия имеются, а если нет, то будьте любезны, прочитать постановку и, если есть что ответить по сути, то писать, а если нет то воздержаться от комментариев не по теме.

[Guest_TSerg_*]

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

[RCray]

В споре может рождаться и постановка задачи, и истина... Если не переходить на личности.

[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] у соответствующих точек и повторить.

[Guest_TSerg_*]

Да ладно.. в инженерной постановке все решается за 5 мин.

По словам ТС, если я правильно понял задачу, которую он так и не прояснил, задача стоит в посещении N точек в заданном уже порядке за минимальное время.

Остаются вопросы по траектории посещения точек и погрешности их посещения:
- линейная;
- произвольная;
- погрешность есть/нет ( примеры: есть - сервопривод, нет - шаговый привод).

При линейной траектории - все просто, оптимальное управление процессами разгона/торможения известной динамической системы.

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

Все. Инженерная задача решена методом обычных школьных геометрии и физики.

[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, и, не такое крокодилистое, как у меня получилось... С другой стороны, работает, ну и ладно, по крайней мере время вычисления коэффициентов таких оптимальных сплайнов мною полученным алгоритмом даже на арме существенно меньше время полета присоски, но ведь всегда хочется элегантности, а не элефантности, решения!

[Guest_TSerg_*]

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

Звучит красиво и, наверняка, повлияет на индекс цитируемости, а на деле - достаточно обычной геометрии и школьника 60-х годов выпуска.
Без обид

[_pv]

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

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

[iiv]

Звучит красиво и, наверняка, повлияет на индекс цитируемости, а на деле - достаточно обычной геометрии и школьника 60-х годов выпуска.
Без обид

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

[Guest_TSerg_*]

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

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

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

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

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

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

[iiv]

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

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

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

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

[Guest_TSerg_*]

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

[RCray]

del