점진적 경험적 경험적 발견

Incremental heuristic search
그래프 및 트리
검색 알고리즘
최단 경로
목록
관련 항목

증분적 경험적 경험적 발견 알고리즘은 증분적 검색과 경험적 경험적 검색을 모두 결합하여 유사 검색 문제의 시퀀스 검색 속도를 높인다. 이는 불완전하게 알려지거나 동적으로 변화하는 도메인에서 중요하다.[1]증분 탐색은 적어도 1960년대 후반부터 연구되어 왔다.증분 검색 알고리즘은 이전 검색의 정보를 재사용하여 현재 검색 속도를 높이고 검색 문제를 처음부터 반복적으로 해결하는 것보다 잠재적으로 훨씬 빠르게 해결한다.[2]마찬가지로 휴리스틱스 탐색도 적어도 1960년대 후반부터 연구되어 왔다.

경험적 발견 알고리즘은 종종 A*를 기반으로 하는 경험적 발견 알고리즘을 목표 거리 근사치의 형태로 경험적 발견 지식을 사용하여 미지식 검색 알고리즘보다 검색에 초점을 맞추고 잠재적으로 훨씬 빠르게 검색 문제를 해결한다.[3]동적 경로 계획 문제라고도 하는 결과적인 검색 문제는 그래프의 위상, 가장자리 비용, 시작 정점 또는 목표 정점이 시간에 따라 변하기 때문에 경로를 반복적으로 찾아야 하는 그래프 검색 문제들이다.[4]

지금까지 세 가지 주요 등급의 점진적 휴리스틱 검색 알고리즘이 개발되었다.

  • 첫 번째 클래스는 현재 검색이 이전 검색에서 벗어나는 지점에서 A*를 재시작한다(예:프린지 세이빙 A*).[5]
  • 두 번째 클래스는 현재 검색 중 이전 검색에서 h-값(예: 일반화 적응형 A*)[6]을 업데이트하여 정보를 더 많이 제공하도록 한다.
  • 세 번째 클래스는 현재 검색 중 이전 검색에서 g 값(시작부터 거리)을 업데이트하여 필요할 때 수정하며, 이는 이전 검색에서 현재 검색(예: 평생 계획 A*,[7] D*,[8] D*, D* Lite[9])을 A* 검색 트리로 변환하는 것으로 해석할 수 있다.

세 등급의 증분 휴리스틱 검색 알고리즘은 모두 재생 에피소드 수에 따라 계획 품질이 저하되지 않는다는 점에서 유추에 의한 계획 등 다른 재생 알고리즘과 다르다.

적용들

점증적 휴리스틱 검색은 로봇공학에서 광범위하게 사용되어 왔으며, 여기서 더 많은 수의 경로 계획 시스템이 D*(일반적으로 이전 시스템) 또는 D* Lite(현재 시스템) 중 하나에 기초하고 있으며, 두 개의 다른 점증적 휴리스틱 검색 알고리즘이다.

참조

  1. ^ S. Koenig, M. Likhachev, Y. 류, D.퍼시. 인공지능의 점진적 휴리스틱 검색.인공지능 매거진, 25(2), 99-112, 2004.
  2. ^ N. Deo와 C.Pang. 최단 경로 알고리즘:분류법 및 주석.네트워크 14, 275–323, 1984.
  3. ^ P. 하트, N. 닐슨, B.Raphael, 최소 비용 경로의 경험적 발견을 위한 공식적 기반, IEEE 트랜스.Sys. Science and Cybernetics, SSC-4(2), 100-107, 1968.
  4. ^ N. Deo와 C.Pang. 최단 경로 알고리즘:분류법 및 주석.네트워크 14, 275–323, 1984.
  5. ^ X. Sun과 S. Koenig.프린지 절약형 A* 검색 알고리즘 - 타당성 조사.IJCAI(International Joint Conference of Infrastructure Intelligence, IJCAI)에서 2007년 2391-2397.
  6. ^ X. Sun, S. Koenig, W.그래, 일반화된 적응형 A*.국제자율대리인 및 멀티에이전트 시스템에 관한 국제공동회의(AAMAS)에서 2008년 469-476.
  7. ^ S. Koenig, M. Likhachev, D.퍼시, 평생 계획 A*.인공지능, 155, (1-2), 93-146, 2004.
  8. ^ 6. A. 스텐츠실시간 재생을 위한 포커스 D* 알고리즘.인공지능에 관한 국제 공동 회의의 진행, 1652–1659, 1995.
  9. ^ S. Koenig와 M.리하체프.알 수 없는 지형에서 항법 수술을 위한 빠른 재배치.로보틱스, 21, (3) 354-363, 2005.

외부 링크