Comments 35
Дип ленинг - это когда чип и дейл спешат на помощь к Ленину? Уберите, пожалуйста, англицизмы из статьи
Нейросеть может подсказать в какую сторону копать, чтобы быстрее найти путь. Но уменьшает ли это общую стоимость поиска? Нейросеть же тоже "не бесплатная" и делает кучу своих поисков.
Раз уж мы говорим о том, что для работы алгоритма хорошо бы использовать GPU, есть ли версии а*, оптимизированные под параллельные выполнения? (Кажется логичным что должны быть) Не было бы логичнее сравнить результаты с таким решением?
Про то, что наработки пригождаются на классе задач посложнее - интересно. Но тоже не до конца понятно, не является ли это оверкиллом по сравнению с сеткой, считающей исключительно добавочную стоимость и проходом по ней а*-ом.
Если что, я сам люблю теоретические вопросы, просто хотелось бы более детально почитать про сравнения результатов с точки зрения памяти/времени
Сравнение поисковых алгоритмов с т.з. времени/памяти не так просто, как может показаться на первый взгляд (по моему мнению). Сильно зависит от реализации. Тот же «стандартный» A* можно реализовать многими разными способами, с использованием различных структур данных для хранения промежуточ.вычислений. Например, можно иметь дубликаты в open и ленивую схему их удаления, но при этом open будет priority queue (по f-значению). А можно сделать два контейнера под open (один для сортировки по f, другой для хранения по id элементов) и обойтись без дубликатов вообще. Можно вообще отказать от хранения род.указателей (и восстанавливать искомый путь в конце по рассчитанным g-значениям). И так далее. Это я к тому, что в целом сравнить «два поисковых алгоритма» по времени работы - непросто. Вернее даже так, сравнить можно, но как трактовать цифры и какие выводы делать из цифр - вопрос. Конечно, всё равно такие сравнения проводят, считая что тот, кто видит результаты - в состоянии сам их проинтерпретировать. В этом плане сравнение «по итерациям» более «устойчиво» и поэтому им часто пользуются.
По «параллельному А*». Я точно встречал статьи, где речь шла именно о распараллеливании поиска «по итерациям» (и там всё не так просто). По параллельной обработке разных заданий батчами на gpu - не встречал. Но это не значит, что их нет. Надо посмотреть. В целом - предложение по такому сравнению очень разумное, да!
Про доп.стоимость - отвечу чуть позже (сейчас в метро, выходить пора :) )
По поводу добавочной стоимости. Мне идея автором Neural A* изначально не очень нравится, т.к. они оценивают (с помощью нейросети) именно что доп. стоимость вершин, НО на самом деле может быть такое, что стоимость попадания в вершину разная в зависисмости от того, а из какой смежной вершины мы в неё попадаем.
В своих экспериментах по планированию на картинках мы рассматриваем такой сценарий - пусть у нас на этапе обучения есть RGB картинка ландшафта (вид сверху) + DEM (digital elevation model) этого ландшафта (т.е. карта высот). И нам нужно построить путь для условного марсохода, которому нежелательно забираться в крутые горки и так далее. В этом случае важно собирать путь именно из ребер графа (переходом между пикселями картинки). Потому что если мы в какую-то вершину пришли с одной строны и без перепада высоты, то это ок, а если с другой стороны и там был перепад высоты, то "это другое".
В целом NeuralA* обуславливается на старт-финиш (насколько я помню) поэтому, по идее это обстоятельство как-то должно улавливаться сеткой. Тем не менее идея определять всё через стоимость вершин (а не стоимости переходов между вершинами) мне кажется не такой уж идеальной.
В общем, скажу так. Если у есть задача планирования по картинкам и на этапе обучения есть только примеры путей по этим картинкам, то тут, наверное, только схема NeuralA* и поможет (хоть она и не идеальная). Если же у нас на этапе обучения есть чуть больше информации (например, есть датасет RGB+DEM, который позволяет нам самим строить не только один путь при решении конкретной задачи но и "путевую колбасу"), то я бы всё-таки советовал TransPath (наш подход) применять.
А что мешает рекурсивно аналитически найти полярные границы препятствия и просто обойти его безо всяких А°? Графы на ваших картинках обходятся так не более чем за 10 шагов.
Давайте я сначала кое-что уточню, а потом отвечу вопросом на вопрос.
Уточнение: в статье картинки задания выглядят «непрерывно», но это сделано доя удобства восприяьия. на входе у нас имеется карта закодированная в виде матрицы с 0 и 1. Там где 1 - клетка заблокирована. Более наглядное представление (с «дискретными клетками») показано на втором рисунке в статье (там где кружочками цветными старт и финиш отмечены).
Вопрос: как по такому дискретному входу (быстро) найти аналитические границы препятствий? В целом - я не до конца понял мысль. Если получится её развернуть и пояснить, будет интересно обсудить.
Идём по белым клеткам вдоль прямой между двумя точками, пока не встретим чёрую. От неё идём по чёрным в лево и вправо, пока не найдём самые крайние. получаем 2 кандидата напромежуточную точку. Повторяем алгоритм от промежуточной до финальной и от начальной до промежуточной.
Я когда-то занимался такими алгоритмами. Да чего уж там, моя канд. диссертация была посвящена именно подобному алгоритму. Мне тогда удалось доказать, что все будет хорошо работать в случае простейших выпуклых фигур ala прямоугольники. Но в общем случае (а нас интересует именно общий случай) - всё не так просто. Когда появляются всякие лабиринты и спирали, то можно и зациклиться.
PS: В непрерывном случае отмеченная стратегия имеет название BUG алгоритм (публикация Люмельского от 79-го чтоли года). Там всё сходится, путь гарантируется, но длине его получается ой-ой-ой.
Детектировать циклы не сложно ведь.
Мне так не показалось, когда я этим занимался. Конечно, в случае препятствий простых форм - всё просто. Я даже доказывал (и уверен, что правильно доказал) корректность и др. теор.свойства подобного алгоритма, когда писал кандидатскую в 2010. Но в общем случае, мне доказать не удалось.
Если вы знаете научную статью статью, описывающую подобный алгоритм, содержащую формальное доказательство теор.свойств (корректность завершения (в т.ч. на нерешаемом input), оптимальность отыскиваемых решений, алг.сложность и пр.), то мне было бы небезынтересно на неё взглянуть. Поделитесь?
Пришли в точку, в которой уже были - цикл.
В общем я делаю такое предположение, основываясь на нашем диалоге. У вас есть идея некоторого алгоритма, который умеет планированить пути на гриде. При этом самого алгоритма и доказательств его теор.свойств нет.
Что тут можно сказать. Сама по себе идея - кажется очень разумной да. Повторюсь, я сам имел опыт разработки методов на основе этой идеи какое-то время назад (>10 лет). И в некоторых случаях это работало а) очень хорошо б) имело доказанные теор.свойства.
НО в общем случае, когда у нас могут быть, например, вогнутые препятсвия, которые "проникают друг в друга", всякие спирали и "спирали в спирали", у меня не получилось доказать корректность моего алгоритма и/или придумать алгоритм, который был бы корректен (хотя я пытался). Если у вас такое получилось, то это здорово, давайте описание/код - будем смотреть/проверять. Если не у вас, а у кого-то другого есть такой алгоритм - тоже пойдёт, кидайте ссылку.
Дальнейшие рассуждения "на уровне идеи" вряд ли что-то дадут. Да, идея хорошая. Но идея без реализации это не совсем то, что нужно для решения задач.
Но в общем случае (а нас интересует именно общий случай) — всё не так просто
[JumpPointSearch](Но в общем случае (а нас интересует именно общий случай) — всё не так просто) в общем-то на этой идее и работает в общем случае.
BUG - это тоже что-то совсем не то. Оно про полуслепого робота.
Ну насколько я понимаю вы предлагаете примерно тоже самое делать, а именно - "идти напрямую пока не упрешься в препятсвие, а потом обходить препятсвие до какого-то момент", но только "в голове", т.е. на этапе планирования пути, а не на этапе исполнения пути, как в BUG. Поэтому и указал на эту аналогию.
Примерно на такой идее и основан алгоритм JumpPointSearch. Это фактически A* с очень специфичной эвристикой получается. Работает очень быстро.
Совсем не то. LPS - крайне не оптимальный алгоритм, как и все A*.
Хороший контр-пример, на котором JPS "обламывается", да. Но на практике всё-таки он в большинстве случае очень хорош. Скажем, если взять весь бенчмарк MovingAI, а это один из самых распространенных бенчмарков в области grid-based pathfinding, и прогнать на нём JPS vs A*, то на подавляющем большинстве карт/заданий JPS будет прям на порядок быстрее-выше-сильнее.
Можно ли для бинарного грида сделать алгоритм, "уделывающий" JPS в single-shot постановке (т.е. когда запрещен любой предрасчет, и дается грид, старт, финиш и нужно искать) и при этом сохраняющий все теор. гарантии? Не знаю. Наверное, можно. Но я как-то не встречал такого в профильной лит-ре (хотя, безусловно, я могу какие-то статьи и не знать). Есть различные вариации JPS (= алгоритмы, использующие и совершенствующие те или иные идеи JPS), это да. Но вот что-то "принципиально другое" - не знаю. Опять же - буду благодарен за ссылку на качественную статью про подобный(е) алгоритм(ы).
Я бы не сказал, что JPS основан именно на этой идее, хотя, сходство, безусловно есть. Всё-таки JPS про breaking symmetries (aka эксплуатацию canonical ordering) и rule-based подход к недобавлению многих "лишних" нод в OPEN. В общем случае JPS не идет "напрямую от старта до финиша". Он скорее "продолжает прошлый ход" при этом "прыгая" либо до границы карты либо до особой точки на углу препятсвтия. При этом если "продолжение хода" идёт по диагонали, то там ещё и бокове "веточки" проверяются. В общем - что-то похожее есть, но всё-таки это не то, о чем говорит @nin-jin.
PS: А вообще JPS - классная штука, да. Для бинарных гридов прям то, что нужно. Кажется недавно и версию для weighted grids запилили (вроде видел на одной из свежих конференций статью про это).
После AlphaGo могли бы уже давно и массово заменять эвристики на ИИ.
Никогда этого не будет. Потому что эвристики — это дешевый вариант получить что-то похожее на правду, не считая это сложное целиком.
ИИ — весьма тяжелые в вычислении.
Согласен с @wataru - для многих задач с комбинаторно-сложной структурой "дешевые эвристики" - это прям то, что нужно.
В каком-то смысле использование эвристик (т.е. common sense, здравого смысла) при решении задач через поиск - это тоже ИИ (раньше вообще половина ИИ было про эвристический поиск. Сейчас, конечно, не так).
AlfaGo - классная штука. Опять же, она про комбинации ML и "классических" алгоритмов (в данном случае в частве "классического" алгоритма выступает MCTS). Мы (как научная группа) как раз тоже ратуем за это направление - интеграция ML и необучаемых алгоритмов.
Основная проблема поиска пути - это ведь вовсе не однократный, пусть и "тяжеловесный" расчет пути. Действительно секунда-другая проблемы не сделает.
А вот проблема пересчета пути при получении новой информации (появлении и исчезновении препятствий, перемещении препятствий - вот что не хочется делать регулярно.
Тот же D* ведь создан как раз для этого.
Может стоило сосредоточиться на этой проблеме, а не выдумывать проблему "сотни-тысяч" расчетов одновременно?
На самом деле сложно сказать, какая "проблема поиска пути" - главная. С научной точки зрения (а я смотрю на эти проблемы именно как научный работник) они все "главные". Просто есть какие-то более интересные (субъектиивно), а какие-то - менее интересные.
Естественно, мы (как научная группа) занимаемся и многими другими проблемами. Например, меня очень мотивирует задача много-агентного планирования (ala централизованное координирование движений роботов на складах amazon). Её тоже можно считать "главной" по такой логике.
Что же касается практической применимости (а, похоже, в комментарии речь идёт скорее про это, но может я и не прав), то тут мне сложно сказать. В робототехнике "главное" - одно, в игровой индустрии - другое. Я не то, чтобы супер-тесно связан с этими мирами, чтобы авторитетно утверждать, что "нужнее на практике".
PS: Кстати, с автором одной из самых популярных вариаций D*, а именно D*Lite - Максимом Лихачевым - я знаком, и его как раз тематика интеграции поиска и ML тоже интересует, причем именно в контексте one-shot planning. У него была статья с подобным подходом на ICAPS 2023. Я её увидел и предложил ему вместе поработать над A*+ML, он согласился и сейчас мы, как говорится, "на ранней стадии совместного исследования". Может через годик и опубликуем статью на этот счёт. Это я к тому, что даже автору D*Lite эта тематика тоже кажется заслуживающей внимание.
Любопытно, а не эффективнее ли в дальней перспективе (когда надо постоянно перепрокладывать маршрут, как в играх) считать иерархически по сетке проходимость ячеек (приняв за ячейку либо комнату, либо просто какой-то кусок пространства, правда во втором случа надо будет как-то учесть открытые области), а потом использовать их для быстрой дальней прокладки уже как граф. При этом мы не получаем точный маршрут, он требует уточнения, зато число ходов сильно меньше. Ну и проходимость локальных ячеек можно считать параллельно. Опять таки при изменении окружения достаточно пересчитать только затрагиваемые ячейки.
Насколько мне известно, подобные подходы (ну или "близкие по идее", скажем там) существуют. Например, есть достаточно старый иерархичный подход - HPA* (гуглится по названию статьи Near Optimal Hierarchical Path-Finding). Там большой грид разбивается на "клетки" поменьше на этапе пре-процессинга и потом уже это разбиение используется при планировании.
Вообще тема с "давайте сначала потратим какое-то время на пре-процессинг карты (и займём при этом какое-то, может быть даже весьма существенное, количество Mb под хранение результатов этого пре-процессинга) - она очень популярна, насколько мне известно. Есть много различный идей и их реализаций насчет того, "что именно предпосчитывать", "где и как именно хранить результаты прерасчета", "как именно их использовать онлайн при поиске".
Внезапно вы изобрели маршрутную декомпозицию на базе полигональных ячеек.
Трансформером по A*, или как уменьшить число итераций самого известного алгоритма поиска пути