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

График и дерево
алгоритмы поиска
Списки
похожие темы

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

Алгоритмы эвристического поиска, часто основанные на А * использовать эвристические знания в форме приближений целевых расстояний, чтобы сфокусировать поиск и решать задачи поиска, потенциально намного быстрее, чем алгоритмы неинформированного поиска.[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 (текущие системы), два разных алгоритма инкрементного эвристического поиска.

Рекомендации

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

внешняя ссылка