Задача мин-ции пути сверлильного станка с чпу или ЗК[РЕШЕНО]

[Гармонист]

чем больше точек есть рядом с каждой - тем менее ценной она становится [1]

может ты хотел сказать "более ценной она становится", а не менее?

[1.1] не просто складываем количество всех точек, а производим расчет так - 1/расстояние до первой точки + 1/расстояние до второй точки + ... + 1/расстояние до последней точки.

а не долго ли получится: более 100 раз(если всего точек больше 100) считать расстояния до всех точек, из заданной точки?
100 по 100 получается 10000 раз = экспонента, от которой мы пытаемся уйти.
В чем оптимизация?

У меня идея относительно самой задачи:

может просто в этих местах при чистовом(или 2м черновом) проходе - вставить код уменьшения скорости подачи в 10 раз,
а после прохождения этих глубоких и узких мест - снова увеличить подачу как и была.
И не нужно будет решать алгоритм минимизации пути сверлильного станка...
Проблема ведь в недостаточной жесткости станка и как следствие - фрезер при большой высоте рельефа не успевает снять нужное кол-во катериала, этот материал накапливается и фреза ломается. Если уменьшить подачу, все должно быть тип-топ(по идее).
Кто что думает по поводу идеи и причин поломки тонких фрез при высоком рельефе на нежестком станке?
Может я не правильно понимаю причину по которой фрезы ломаются?

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

[michael-yurov]

может ты хотел сказать "более ценной она становится", а не менее?

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

а не долго ли получится: более 100 раз(если всего точек больше 100) считать расстояния до всех точек, из заданной точки?
100 по 100 получается 10000 раз = экспонента, от которой мы пытаемся уйти.
В чем оптимизация?

В том что это всего лишь вторая степень, а не сотая! Получается очень значительная оптимизация.
Для современных процессоров произвести 10 000 математических операций - это 1/300 000 доля секунды!
Мы пытаемся уйти не от экспоненты, а от факториала! это огромная разница.

Осознание гениальности этого решения даже до меня самого не сразу дошло.
Вероятно, алгоритм можно еще немного улучшить, т.к. в чистом виде он может оказаться слишком сырым, но, результат должен быть очень достойным.
Например, при значительном заполнении точками усредненную траекторию обхода можно сделать подобно выборке 2d фигуры змейкой, или по спирали, как в CAM программах.
А можно - проще, и, возможно, даже лучше - увеличив приоритет выбора тех точек, которые находятся ближе к ранее пройденным. Тогда данный эффект получится сам собой.
Опять же кому это все надо?

[michael-yurov]

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

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

[Serg]

Мы пытаемся уйти не от экспоненты, а от факториала! это огромная разница.

Нет в этой задаче факториала. Тупым перебором задача решается за N(N+1)/2 итераций.

[michael-yurov]

Нет в этой задаче факториала. Тупым перебором задача решается за N(N+1)/2 итераций.

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

Я тоже с разбегу заглянув в эту тему так же ошибся:

ОЙ, и правда, что-то я все перепутал.
Я перепутал с задачей поиска кратчайшего маршрута.

[Serg]

Так сумма кратчайших путей для подобных случаев и даст путь, очень близкий к оптимальному. А если, как я предлагал в самом начале, всю площадь ещё и побить на квадраты, то результат будет ещё ближе, а вычисления в разы меньше.
Не, можно конечно в течении нескольких часов рассчитать идеальную траекторию и выполнить её минут за 20, вместо того, чтобы комп целых 10 минут расчитывал приблизительную траекторию, которую станок будет исполнять аж полчаса...

[michael-yurov]

Если точек 100, то 100! (факторил) это уже 158-значное число количества операций . Вычислять современный компьютер будет далеко не пол часа...
По моему алгоритму придется сделать около 10 000 операций (+/- порядок), вычисление займет малые доли секунды даже для тысяч точек.
Результат будет намного (на минуты / десятки минут) лучше, чем если просто побить территорию на квадраты.
Я уже устал доказывать, что я не тюлень.

[Serg]

Это несправедливо! Почему тогда по моему алгоритму у тебя получается 100! (факторил), если я уже тоже устал доказывать, что никакого факториала не надо?

