의 휴리스틱 요소에 대한 가중치를 조정하는 실험을 수행하였다.
depth first search (되추적 탐색) 을 개선할 수 있는 다양한 방법들로 종속 관계에 의한 되추적 (dependency directed backtracking) [Richard Stallman & Gerald Sussman 1977. Forward Reasoning and Dependency Directed Backtracking in a ...], 되도약 (backjumping) [Gaschnig 1979], 동적 되추적 (dynamic backtracking) [Matthew Ginsberg 1993. Dynamic Backtracking] 등이 있다. 마지막 논문에서는 이러한 방법들을 비교하고 동적 되추적 방법의 장점을 설명하고 있다. 이러한 향상된 되추적 기법들은 일반적으로 제약조건 충족 (constraint satisfaction) 문제에 많이 적용된다.
heuristic search 는 두 종류의 계산을 수행한다. 첫째로, 실제로 노드를 확장하고 경로 자체를 생성하는 객체 레벨 (object level) 의 계산이 있다. 둘째로, 다음에 어느 노드를 확장할 것인지를 결정하는 메타 레벨 (meta level) 의 계산이 있다. 객체 레벨은 실세계에서의 물리적인 행동에 관한 것이고, 메타 레벨은 그래프에서의 계산에 관한 것이다. 객체 레벨과 메타 레벨의 구분은 AI 에서 자주 등장한다. 이들은 [Stuart Russell & Wefald 1991. Do the Right Thing] 에 철저하게 논의되어 있으며, 계획, 행동 그리고 학습에서는 설명할 단축된 (abbreviated) 탐색 방법에 있어서 특히 중요한 역할을 수행한다.
타일 맞추기 문제는 많은 AI 연구자들에 의해 휴리스틱 탐색 방법을 시험하기 위한 테스트베드 (testbed) 로 사용되어 왔다. [Doran & Michie 1966. Experiments with the Graph Traverse Program] 의 초기 논문이 8 퍼즐을 사용했고, 그 이후로 사람들이 그래프에서 경로를 찾는 과정에 평가 함수를 사용하기 시작했다.
1990 년에 Korf 는 "IDA* 로 15 퍼즐은 풀 수 있지만 그 이상의 퍼즐 (24 퍼즐 등) 은 현재의 컴퓨터로 처리할 수 없다" 고 하였다 [Korf 1990, Realtime Heuristic search]. 하지만 더 강력한 컴퓨터 (초당 백만 개의 노드를 생성할 수 있는 Sun Ultra Sparc 워크스테이션) 와 더 강력한 (자동적으로 찾아진) 휴리스틱을 사용하여 [Richard Korf & Taylor 1996. Optimal Solution to 24 puzzles] 는 무작위로 만들어낸 답이 있는 24 퍼즐 문제에 대한 최적해를 2 시간 15 분에서 1 개월 사이의 시간에 찾아낼 수 있었다. [Richard Korf 1997. Optimal Solution to Rubik's Cube Using Pattern Databases] 는 IDA* 를 3 × 3 × 3 루빅스 큐브 (Rubik's Cube) 퍼즐의 최적 해를 찾는 데도 적용하였다.
탐색 기법들을 시험하고
개선하기 위하여 퍼즐들이 유용하게 사용되어 왔지만, A* 와 기타 휴리스틱
탐색 방법들은 많은 실제 문제에도 성공적으로 적용되어 왔다. 휴리스틱 함수를
찾기 위한 완화된 모델에 대하여 더 자세한 내용은 [Mostow & Prieditis
1989, Prieditis 1993] 에 나와 있다. [Pohl 1973] 은 의 휴리스틱 요소에 대한 가중치를 조정하는 실험을 수행하였다.
휴리스틱 탐색에 대한 가장 고전적인 책은 [Judea Pearl 1984. Heuristics Intelligent Search Strategies...] 이다. [Laveen N. Kanal & Kumar 1988. Search in AI] 은 탐색에 관한 논문들을 모아놓은 책이다. 이 책의 첫 번째 논문은 AI 와 OR (operations research) 연구자들에 의해 각각 독립적으로 개발된 탐색 방법들을 하나로 통일시킬 것을 제안하고 있다.
planning
감지/계획/행동 주기 는 Agre 와 Chapman 이 말한 인터리브 계획 (interleaved planning) 의 한 예이다 [Philip Agre & Chapman 1990 What are plans for?]. 이들은 이들이 제안한 즉흥 행동 (improvisation) 고 인터리브 계획을 대비하여 설명하였다. [Agre & Chapman 1990, p.30] 에 다음과 같은 말이 나와 있다. 인터리브 계획과 즉흥 행동은 문제에 대한 이해의 측면에서 다르다. 인터리브 계획에서는 계획에 따라 진행되는 것이 정상적이고, 문제가 일어나는 것은 예외적인 현상이다. 즉흥 행동에서는 모든 일이 계획에 따라 진행되지 않는다고 가정한다. 따라서, 에이전트는 지속적으로 새로운 판단을 내려야만 한다.
그러나 인식 및 작동 시스템에서 문제가 발생하는 상황이 예외적인 것이 되도록 (주어진 임무와 환경을 고려하여) 설계하는 것은 당연히 설계자의 임무가 아닌가? T-R 트리 [Nils J.Nilsson 1994] 와 같은 형태에서의 계획은 예외적인 문제에 대해 상당히 강건하다. 인터리브 계획과 실행에 대한 더 자세한 내용은 [Stentz 1995, Stentz & Hebert 1995, Nourbakhsh 1977] 에 나와 있다.
섬을 통한 탐색에 관해서는 [Chakrabarti, Ghose, & DeSarkar 1986] 을, 계층적 계획에 대한 모델과 분석에 대해서는 [Richard Korf 1987, Bacchus & Yang 1992] 를 참조하라. [Stefik 1995, pp.259-280] 에는 계층적 계획에 대한 명쾌한 설명이 나와 있다.
시계 제한 탐색에서는 시계를 지정해야 한다. 이러한 결정을 하기 위해서는 추가적인 계산의 가치와 이미 수행된 계산에 의해 추천되는 행동의 가치 사이의 절충을 고려해야 한다. 이 절충은 행동 지연의 비용에 의해 영향을 받는다. 추가적인 계산과 즉각적인 행동의 상대적인 가치를 평가하는 것은 메타 레벨 계산의 한 예이다. 이 주제에 관해서는 [Russell & Wefald 1991, 5장] 에서 자세히 다루고 있다. 이들의 DTA* 알고리즘은 이런 주제에 대한 아이디어를 구현한 것이다.
[Lee & Mahajan 1988] 은 평가 함수의 학습 방법을 기술하고 있다. 지연된 보상 (delayed reinforcement) 과 시간 차이 (temporal difference) 학습 방법은 확률적인 동적 프로그래밍 (stochastic dynamic programming) 과 밀접한 관련이 있다. 여기에 대해서는 [Barto, Gradtke, & Singh 1995, Ross 1988] 을 참고하라. 보상을 기반으로 하여 행동 정책을 학습하는 로봇 시스템의 예들은 [Mahadevan & Connell 1992] 와 [Connell & Mahadevan 1993b] 에 나와 있다. [Moore & Atkeson 1993] 에는 실제적인 시스템을 제어하기 위한 효율적인 기억기반 (memory-based) 보상 방법이 제시되어 있다. [Montague, et al. 1995] 는 강화 학습을 기반으로 꿀벌이 꿀을 찾아다니는 행동에 대한 모델을 제시하였고, [Schultz, Dayan, & Montague 1997] 은 시간 차이 학습 방식이 영장류의 신경계에 어떻게 구현되어 있는지를 설명하고 있다.
게임
퍼즐처럼 게임들도 AI 기법들을 다듬고 시험하는 데 매우 중요한 역할을 해왔다. 예를 들어 [Russell & Wefald 1991, 4 장] 는 알파 베타보다 효과적인 방법으로 탐색트리를 줄이기 위해 (계속되는 탐색의 기대값을 이용하여) 메타 레벨 계산을 수행하는 게임트리 알고리즘 (MGSS* 와 MGSS2) 을 제안하였다. Berliner 의 B* 알고리즘도 구간 한계 (interval bound) [Berliner 1979] 를 사용하여 보다 효과적인 절단을 한다. [Korf 1991] 은 알파 베타 방법을 여러 명이 하는 게임에 적용하도록 확장하였다.
수치 평가 함수를 사용하는 대신에, 게임에 대한 일부 연구에서는 하나의 상황이 다른 상황에 비해 더 좋은지 (better than) 혹은 더 나쁜지 (worse than) 를 판단하는 데 패턴인식 (pattern recognition) 기법을 사용하였다. 이러한 기법은 체스의 게임 마지막 부분을 수행하는 프로그램에 사용되었다 [Huberman 1968, Bratko & Michie 1980].
게임에 대한 가장 성공적인 초기 업적은 체커 (Checker) 게임에서의 기계 학습 (machine learning) 방법을 개발한 Arthur Samuel 의 연구이다 [Samuel 1967 Some Studies in Machine Learning Using the Game of Checkers]. Samuel 의 체커 프로그램은 챔피언에 가까운 수준으로 게임을 수행하였다. 현재는 University of Alberta 에 있는 Jonathan Schaeffer 의 CHINOOK 프로그램 [Schaeffer et al.1992 A World Championship Caliber Checkers Program, Schaeffer 1997] 이 세계 체커 챔피언으로 알려져 있다. 1997년에는 IBM 의 프로그램인 DEEP BLUE 가 챔피언 타이틀전에서 세계 체스 챔피언인 Garry Kasparov 를 이겼다.
[Monty Newborn 1996 Computer Chess Comes of Age] 은 컴퓨터 체스에 관한 책으로서, 1996년에 DEEP BLUE 가 Garry Kasparov 에게 패할 때까지의 역사를 열거한 것이다. 이 책에 대한 서평과 AI 를 위한 연구용으로서의 체스의 역할에 대한 설명은 [John McCarthy 1997 AI as Sport] 을 참조하라. McCarthy 는 체스 프로그램이 좀더 인간과 비슷한 추론 방법을 사용한다면 더 적은 탐색으로도 더 나은 성능을 보일 것이라고 하였다. [Donald Michie 1966 Game Playing and Game Learning Automata] 는 기대값 최대화 (expectimax) 라는 말을 만들고 이 기법에 대한 실험을 수행하였다.
[Lee & Mahajan 1988] 은 강화 학습 (reinforcement learning) 방법을 오셀로 (Othello) 게임에 적용하였으며, [Schraudolph, Dayan, & Sejnowski 1994] 는 시간차이 (temporal difference) 기법을 바둑에 적용하였다. 일반적인 게임 탐색 방법에 대해 더 알고 싶다면 [Judea Pearl 1984, Heuristics Intelligent Search Strategies... 9 장] 을 참조하라.