Я не вижу в тексте ничего, что можно было бы трактовать как «логическое программирование - неспособное».
Если кто-то считает, что нужно использовать лог.программирование для решения описываемой задачи - ок. Больше методов для сравнения - выше шанс «докопаться до истины». Мы наше решение выложили в открытый доступ, с ним можно будет сравниться, сделать выводы.
Про MAgent мы знали, экспериментировали с этой средой, прежде сем принять решение делать свое (тогда кажется только первая версия MAgent была доступна). Нас не устроило то, что в ней нет собственно сценария MAPF, нет процедурной генерации карт, нет возможности подгружать свои собственные карты/распределения карт для обучения/эвала. Дописывать это всё нам показалось менее удобным, чем написать свою среду с нуля. В общем мы сделали выбор в пользу более специализированной среды, заточенной именно под MAPF.
Я думаю можно, как минимум, пробовать. Сами мы этим (пока) не занимались, т.к. нам в силу опыта задача планирования траектории(й) ближе.
важно ещё насчет «оптимума» сказать. Наш подход, равно как и все другие известные нам, основанные на обучении, не дают строгих теоретических гарантий. Не то что оптимума, а просто нет гарантии того, что агенты дойдут до своих (целей), а не застрянут где-то по дороге в узком проходе.
То есть эмпирически (в многих-многих экспериментах) мы видим, что метод работает хорошо, но теоретических гарантий у нас нет. Есть куда работать :)
Насчет звездочек в названии алгоритмов. Кажется, что это такой знак, сигнализирующий о том, что алгоритм «на максималках», т.е. обладает каким-то важным свойством. Например, упомянутый в статье алгоритм RRT*, это модификация алгоритма RRT. При этом RRT* гарантирует (в вероятностном смысле, тк алгоритм основан на случайном выборе) отыскание оптимального решения, а RRT - нет.
Возможно, эта звездочка перекочевала из командной строки, где она изначально использовалась как wildcard для обозначения всего и сразу (delete *.*)
Очень интересная статья, спасибо. Было бы здорово услышать (возможно - через какое-то время) о реальных случаях использования. Сейчас, если честно, не до конца понятно (для человека со стороны) - для чего это нужно :) например, режим «реального времени» - он для чего?
А я бы, наоборот, не отказался от ссылки на курсы, чтобы для себя понять - а сколько это всё может стоить. Ведь видно, что в создание этой образовательной программы вложено немало сил, времени, энтузиазма и пр.
И второй вопрос - насколько ваша программа обучения масштабируема? Условно, вы готовы отдать сторонним людям методички, материалы и прочее? Если нет, то в чём тогда смысл? Просто какой-то локальный личный доход иметь от того, что нравится делать? Если готовы «отдать», то не окажется ли, что курс слишком «авторский» и другие его не смогут эффективно преподавать?
Jump point search - алгоритм поиска путей на сетчатых графах (который скипает много промежуточных вычислений по сравнению с A* и за счет этого на многих картах (но не на всех) оказывается ощутимо быстрее).
Вопрос - проводили ли вы испытания вашего ml-планировщика в реальных условиях (т.е. на машине, не в симуляторе)? Какие были результаты (в сравнении с классикой)?
В общем я делаю такое предположение, основываясь на нашем диалоге. У вас есть идея некоторого алгоритма, который умеет планированить пути на гриде. При этом самого алгоритма и доказательств его теор.свойств нет.
Что тут можно сказать. Сама по себе идея - кажется очень разумной да. Повторюсь, я сам имел опыт разработки методов на основе этой идеи какое-то время назад (>10 лет). И в некоторых случаях это работало а) очень хорошо б) имело доказанные теор.свойства.
НО в общем случае, когда у нас могут быть, например, вогнутые препятсвия, которые "проникают друг в друга", всякие спирали и "спирали в спирали", у меня не получилось доказать корректность моего алгоритма и/или придумать алгоритм, который был бы корректен (хотя я пытался). Если у вас такое получилось, то это здорово, давайте описание/код - будем смотреть/проверять. Если не у вас, а у кого-то другого есть такой алгоритм - тоже пойдёт, кидайте ссылку.
Дальнейшие рассуждения "на уровне идеи" вряд ли что-то дадут. Да, идея хорошая. Но идея без реализации это не совсем то, что нужно для решения задач.
Ну насколько я понимаю вы предлагаете примерно тоже самое делать, а именно - "идти напрямую пока не упрешься в препятсвие, а потом обходить препятсвие до какого-то момент", но только "в голове", т.е. на этапе планирования пути, а не на этапе исполнения пути, как в BUG. Поэтому и указал на эту аналогию.
Насколько мне известно, подобные подходы (ну или "близкие по идее", скажем там) существуют. Например, есть достаточно старый иерархичный подход - HPA* (гуглится по названию статьи Near Optimal Hierarchical Path-Finding). Там большой грид разбивается на "клетки" поменьше на этапе пре-процессинга и потом уже это разбиение используется при планировании.
Вообще тема с "давайте сначала потратим какое-то время на пре-процессинг карты (и займём при этом какое-то, может быть даже весьма существенное, количество Mb под хранение результатов этого пре-процессинга) - она очень популярна, насколько мне известно. Есть много различный идей и их реализаций насчет того, "что именно предпосчитывать", "где и как именно хранить результаты прерасчета", "как именно их использовать онлайн при поиске".
Хороший контр-пример, на котором 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 запилили (вроде видел на одной из свежих конференций статью про это).
Мне так не показалось, когда я этим занимался. Конечно, в случае препятствий простых форм - всё просто. Я даже доказывал (и уверен, что правильно доказал) корректность и др. теор.свойства подобного алгоритма, когда писал кандидатскую в 2010. Но в общем случае, мне доказать не удалось.
Если вы знаете научную статью статью, описывающую подобный алгоритм, содержащую формальное доказательство теор.свойств (корректность завершения (в т.ч. на нерешаемом input), оптимальность отыскиваемых решений, алг.сложность и пр.), то мне было бы небезынтересно на неё взглянуть. Поделитесь?
На самом деле сложно сказать, какая "проблема поиска пути" - главная. С научной точки зрения (а я смотрю на эти проблемы именно как научный работник) они все "главные". Просто есть какие-то более интересные (субъектиивно), а какие-то - менее интересные.
Естественно, мы (как научная группа) занимаемся и многими другими проблемами. Например, меня очень мотивирует задача много-агентного планирования (ala централизованное координирование движений роботов на складах amazon). Её тоже можно считать "главной" по такой логике.
Что же касается практической применимости (а, похоже, в комментарии речь идёт скорее про это, но может я и не прав), то тут мне сложно сказать. В робототехнике "главное" - одно, в игровой индустрии - другое. Я не то, чтобы супер-тесно связан с этими мирами, чтобы авторитетно утверждать, что "нужнее на практике".
PS: Кстати, с автором одной из самых популярных вариаций D*, а именно D*Lite - Максимом Лихачевым - я знаком, и его как раз тематика интеграции поиска и ML тоже интересует, причем именно в контексте one-shot planning. У него была статья с подобным подходом на ICAPS 2023. Я её увидел и предложил ему вместе поработать над A*+ML, он согласился и сейчас мы, как говорится, "на ранней стадии совместного исследования". Может через годик и опубликуем статью на этот счёт. Это я к тому, что даже автору D*Lite эта тематика тоже кажется заслуживающей внимание.
Я не вижу в тексте ничего, что можно было бы трактовать как «логическое программирование - неспособное».
Если кто-то считает, что нужно использовать лог.программирование для решения описываемой задачи - ок. Больше методов для сравнения - выше шанс «докопаться до истины». Мы наше решение выложили в открытый доступ, с ним можно будет сравниться, сделать выводы.
Муравьиных алгоритмов у нас не было.
Про MAgent мы знали, экспериментировали с этой средой, прежде сем принять решение делать свое (тогда кажется только первая версия MAgent была доступна). Нас не устроило то, что в ней нет собственно сценария MAPF, нет процедурной генерации карт, нет возможности подгружать свои собственные карты/распределения карт для обучения/эвала. Дописывать это всё нам показалось менее удобным, чем написать свою среду с нуля. В общем мы сделали выбор в пользу более специализированной среды, заточенной именно под MAPF.
Спасибо за поздравление =)
В своем исследовании мы обосновали экспериментально преимущество предложенного нами метода над известными мировыми аналогами.
Я думаю можно, как минимум, пробовать. Сами мы этим (пока) не занимались, т.к. нам в силу опыта задача планирования траектории(й) ближе.
важно ещё насчет «оптимума» сказать. Наш подход, равно как и все другие известные нам, основанные на обучении, не дают строгих теоретических гарантий. Не то что оптимума, а просто нет гарантии того, что агенты дойдут до своих (целей), а не застрянут где-то по дороге в узком проходе.
То есть эмпирически (в многих-многих экспериментах) мы видим, что метод работает хорошо, но теоретических гарантий у нас нет. Есть куда работать :)
Насчет звездочек в названии алгоритмов. Кажется, что это такой знак, сигнализирующий о том, что алгоритм «на максималках», т.е. обладает каким-то важным свойством. Например, упомянутый в статье алгоритм RRT*, это модификация алгоритма RRT. При этом RRT* гарантирует (в вероятностном смысле, тк алгоритм основан на случайном выборе) отыскание оптимального решения, а RRT - нет.
Возможно, эта звездочка перекочевала из командной строки, где она изначально использовалась как wildcard для обозначения всего и сразу (delete *.*)
Очень интересная статья, спасибо. Было бы здорово услышать (возможно - через какое-то время) о реальных случаях использования. Сейчас, если честно, не до конца понятно (для человека со стороны) - для чего это нужно :) например, режим «реального времени» - он для чего?
Хорошо. Если на реке не работает, то что насчет моря/океана? Например, в Финском заливе пробовали?
А я бы, наоборот, не отказался от ссылки на курсы, чтобы для себя понять - а сколько это всё может стоить. Ведь видно, что в создание этой образовательной программы вложено немало сил, времени, энтузиазма и пр.
И второй вопрос - насколько ваша программа обучения масштабируема? Условно, вы готовы отдать сторонним людям методички, материалы и прочее? Если нет, то в чём тогда смысл? Просто какой-то локальный личный доход иметь от того, что нравится делать? Если готовы «отдать», то не окажется ли, что курс слишком «авторский» и другие его не смогут эффективно преподавать?
Jump point search - алгоритм поиска путей на сетчатых графах (который скипает много промежуточных вычислений по сравнению с A* и за счет этого на многих картах (но не на всех) оказывается ощутимо быстрее).
А JPS не пробовали запилить/включить в бенчмаркинг? Интересно было бы посмотреть на результаты.
Спасибо, интресно!
Вопрос - проводили ли вы испытания вашего ml-планировщика в реальных условиях (т.е. на машине, не в симуляторе)? Какие были результаты (в сравнении с классикой)?
В общем я делаю такое предположение, основываясь на нашем диалоге. У вас есть идея некоторого алгоритма, который умеет планированить пути на гриде. При этом самого алгоритма и доказательств его теор.свойств нет.
Что тут можно сказать. Сама по себе идея - кажется очень разумной да. Повторюсь, я сам имел опыт разработки методов на основе этой идеи какое-то время назад (>10 лет). И в некоторых случаях это работало а) очень хорошо б) имело доказанные теор.свойства.
НО в общем случае, когда у нас могут быть, например, вогнутые препятсвия, которые "проникают друг в друга", всякие спирали и "спирали в спирали", у меня не получилось доказать корректность моего алгоритма и/или придумать алгоритм, который был бы корректен (хотя я пытался). Если у вас такое получилось, то это здорово, давайте описание/код - будем смотреть/проверять. Если не у вас, а у кого-то другого есть такой алгоритм - тоже пойдёт, кидайте ссылку.
Дальнейшие рассуждения "на уровне идеи" вряд ли что-то дадут. Да, идея хорошая. Но идея без реализации это не совсем то, что нужно для решения задач.
Ну насколько я понимаю вы предлагаете примерно тоже самое делать, а именно - "идти напрямую пока не упрешься в препятсвие, а потом обходить препятсвие до какого-то момент", но только "в голове", т.е. на этапе планирования пути, а не на этапе исполнения пути, как в BUG. Поэтому и указал на эту аналогию.
Насколько мне известно, подобные подходы (ну или "близкие по идее", скажем там) существуют. Например, есть достаточно старый иерархичный подход - HPA* (гуглится по названию статьи Near Optimal Hierarchical Path-Finding). Там большой грид разбивается на "клетки" поменьше на этапе пре-процессинга и потом уже это разбиение используется при планировании.
Вообще тема с "давайте сначала потратим какое-то время на пре-процессинг карты (и займём при этом какое-то, может быть даже весьма существенное, количество Mb под хранение результатов этого пре-процессинга) - она очень популярна, насколько мне известно. Есть много различный идей и их реализаций насчет того, "что именно предпосчитывать", "где и как именно хранить результаты прерасчета", "как именно их использовать онлайн при поиске".
Спасибо!
Хороший контр-пример, на котором 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 запилили (вроде видел на одной из свежих конференций статью про это).
Мне так не показалось, когда я этим занимался. Конечно, в случае препятствий простых форм - всё просто. Я даже доказывал (и уверен, что правильно доказал) корректность и др. теор.свойства подобного алгоритма, когда писал кандидатскую в 2010. Но в общем случае, мне доказать не удалось.
Если вы знаете научную статью статью, описывающую подобный алгоритм, содержащую формальное доказательство теор.свойств (корректность завершения (в т.ч. на нерешаемом input), оптимальность отыскиваемых решений, алг.сложность и пр.), то мне было бы небезынтересно на неё взглянуть. Поделитесь?
На самом деле сложно сказать, какая "проблема поиска пути" - главная. С научной точки зрения (а я смотрю на эти проблемы именно как научный работник) они все "главные". Просто есть какие-то более интересные (субъектиивно), а какие-то - менее интересные.
Естественно, мы (как научная группа) занимаемся и многими другими проблемами. Например, меня очень мотивирует задача много-агентного планирования (ala централизованное координирование движений роботов на складах amazon). Её тоже можно считать "главной" по такой логике.
Что же касается практической применимости (а, похоже, в комментарии речь идёт скорее про это, но может я и не прав), то тут мне сложно сказать. В робототехнике "главное" - одно, в игровой индустрии - другое. Я не то, чтобы супер-тесно связан с этими мирами, чтобы авторитетно утверждать, что "нужнее на практике".
PS: Кстати, с автором одной из самых популярных вариаций D*, а именно D*Lite - Максимом Лихачевым - я знаком, и его как раз тематика интеграции поиска и ML тоже интересует, причем именно в контексте one-shot planning. У него была статья с подобным подходом на ICAPS 2023. Я её увидел и предложил ему вместе поработать над A*+ML, он согласился и сейчас мы, как говорится, "на ранней стадии совместного исследования". Может через годик и опубликуем статью на этот счёт. Это я к тому, что даже автору D*Lite эта тематика тоже кажется заслуживающей внимание.