[인공지능] 6-1 계획수립

계획수립

주어진 계획수립 문제의 임의의 초기 상태에서 목표 상태 중의 하나로 도달할 수 있게 하는 일련의 행동을 생성하는 것

로봇의 계획 수립

• 움직임 계획수립 : 원하는 움직임 작업을 수행하도록 제약조건을 만족시키면서 최소 비용으로 일련의 움직임을 찾아내는 일
• 경로 계획수립 : 시작 위치에서 목적 위치로 가기 위해 관절이나 바퀴를 이동시킬 순차적인 위치를 결정하는 일
• 궤적 계획수립 : 주어진 경로와 제약조건을 고려하여 매 시점의 관절 등의 위치, 속도, 가속도를 결정하는 일

계획수립 문제의 구성요소

• 초기상태에 대한 명세
• 원하는 목표 상태에 대한 명세
• 가능한 행동들에 대한 명세

계획수립 문제의 형태

1. 고전적 계획수립

• 가장 간단한 계획수립 문제 부류
• 기본전제
  • 초기 상태는 하나만 주어진다.
  • 행동들은 지속시간이 없고, 행동의 결과가 결정적이고, 한 번에 하나의 행동만 수행된다.
  • 행동을 하는 에이전트는 하나이다.
• 일련의 행동들을 수행한 이후의 세계의 상태 예측 가능

2. 마르코프 결정과정

• 행동들의 결과는 비결정적이고, 에이전트가 행동을 통제할 수 있는 문제
• 이산시간 마르코프 결정과정 문제
  • 행동들은 지속시간이 없다
  • 행동의 결과가 확률에 따라 결정되어 비결정적이다.
  • 행동의 결과는 관측 가능하여 확인할 수 있다.
  • 보상함수를 최대화하는 것을 목적으로 한다.
  • 행동을 하는 에이전트는 하나다.

3. 부분관측 마르코프 결정과정

• 행동의 결과가 확률에 따라 결정되는 비결정적인 마르코프 결정과정
• 행동의 결과가 부분적으로만 제공된다.
• 현재 상태에 대한 확률적인 분포를 믿음이라고 함
• 행동을 하면서 믿음을 계속 갱신

4. 다중 에이전트 계획수립

• 여러 에이전트가 있는 문제
• 하나의 공동목표를 위한 에이전트들이 계획수립하는 것
• 협상을 통해 계획을 정제하는 것
• 에이전트들이 작업을 조정하는 것

 

계획수립기

주어진 문제에 대한 계획을 생성하는 알고리즘 또는 프로그램

1. 특정 영역 계획수립기

• 해당 영역에 특화된 계획수립 방법
• 다른 영역에 적용 불가

2. 영역 독립 계획수립기

• 영역에 상관없이 적용할 수 있는 범용 계획수립기
• 특정영역 계획수립기에 비해 처리속도는 느림
• 모든 계획수립문제에 효과적인 계획수립기 개발 곤란
  • 적용 영역을 일부 제한하는 계획수립기 개발
• 계획수립 접근방법
  • 상태공간 계획수립
  • 계획공간 계획수립

3. 설정가능 계획수립기

• 영역 독립 계획수립기를 사용하면서 해당 영역의 문제를 해결하는 방법에 관한 정보를 입력으로 사용
• 특정영역 계획수립기 보다 계획수립의 범용성이 높음
• 영역독립 계획수립기 보다 처리 효율성이 좋음

 

계획수립 언어

• 계획수립 문제를 표현하는 데 사용되는 언어
• 고전적 계획수립 문제를 표현하는 언어
  • STRIPS, PDDL
  • 리터럴로 표현되는 상태변수가 중심

 

STRIPS

• 상태와 행동을 표현하기 위해 술어논리 사용
• 상태 : 변수와 함수를 포함하지 않은 긍정 리터럴들의 논리곱으로 표현
• 목표 : 리터럴들의 논리곱으로 표현, 부정 리터럴, 존재한정사가 붙은 것으로 간주되는 변수 가능
• 행동
  • 이름, 매개변수, 목록, precondition, effect로 구성
  • effect
    • 행동의 실행 후에 생기는 상태변화를 나타낸 것
    • 함수를 사용하지 않은 리터럴들의 논리곱으로 표현
    • 긍정리터럴들은 행동 실행으로 새로 생기는 성질 표현 (add-list)
    • 부정리터럴들은 행동 실행으로 더 이상 만족되지 않는 성질 표현 (delete-list)

 

PDDL

 계획수립 문제를 두 개의 파일에 나누어 저장

• domain 파일 : 술어, 행동에 대한 정보 저장 - 문제 영역 정의
• problem 파일 : 객체, 초기 상태, 목표 저장 - 문제 정의
• effect부분에서 not이 되는 부분이 STRIPS에서 delete-list에 해당
• 그렇지 않은 부분은 add-list에 해당
• ?로 시작하는 것은 변수

 

Quiz

계획수립은 과업을 수행하는 중에 수행될 수도 있다. (O)

계획수립은 과업 수행이 가능한 계획을 찾는다는 점에서 탐색과 관련성이 있다. (O)

계획수립 문제는 초기 상태, 목표상태, 가능한 행동들에 대한 명세를 통해 정의된다. (O)

PDDL에서 행동을 기술하는 문장은 domain파일에 저장된다. (X)