Алгоритмы инкрементального эвристического поиска объединяют как инкрементный, так и эвристический поиск для ускорения поиска последовательностей схожих поисковых задач, что важно в областях, которые не полностью известны или изменяются динамически. [1] Инкрементальный поиск изучается, по крайней мере, с конца 1960-х годов. Алгоритмы инкрементного поиска повторно используют информацию из предыдущих поисков, чтобы ускорить текущий поиск и решить проблемы поиска потенциально намного быстрее, чем их многократное решение с нуля. [2] Точно так же эвристический поиск также изучается, по крайней мере, с конца 1960-х годов.
Алгоритмы эвристического поиска, часто основанные на A * , используют эвристические знания в форме приближений целевых расстояний, чтобы сфокусировать поиск и решать проблемы поиска, потенциально намного быстрее, чем алгоритмы неинформированного поиска. [3] Результирующие проблемы поиска, иногда называемые проблемами динамического планирования пути, представляют собой задачи поиска по графу, в которых пути необходимо находить многократно, потому что топология графа, стоимость его ребер, начальная вершина или конечные вершины меняются со временем. [4]
К настоящему времени разработаны три основных класса алгоритмов инкрементного эвристического поиска:
- Первый класс перезапускает A * в точке, где его текущий поиск отличается от предыдущего (пример: Fringe Saving A * [5] ).
- Второй класс обновляет h-значения (эвристика, то есть приблизительное расстояние до цели) из предыдущего поиска во время текущего поиска, чтобы сделать их более информированными (пример: Generalized Adaptive A * [6] ).
- Третий класс обновляет g-значения (расстояние от начала) от предыдущего поиска во время текущего поиска, чтобы исправить их, когда это необходимо, что можно интерпретировать как преобразование дерева поиска A * из предыдущего поиска в дерево поиска A * для текущий поиск (примеры: пожизненное планирование A * , [7] D * , [8] D * Lite [9] ).
Все три класса алгоритмов инкрементного эвристического поиска отличаются от других алгоритмов перепланирования, таких как планирование по аналогии, тем, что качество их плана не ухудшается с количеством эпизодов перепланирования.
Приложения
Инкрементный эвристический поиск широко используется в робототехнике , где большее количество систем планирования пути основано либо на D * (обычно более ранние системы), либо на D * Lite (текущие системы), двух разных алгоритмах инкрементного эвристического поиска.
Рекомендации
- ^ С. Кениг, М. Лихачев, Ю. Лю и Д. Фурси. Инкрементальный эвристический поиск в искусственном интеллекте. Журнал «Искусственный интеллект», 25 (2), 99-112, 2004.
- ^ Н. Део и К. Панг. Алгоритмы кратчайшего пути: таксономия и аннотация. Сети 14, 275–323, 1984.
- ^ П. Харт, Н. Нильссон и Б. Рафаэль, Формальная основа для эвристического определения путей с минимальной стоимостью, IEEE Trans. Syst. Наука и кибернетика, SSC-4 (2), 100-107, 1968.
- ^ Н. Део и К. Панг. Алгоритмы кратчайшего пути: таксономия и аннотация. Сети 14, 275–323, 1984.
- ^ X. Сан и С. Кениг. Спасающий край алгоритм поиска A * - технико-экономическое обоснование. В материалах Международной совместной конференции по искусственному интеллекту (IJCAI), 2391-2397, 2007.
- ^ X. Сан, С. Кениг и В. Йео. Обобщенный адаптивный A *. В материалах Международной совместной конференции по автономным агентам и многоагентным системам (AAMAS), 469-476, 2008.
- ^ С. Кениг, М. Лихачев и Д. Фурси. Планирование на всю жизнь A *. Искусственный интеллект, 155, (1-2), 93-146, 2004.
- ^ 6. А. Стенц. Сфокусированный алгоритм D * для перепланирования в реальном времени. Труды Международной совместной конференции по искусственному интеллекту, 1652–1659, 1995.
- ^ С. Кениг и М. Лихачев. Быстрое перепланирование навигации в неизвестной местности. Труды по робототехнике, 21, (3), 354-363, 2005.