В каком-то смысле использование эвристик (т.е. common sense, здравого смысла) при решении задач через поиск - это тоже ИИ (раньше вообще половина ИИ было про эвристический поиск. Сейчас, конечно, не так).
AlfaGo - классная штука. Опять же, она про комбинации ML и "классических" алгоритмов (в данном случае в частве "классического" алгоритма выступает MCTS). Мы (как научная группа) как раз тоже ратуем за это направление - интеграция ML и необучаемых алгоритмов.
По поводу добавочной стоимости. Мне идея автором Neural A* изначально не очень нравится, т.к. они оценивают (с помощью нейросети) именно что доп. стоимость вершин, НО на самом деле может быть такое, что стоимость попадания в вершину разная в зависисмости от того, а из какой смежной вершины мы в неё попадаем.
В своих экспериментах по планированию на картинках мы рассматриваем такой сценарий - пусть у нас на этапе обучения есть RGB картинка ландшафта (вид сверху) + DEM (digital elevation model) этого ландшафта (т.е. карта высот). И нам нужно построить путь для условного марсохода, которому нежелательно забираться в крутые горки и так далее. В этом случае важно собирать путь именно из ребер графа (переходом между пикселями картинки). Потому что если мы в какую-то вершину пришли с одной строны и без перепада высоты, то это ок, а если с другой стороны и там был перепад высоты, то "это другое".
В целом NeuralA* обуславливается на старт-финиш (насколько я помню) поэтому, по идее это обстоятельство как-то должно улавливаться сеткой. Тем не менее идея определять всё через стоимость вершин (а не стоимости переходов между вершинами) мне кажется не такой уж идеальной.
В общем, скажу так. Если у есть задача планирования по картинкам и на этапе обучения есть только примеры путей по этим картинкам, то тут, наверное, только схема NeuralA* и поможет (хоть она и не идеальная). Если же у нас на этапе обучения есть чуть больше информации (например, есть датасет RGB+DEM, который позволяет нам самим строить не только один путь при решении конкретной задачи но и "путевую колбасу"), то я бы всё-таки советовал TransPath (наш подход) применять.
Я когда-то занимался такими алгоритмами. Да чего уж там, моя канд. диссертация была посвящена именно подобному алгоритму. Мне тогда удалось доказать, что все будет хорошо работать в случае простейших выпуклых фигур ala прямоугольники. Но в общем случае (а нас интересует именно общий случай) - всё не так просто. Когда появляются всякие лабиринты и спирали, то можно и зациклиться.
PS: В непрерывном случае отмеченная стратегия имеет название BUG алгоритм (публикация Люмельского от 79-го чтоли года). Там всё сходится, путь гарантируется, но длине его получается ой-ой-ой.
Давайте я сначала кое-что уточню, а потом отвечу вопросом на вопрос.
Уточнение: в статье картинки задания выглядят «непрерывно», но это сделано доя удобства восприяьия. на входе у нас имеется карта закодированная в виде матрицы с 0 и 1. Там где 1 - клетка заблокирована. Более наглядное представление (с «дискретными клетками») показано на втором рисунке в статье (там где кружочками цветными старт и финиш отмечены).
Вопрос: как по такому дискретному входу (быстро) найти аналитические границы препятствий? В целом - я не до конца понял мысль. Если получится её развернуть и пояснить, будет интересно обсудить.
Сравнение поисковых алгоритмов с т.з. времени/памяти не так просто, как может показаться на первый взгляд (по моему мнению). Сильно зависит от реализации. Тот же «стандартный» A* можно реализовать многими разными способами, с использованием различных структур данных для хранения промежуточ.вычислений. Например, можно иметь дубликаты в open и ленивую схему их удаления, но при этом open будет priority queue (по f-значению). А можно сделать два контейнера под open (один для сортировки по f, другой для хранения по id элементов) и обойтись без дубликатов вообще. Можно вообще отказать от хранения род.указателей (и восстанавливать искомый путь в конце по рассчитанным g-значениям). И так далее. Это я к тому, что в целом сравнить «два поисковых алгоритма» по времени работы - непросто. Вернее даже так, сравнить можно, но как трактовать цифры и какие выводы делать из цифр - вопрос. Конечно, всё равно такие сравнения проводят, считая что тот, кто видит результаты - в состоянии сам их проинтерпретировать. В этом плане сравнение «по итерациям» более «устойчиво» и поэтому им часто пользуются.
По «параллельному А*». Я точно встречал статьи, где речь шла именно о распараллеливании поиска «по итерациям» (и там всё не так просто). По параллельной обработке разных заданий батчами на gpu - не встречал. Но это не значит, что их нет. Надо посмотреть. В целом - предложение по такому сравнению очень разумное, да!
Про доп.стоимость - отвечу чуть позже (сейчас в метро, выходить пора :) )
Согласен с @wataru - для многих задач с комбинаторно-сложной структурой "дешевые эвристики" - это прям то, что нужно.
В каком-то смысле использование эвристик (т.е. common sense, здравого смысла) при решении задач через поиск - это тоже ИИ (раньше вообще половина ИИ было про эвристический поиск. Сейчас, конечно, не так).
AlfaGo - классная штука. Опять же, она про комбинации ML и "классических" алгоритмов (в данном случае в частве "классического" алгоритма выступает MCTS). Мы (как научная группа) как раз тоже ратуем за это направление - интеграция ML и необучаемых алгоритмов.
По поводу добавочной стоимости. Мне идея автором Neural A* изначально не очень нравится, т.к. они оценивают (с помощью нейросети) именно что доп. стоимость вершин, НО на самом деле может быть такое, что стоимость попадания в вершину разная в зависисмости от того, а из какой смежной вершины мы в неё попадаем.
В своих экспериментах по планированию на картинках мы рассматриваем такой сценарий - пусть у нас на этапе обучения есть RGB картинка ландшафта (вид сверху) + DEM (digital elevation model) этого ландшафта (т.е. карта высот). И нам нужно построить путь для условного марсохода, которому нежелательно забираться в крутые горки и так далее. В этом случае важно собирать путь именно из ребер графа (переходом между пикселями картинки). Потому что если мы в какую-то вершину пришли с одной строны и без перепада высоты, то это ок, а если с другой стороны и там был перепад высоты, то "это другое".
В целом NeuralA* обуславливается на старт-финиш (насколько я помню) поэтому, по идее это обстоятельство как-то должно улавливаться сеткой. Тем не менее идея определять всё через стоимость вершин (а не стоимости переходов между вершинами) мне кажется не такой уж идеальной.
В общем, скажу так. Если у есть задача планирования по картинкам и на этапе обучения есть только примеры путей по этим картинкам, то тут, наверное, только схема NeuralA* и поможет (хоть она и не идеальная). Если же у нас на этапе обучения есть чуть больше информации (например, есть датасет RGB+DEM, который позволяет нам самим строить не только один путь при решении конкретной задачи но и "путевую колбасу"), то я бы всё-таки советовал TransPath (наш подход) применять.
Я когда-то занимался такими алгоритмами. Да чего уж там, моя канд. диссертация была посвящена именно подобному алгоритму. Мне тогда удалось доказать, что все будет хорошо работать в случае простейших выпуклых фигур ala прямоугольники. Но в общем случае (а нас интересует именно общий случай) - всё не так просто. Когда появляются всякие лабиринты и спирали, то можно и зациклиться.
PS: В непрерывном случае отмеченная стратегия имеет название BUG алгоритм (публикация Люмельского от 79-го чтоли года). Там всё сходится, путь гарантируется, но длине его получается ой-ой-ой.
Давайте я сначала кое-что уточню, а потом отвечу вопросом на вопрос.
Уточнение: в статье картинки задания выглядят «непрерывно», но это сделано доя удобства восприяьия. на входе у нас имеется карта закодированная в виде матрицы с 0 и 1. Там где 1 - клетка заблокирована. Более наглядное представление (с «дискретными клетками») показано на втором рисунке в статье (там где кружочками цветными старт и финиш отмечены).
Вопрос: как по такому дискретному входу (быстро) найти аналитические границы препятствий? В целом - я не до конца понял мысль. Если получится её развернуть и пояснить, будет интересно обсудить.
Сравнение поисковых алгоритмов с т.з. времени/памяти не так просто, как может показаться на первый взгляд (по моему мнению). Сильно зависит от реализации. Тот же «стандартный» A* можно реализовать многими разными способами, с использованием различных структур данных для хранения промежуточ.вычислений. Например, можно иметь дубликаты в open и ленивую схему их удаления, но при этом open будет priority queue (по f-значению). А можно сделать два контейнера под open (один для сортировки по f, другой для хранения по id элементов) и обойтись без дубликатов вообще. Можно вообще отказать от хранения род.указателей (и восстанавливать искомый путь в конце по рассчитанным g-значениям). И так далее. Это я к тому, что в целом сравнить «два поисковых алгоритма» по времени работы - непросто. Вернее даже так, сравнить можно, но как трактовать цифры и какие выводы делать из цифр - вопрос. Конечно, всё равно такие сравнения проводят, считая что тот, кто видит результаты - в состоянии сам их проинтерпретировать. В этом плане сравнение «по итерациям» более «устойчиво» и поэтому им часто пользуются.
По «параллельному А*». Я точно встречал статьи, где речь шла именно о распараллеливании поиска «по итерациям» (и там всё не так просто). По параллельной обработке разных заданий батчами на gpu - не встречал. Но это не значит, что их нет. Надо посмотреть. В целом - предложение по такому сравнению очень разумное, да!
Про доп.стоимость - отвечу чуть позже (сейчас в метро, выходить пора :) )