Пусть будет 100 точек. Берём первую точку и сравниваем её с 99 оставшимися, т.е. делаем 99 итераций. Из этих 99 выбираем (по тем критериям, которым надо) очередную и сравниваем её с 98 оставшимися, т.е. ещё 98 итераций. И так далее пока точек не останется. Где тут факториал?

Гармонист, дай УП, картинку которой ты привёл в начале (проход по этим точкам) - пора уже сгенерить массив точек и пробовать.

[michael-yurov]

Хорошо, взяли первую точку.
Как найти следующую? Ближайшую взять? это и будет простейший "жадный алгоритм", там, конечно, никакого факториала не будет.
А вот если попытаться перебрать все варианты прохождения пути, то вариантов оказывается очень много.

(по тем критериям, которым надо)

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

[Serg]

Как найти следующую? Ближайшую взять?

Можно и так, но необязательно. Можно например отдавать предпочтение чуть более дальней точке, но лежащей например почти рядом по X - тут уже можно делать поправку на особенности механики станка.
А деление на зоны (квадраты или полосы) позволит в разы сократить количество итераций, за счёт несущественного увеличения общего пути.

[michael-yurov]

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

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

[Serg]

На суммы принципиально не спорю, но попробовать готов. Выше уже просил исходные данные.

[michael-yurov]

Чуда не произошло. Обидно.
Радует то, что мой алгоритм оказывается всегда умнее "жадного".

В общем - вот, состряпал:

optimizator.zip

(2.86 МБ) 368 скачиваний

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

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

[Гармонист]

По сути здесь 2 задачи - одна - задача кластеризации данных(если её опустить - получится простой жадный алгоритм), а 2ая - задача нахождения пути.

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

это как раз - задача кластеризации.

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

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

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

результаты работы жадного алгоритма

недостатки жадного алгоритма

недостатки жадного алгоритма - траектория обхода точек

Как видите(нужно приблизить - так не видно ) - длина синих линий значительно сократилась...
Сравните с картинкойиз 1го поста.

Если добавить еще и разбиение на кластеры, то будет савсем - чудесно

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

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

Вот я и смог придумать и сформулировать эти критерии, это и есть решение.

спасибо, я покручу твой алгоритм...

Выше уже просил исходные данные.

программу временно разламал когда усовершенствовал. Когда починю - выложу...

[michael-yurov]

спасибо, я покручу твой алгоритм...

Как оказалось - не стоит. Он получился заметно медленнее "жадного", но не на много оптимальнее.
Получилось что-то вроде улучшенного "жадного" алгоритма с регулировкой жадности.

программу временно разламал когда усовершенствовал. Когда починю - выложу...

Что вообще никак?
Дай для пробы хоть в каком нибудь виде?, а я попробую в свою программку засунуть.

Гармонист, а у тебя волны круглые или ромбообразные?
А то я думаю, они вообще должны быть квадратными (даже прямоугольными, если максимальные скорости осей станка разные), т.к. оси движутся независимо, и время не на прямую зависит от расстояния.

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

[Serg]

Если добавить еще и разбиение на кластеры, то будет савсем - чудесно

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

[Гармонист]

Дай для пробы хоть в каком нибудь виде?

вечером

а у тебя волны круглые или ромбообразные?

для скорости - квадратные

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

не понял

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

попробую

[michael-yurov]

писал(а):
Лучше сделать короткие переходы прямо по рельефу, без подъема, тогда время обработки сильно сократится.

не понял

Я, вероятно, не правильно понял начальную задачу. Потом почитаю, отвечу понятно.

[Тандем]

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

Это генетические алгоритмы. Берётся надцать случайных решений поставленной задачи. Потом эти решения скрещиваются (часть решения берётся от одного предка, часть - от другого), мутируют (некоторая часть решения изменяется). Затем происходит отбор, и самые отстойные решения выбрасываются. Снова скрещивание и мутация, и так по кругу, пока наблюдается общее повышение уровня решений. Насколько я понял, на данный момент один из самых эффективных методов решения таких задач - получение результата, близкого к оптимальному, при относительно небольшом времени работы.

[Nick]

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

Очень часто все останавливается в локальном минимуме и дальше не идет... Плюс не всегда просто составить описание случая через гены и описать скрещивание и мутации. Хот я в нашем случае это вроде достаточно просто...

ЗЫ делал таким алгоритмом расстановку для оптимизации раскроя: Gcode tools - расширение для плазмы #35