그래프플랜
Graphplan그래프플랜(Graphplan)은 1995년 에이브림 블럼과 메릭 퍼스트가 개발한 자동화 계획 알고리즘이다.Graphplan은 STIP로 표현된 계획 문제를 입력으로 받아들이고, 가능한 경우 목표 상태에 도달하기 위한 일련의 작업을 생성한다.
그래프플랜이라는 이름은 국가 공간 그래프의 직설적인 탐색에서 해결책을 찾는 데 필요한 검색량을 줄이기 위해 새로운 계획 그래프를 사용했기 때문이다.
상태 공간 그래프에서:
- 노드는 가능한 상태,
- 가장자리는 특정 동작을 통해 도달할 수 있음을 나타낸다.
반대로, 그래프플랜의 계획 그래프에서:
- 노드는 행동과 원자적인 사실이며, 다른 수준으로 배열되어 있다.
- 가장자리는 다음 두 가지 유형이다.
- 원자적인 사실로부터 그것이 조건인 행동까지,
- 어떤 행동에서 원자 사실에 이르기까지 그것은 진실과 거짓을 만든다.
첫 번째 수준은 초기 상태를 식별하는 진정한 원자 사실을 포함한다.
동시에 진실일 수 없는 양립할 수 없는 사실과 함께 실행할 수 없는 양립할 수 없는 행동의 목록도 유지된다.
그런 다음 알고리즘은 계획 그래프를 반복적으로 확장하여, 역방향 체인에 의한 길이 l의 계획을 찾기 전에 길이 l-1의 해결책이 없음을 증명한다: 목표가 사실이라고 가정할 때, 그래프플랜은 목표에 도달할 수 있는 조치와 이전 상태를 찾고, 비호환성 i로 인해 가능한 많은 목표를 제거한다.양식의
계획과 밀접하게 관련된 접근방식은 만족도로서의 계획(Satplan)이다.둘 다 서로 다른 고정된 지평선 길이의 계획을 검색하기 위해 자동화된 계획 문제를 줄인다.
