Инкрементальный эвристический поиск

Истоки инкрементального эвристического поиска лежат в исследованиях, которые велись с конца 1960-х годов и были направлены на объединение двух подходов: инкрементального поиска, повторно использующего информацию из предыдущих вычислений, и эвристического, который применяет оценочные функции для сужения области поиска. Это сочетание оказалось особенно эффективным для решения задач динамического планирования пути, где маршрут необходимо многократно пересчитывать из-за изменений в среде.

Прорыв в этой области произошёл в 1994 году, когда Энтони Стенц (англ. Anthony Stentz) представил алгоритм D* (англ. Dynamic A*), разработанный для планирования пути мобильных роботов в неполностью известных или неточных средах^[2]. В отличие от многократного запуска A*, D* не пересчитывал весь путь заново при обнаружении препятствия, а эффективно корректировал существующий план, распространяя информацию об изменении стоимости только на затронутые участки графа. Несмотря на свою эффективность, оригинальный D* приобрёл репутацию сложного для понимания и реализации алгоритма^[3].

Следующий этап эволюции связан с работами Свена Кёнига (англ. Sven Koenig) и Максима Лихачёва (англ. Maxim Likhachev). В 2001 году они представили Lifelong Planning A* (LPA*) — инкрементальную версию A*, которая при последующих запусках в изменённом графе значительно сокращала объём вычислений за счёт использования информации из предыдущих поисков. На основе LPA* в 2002 году они создали алгоритм D* Lite^[4].

D* Lite реализует то же поведение, что и D*, но основан на более простой и понятной структуре LPA*^[3]. Алгоритм выполняет поиск в обратном направлении (от цели к старту) и при обнаружении роботом изменений в карте инкрементально корректирует путь. D* Lite оказался не только проще в реализации, но и как минимум таким же быстрым, а зачастую и более производительным, чем его предшественник^[3]. Благодаря этим преимуществам он практически полностью вытеснил оригинальный D* в современных приложениях. Алгоритмы семейства D* нашли применение, в частности, в навигационных системах прототипов марсоходов «Спирит» и «Оппортьюнити», а также в автомобиле-победителе конкурса DARPA Urban Challenge.

В 2003 году Максим Лихачёв, Джефф Гордон и Себастьян Трун разработали алгоритм Anytime Repairing A* (ARA*), который быстро находит субоптимальное решение с помощью взвешенного алгоритма A* и инкрементально улучшает его до оптимального за счёт переиспользования результатов предыдущих поисков при постепенном уменьшении границы ошибки.

Алгоритмы инкрементального эвристического поиска можно разделить на три основных класса в зависимости от способа использования информации, полученной в ходе предыдущих вычислений.

1. Обновление g-значений (стоимости пути от старта). Наиболее распространённый подход, при котором алгоритмы корректируют g-значения, унаследованные от предыдущего поиска, чтобы «исправить» старое дерево поиска в соответствии с новыми условиями. Это можно представить как преобразование дерева поиска из предыдущей задачи в дерево для текущей^[5]. К этому классу относятся такие известные алгоритмы, как LPA*, D* и D* Lite^[5].
2. Обновление h-значений (эвристических оценок). Алгоритмы этого класса используют результаты предыдущего поиска для уточнения эвристической функции в текущем поиске, делая её более «информированной» и позволяя эффективнее направлять поиск к цели^[5]. Представителем этого класса является Generalized Adaptive A*.
3. Перезапуск поиска с точки расхождения. Алгоритмы этого типа сохраняют часть информации из предыдущего поиска и перезапускают стандартный эвристический поиск (например, A*) с того места, где новое состояние задачи начинает отличаться от старого. Примером такого алгоритма является Fringe Saving A*.

Инкрементальный эвристический поиск широко применяется в робототехнике, где множество систем планирования путей основаны либо на алгоритме D*, либо на D* Lite — двух различных инкрементальных эвристических алгоритмах поиска (D* чаще применялся в ранних системах, D* Lite — в современных). Практическое применение эти алгоритмы нашли в навигационных системах марсоходов НАСА «Спирит» и «Оппортьюнити», а также в системе управления автомобилем, победившим в соревновании DARPA Urban Challenge.

Современные разработки направлены на повышение эффективности, построение более плавных траекторий и адаптацию к сложным динамическим средам. Появились алгоритмы, работающие в непрерывном пространстве, такие как Field D* (разработанный Дэйвом Фергюсоном и Энтони Стенцем), который использует линейную интерполяцию для оценки стоимости пути внутри ячеек сетки, что позволяет строить гладкие маршруты с непрерывным диапазоном направлений^[6][7]. Его трёхмерная версия (3D Field D*) используется для планирования маршрутов летающих и подводных дронов^[7]. Другое направление — anytime-алгоритмы (алгоритмы с гибким временем выполнения), например Anytime Dynamic A* (AD*). Они быстро находят первоначальное, пусть и неоптимальное, решение и асинхронно улучшают его, что позволяет роботу начать движение раньше, не дожидаясь завершения всех вычислений.

Актуальной тенденцией является гибридизация подходов, когда глобальный планировщик (например, улучшенный D* Lite) работает в паре с локальным (например, Dynamic Window Approach), что позволяет эффективно сочетать стратегическое планирование с быстрым обходом внезапных препятствий. Также усложняются функции стоимости: вместо простого расстояния они теперь могут учитывать безопасность, плавность поворотов и кинематические ограничения транспортного средства. Для решения задач в многомерных пространствах используются алгоритмы с несколькими эвристиками (Multi-Heuristic A*)^[8], а также исследуется применение нейронных сетей для автоматического формирования эвристических функций^[8]. В 2023 году был предложен гибридный алгоритм, объединяющий D* Lite и алгоритм Беллмана — Форда, который позволяет сократить время вычислений примерно на 25 % по сравнению со стандартным D* Lite^[9].