Традиционные жадные алгоритмы пасуют перед плотными структурами, заставляя инструменты ЧПУ и роботов метаться по всей рабочей зоне. В этой статье я представляю «Алгоритм Динамического Шампура» (Shampur-Scraper Method) — иерархический подход к задаче коммивояжера, сочетающий инерционное планирование магистралей и динамическую зачистку зон ответственности. Разберем логику «Скребка», эффект «напряжения тупиков» и посмотрим, как этот метод играючи справляется с самопересекающимися трилистниками и плотными спиралями за доли секунды.
Вступление
Представьте, что вам нужно пропылесосить комнату, но ваш робот-пылесос двигается как пьяный курьер: засасывает пылинку в одном углу, внезапно прыгает в другой, возвращается за пропущенным клочком и снова улетает. В мире ЧПУ и промышленной робототехники это называется «проблемой избыточных холостых переходов». В деньгах это означает:
+40% времени цикла на ЧПУ станках
Лишний износ инструмента от холостых прогонов
Брак из-за рассинхрона при многопроходной обработке
Классическая задача коммивояжера (TSP) на больших массивах (10k+ точек) либо решается мучительно долго, либо превращается в «сито» из перелетов. Мы решили подойти к этому с кулинарной точки зрения и разработали метод «Динамического Шампура» (Shampur-Scraper Method).
Проблема: почему «жадность» — это плохо
Обычно точки обходят методом ближайшего соседа. На простых фигурах это работает. Но попробуйте скормить такому алгоритму плотную спираль или самопересекающийся трилистник. Из-за геометрической «слепоты» алгоритм начинает прыгать между витками, пробивая структуру насквозь.
Рис. 1: Красные линии — это "прыжки" жадного алгоритма. Заметьте, как он протыкает спираль насквозь вместо того, чтобы идти по витку.
Почему существующие методы не работают?
Точное решение (Branch-and-Bound):
✅ Идеально, но O(n!) — для 10k точек считает до конца Вселенной
Эвристики (LKH, Christofides):
✅ Быстрее, но все равно секунды/минуты на больших данных
❌ Не учитывают топологию (прыгают между ветками)
Жадные алгоритмы:
✅ Мгновенно, но...
❌ Хаос на сложных фигурах (см. Рис. 1)
Нужен был новый подход.
Уровень 1: Генплан и инерция
Мы разделили управление на «мозг» и «руки».«Мозг» — это Генплан (Roadmap). Мы не смотрим на каждую точку, мы строим магистраль через локальные центры масс.Но чтобы магистраль не «коротила» на поворотах, мы внедрили инерционный штраф. Если путь предлагает резко повернуть на 90 градусов (прыгнуть на соседнюю ветку), алгоритм "Штрафует такие переходы" и заставляет ехать прямо по «рельсам» своей петли. Представьте поезд: если он едет на север, то затормозить и развернуться на юг — это ДОРОГО (в терминах штрафа расстояния), а плавно повернуть налево — ОК. Именно так работает инерционный генплан.
Рис. 2: Желтая звезда — это вход - случайный. Синий цвет и стрелки указывают направление движения (от холодного к теплому). Ромбы - тупики.
Уровень 2: Скребок и «напряжение тупика»
«Руки» — это сам Скребок (Scraper). Когда мы заходим в зону ответственности конкретного узла, мы не просто бежим к выходу. Мы используем динамический наклон линии отреза.Линия «чувствует» плотность остатка. Если где-то на периферии остался аппендикс (тупик), линия наклоняется так, чтобы сначала «вымести» его, прижимая основной массив точек к выходу. Мы назвали это «эффектом дворника».
Динамический баланс между выходом и зачисткой
v_exit = direction_to_exit() # Куда идти
v_cleanup = direction_to_remains() # Что осталось
v_aim = v_exit 0.7 + v_cleanup 0.3 # Магия!
Результаты: когда остаток равен 0
"Ключевой результат"
Спираль: 10 000 точек проходятся одним плавным витком.
Трилистник: Самопересечения пролетаются насквозь без «соскакивания» на чужую колею.
Скорость: Обработка всей геометрии занимает доли секунды.
Метод | Время | Остаток | Прыжки |
|---|---|---|---|
Greedy (жадный) | 0.12s | 0 | 847 😱 |
Christofides | 1.45s | 0 | 234 |
Shampur-Scraper | 0.82s | 0 | 0 ✅ |
Где это работает?
✅ Производство:
ЧПУ фрезеровка сложных контуров
Лазерная резка/гравировка
Робо-покраска автомобилей
✅ Аддитивное производство:
3D печать (оптимизация путей экструдера)
Биопринтинг органов (непрерывность критична!)
✅ Инспекция:
Автоматическое сканирование дефектов
Планирование путей дронов
Итог
Метод уже находится на регистрации в Роспатенте. Он применим везде, где важна непрерывность: от печати органов на биопринтерах до лазерной резки сложнейших узоров. Мы доказали: чтобы навести порядок в хаосе, иногда достаточно просто хорошего «Шампура».
Проект полностью покрыт Unit-тестами (40 сценариев через pytest). Мы проверили всё: от классической зачистки спирали до экстремальных краевых случаев — коллинеарных точек, микроскопических зон и работы в условиях численной нестабильности. Особое внимание уделили L-образным структурам, чтобы гарантировать: алгоритм "чувствует" изгиб и не совершает прыжков даже на сложных углах
код пока не доступен на GitHub
Видео ссылка https://youtu.be/vzzTfpdrSa8
Что дальше:
⭐ Поставьте звезду, если интересно
💬 Напишите в Issues, для каких задач хотите попробовать
🤝 Коммерческое использование? Напишите в личку
P.S. Если вы из Siemens или Autodesk — у нас есть что обсудить 😉
