Комментарии 11
Интересно. Особенно можно ли применять такой подход не только для нахождения траекторий, но и вообще для нахождения различных оптимумов в децентрализованных сетях.
Я думаю можно, как минимум, пробовать. Сами мы этим (пока) не занимались, т.к. нам в силу опыта задача планирования траектории(й) ближе.
важно ещё насчет «оптимума» сказать. Наш подход, равно как и все другие известные нам, основанные на обучении, не дают строгих теоретических гарантий. Не то что оптимума, а просто нет гарантии того, что агенты дойдут до своих (целей), а не застрянут где-то по дороге в узком проходе.
То есть эмпирически (в многих-многих экспериментах) мы видим, что метод работает хорошо, но теоретических гарантий у нас нет. Есть куда работать :)
"... систему правил будет придумать непросто, скорее всего правил будет много... и так далее... у нас же XXI век на дворе, дип лёнинг, биг дата и все дела.." - как-то несерьёзно, что-ли: смысл таких исследований и статей в конечном итоге системно обосновать преимущество новых технологий над старыми типа продукций, Пролога и т.п. (они тоже могли бы применяться). А так пока итог такой: "попробовали что-то новое, что-то получили". Ну хорошо, поздравляю!
Спасибо за поздравление =)
В своем исследовании мы обосновали экспериментально преимущество предложенного нами метода над известными мировыми аналогами.
Над аналогами - ок. Но зачем вскользь упоминать про "неаналоги" - принципиально другие подходы (логическое программирование, о котором я писал в предыдущем комменте), сразу их отодвигая в сторону как неспособные, если они не изучались и не сравнивались...
Я не вижу в тексте ничего, что можно было бы трактовать как «логическое программирование - неспособное».
Если кто-то считает, что нужно использовать лог.программирование для решения описываемой задачи - ок. Больше методов для сравнения - выше шанс «докопаться до истины». Мы наше решение выложили в открытый доступ, с ним можно будет сравниться, сделать выводы.
Спасибо, очень интересная статья! Вы пишите
других эффективных и удобных сред, заточенных под MAPF задачи просто не существовало.
Почему не подошла библиотека https://github.com/Farama-Foundation/MAgent2 ?
Про MAgent мы знали, экспериментировали с этой средой, прежде сем принять решение делать свое (тогда кажется только первая версия MAgent была доступна). Нас не устроило то, что в ней нет собственно сценария MAPF, нет процедурной генерации карт, нет возможности подгружать свои собственные карты/распределения карт для обучения/эвала. Дописывать это всё нам показалось менее удобным, чем написать свою среду с нуля. В общем мы сделали выбор в пользу более специализированной среды, заточенной именно под MAPF.
Поиск пути, многоагентная система, эвристики... Кажется, что если сложить все ключевые слова воедино, то на выходе получим муравьиные алгоритмы. Но не увидел, может, невнимательно читал.
Не обязательно бросаться в крайности: централизованное или распределённое управление. Понятно, что в случае большого числа агентов централизованное управление утопично, но совсем отказываться от центра не стоит, он может оказать посильную помощь. В современных мегаполисах многие автомобилисты прибегают к услугам навигатора, который при выборе маршрута пользуется подсказками центра, например, о пробках. А если бы агенты передавали центру информацию о выбранных маршрутах, то тот мог бы не только сообщать об имеющихся пробках, но и прогнозировать намечающиеся.
Проблема захвата ресурсов. Пусть агентам 1 и 2 требуется один и тот же участок дороги А, причём агенту 1 этот участок нужен позарез, а агент 2 мог бы вместо участка А воспользоваться участком Б, ничего не потеряв или потеряв очень мало. Агент 2 и рад бы уступить, но он ничего не знает о потребностях агента 1. Центр мог бы объявить на участок А что-то вроде аукциона.
Здесь возможна и ситуация взаимного клинча. Увидев, что участок А занят, агент 1 выбирает гораздо более дорогой путь, проходящий через участок Б. Теперь агент 2, даже если захочет, не сможет уступить участок А, пока участок Б не будет освобождён. Сам собой такой клинч не распутается, нужен специальный механизм либо центрального арбитража, либо сепаратной договорённости агентов.
Наконец, существует проблема буриданова осла. Рассмотрим простенький граф: вершина 5 соединена с каждой из вершин {1, 2, 3, 4}. Агенту 1 надо попасть из вершины 1 в вершину 3, а агенту 2 – из вершины 2 в вершину 4. Как исключить возможность столкновения, если агенты действуют по одинаковому алгоритму?
Ясно, что один из агентов должен пропустить ход. Но какой? Здесь либо выбор может сделать центр, либо агенты могут сыграть в «камень-ножницы-бумага», либо сделать вывод, кто должен уступить дорогу, не вступая в переговоры, а просто посмотрев на номера друг друга или на приоритет рёбер. Агентов может быть и больше двух.
В более серьёзной версии этого конфликта два барана могут подойти к разным концам узкого моста, настолько длинного, что они не видят друг друга. Но центр-то видит.
Много-агентное планирование траекторий в децентрализованном режиме: эвристический поиск и обучение с подкреплением