2022. 4. 30. 14:52ㆍMajor`/인공지능
Planning
(초기 상태 → 목표 상태)에 도달하기 위한 "Sequence Of Action"을 찾아내는 것
※ 계획 수립
(초기 상태 → 목표 상태)에 도달하기 위한 "Sequence Of Action"을 찾기 위해서 필요한 여러가지 환경/요소 등을 정의하는 것
>> 이렇게 도출된 Solution Plan은 "Optimal"해야 한다
- 최소 비용으로 목표에 도달
전통적 계획 수립의 여러가지 가정들
1. Environment
[AI] Agent
Agent (Rational Agent) 1. 자신이 놓인 환경에 대해서 "센서"를 통해서 환경에 대한 상태를 "추정" (Sensor Value 획득) 환경이 현재 어떤 상태인가 그 환경 속에서 나는 어떤 상태인가 2. Effectors를 통해서..
cs-ssupport.tistory.com
여기서 정의한 "환경의 특성"에서 볼 때 현실 세계에서의 환경 특성은 다음과 같다
- 부분 관측 (Partially Observable)
- 비결정 (Stochastic)
- 동적 (Dynamic)
- 연속적 (Continuous)
- 순차적 (Sequential)
- 멀티 에이전트 (Multi Agent)
하지만 "전통적 계획 수립"에서는 현실 세계와 전혀 반대의 환경 특성을 가정으로 한다
왜냐하면 현실 세계는 Planning을 하기에는 매우 복잡하고 어려운 상태이다
따라서 전통적 계획 수립에서는 모든 환경적 요소/특성들을 간단히 함으로써 계획 수립을 원활하게 할 수 있도록 해준다
완전 관측 (Fully Observable)
결정 (Deterministic)
정적 (Static)
이산적 (Discrete)
싱글 에이전트 (Single Agent)
2. Actions
또 다시 현실세계와 비교를 한다면
>> 현실세계에서 어떠한 동작을 수행할 때는 "반드시 동작 수행 시간"이 존재한다
하지만 전통적 계획 수립에서는 계획 수립의 편리함을 위해서 "Duration-Less >> 행동 자체의 수행 시간이 없다"라고 가정한다
일단 "계획 수립"을 하는 의미는 Agent가 수립된 계획을 파악하고 계획 수립 방식(탐색)을 활용해서 Sequence Of Action을 찾아내야 한다
따라서 State나 그에 따른 Action들은 Agent가 이해해야 한다
>> 그러므로 상태 표현/행동 표현은 "기호"로 표현해서 Agent가 이해할 수 있도록 해줘야 한다
상태 표현 (State Representation)
상태를 표현할때는 주로 "일차 술어 논리"로 표현을 한다
일차 술어 논리란 on(C, B)/on(B, A)/on(A, Table)처럼 그냥 간단하게 표현하는 것이다
- 여기서 on, left, right 등을 "Predicates"라고 한다
- C, B, A, Table 등은 "Objects"라고 한다
※ 상태 표현 조건
1. 긍정형 표현
상태만을 표현할 경우에는 "부정적"으로 표현하지 말아야 한다
예를 들어서 Not on(C, B)에서의 "Not"과 같은 부정형 표현은 "상태 표현"에서 사용하면 안된다
2. Predicates 인자 제한
on(C, B)에서 Predicates의 인자란 {C, B}등을 가리키고 이 인자들은 오직 "상수"만 사용해야 한다
상태를 인식할 때는 그 상태 그대로 인식하므로 인자로 당연히 상수가 들어가야 하고 환경을 정의할 때 사용되는 PDDL (domain.pddl)에서는 predicates의 인자로 변수를 선언함으로써 어떠한 objects도 변수에 대입가능하도록 설계한다
예를 들어서 on(?x-block ?y-block)라고 상태를 표현하면 Agent는 이 상태가 도대체 무엇인지 당연히 모를 것이다.
3. 미래에 대한 가정 X (Closed world Assumption)
여기서 미래란 "언급되지 않은 사실"을 의미한다
당연히 State는 Action에 의해서 변경될 것이다
예를 들어서 현재 C-B-A순으로 쌓여있다고 생각하자
근데 미래에 어떤 Action에 의해서 C가 Table위로 내려왔다고 하자
>> 여기서 "미래에 대한 가정"인 "C가 Table 위로 내려왔다"는 현재 알 수 없는 사실이므로 모두 거짓이라고 가정한다
행동 표현 (Action Representation)
Action은 "Preconditions" & "Effects"로 묘사될 수 있다
어떤 Action을 수행하는 것은 "현재 상태로부터 해당 Action이 가능하다"와 "해당 Action을 취하고 환경이 어떻게 변하게 될 것인지"를 파악하고 있다는 것이다
Preconditions
Action을 적용하기 "전"에 반드시 만족되어야하는 여러가지 조건들
Effects
Action을 적용한 "후"에 환경이 어떻게 변할 것인지에 대한 여러 효과들
PDDL
"Planning Domain Definition Language"
PDDL은 Symbolic Logic을 통해서 (States/Actions/Goals)를 묘사하게 된다
그리고 PDDL은 크게 2가지 .pddl 파일로 나뉘어져 있다
domain.pddl
domain.pddl이란 "계획 수립을 위한 환경"을 정의해놓은 pddl 파일이다
Objects
계획 수립을 위한 환경에 존재하는 여러가지 물체들
예를 들어서 "블록 쌓기"라는 계획 수립 환경에 존재하는 물체는 "Blocks"일 것이다
실제로 이러한 Objects들을 조작함으로써 목표 상태에 도달하게 된다
Predicates
Objects들간의 "관계"를 서술해준다
- 환경내에서 가능한 "물체들간의 관계"를 묘사한 것이다
"블록 쌓기"에서 Predicates는 다음과 같다
on(x, y) : x가 y위에 존재
ontable(x) : x가 테이블위에 존재
clear(x) : x위에 아무것도 없다
handempty() : "Agent" 손이 비었다
hold(x) : "Agent"가 x를 들고 있다
>> Agent도 환경안에 존재하는 "물체"라고 볼 수 있으며, handempty() & hold(x)는 "Block - Agent"간의 관계를 나타낸 것이다
이러한 state에서 구체화한 predicates는 다음과 같다
clear(C)
clear(B)
ontable(A)
ontable(B)
on(C A)
실제로 이런 구체화는 task/problem.pddl에서의 "init"을 정의할 때 표현한다
Actions
Action이란 말그대로 계획 수립을 위한 환경에서 수행할 수 있는 여러가지 행동들이다
Action들은 존재하지만 "현재 State"에서 해당 action들이 가능한지는 먼저 (action → precondition)을 확인해야 한다
만약 Precondition을 만족한다면 현재 환경에서 해당 action을 수행하고 그에따른 state 변화를 적용해야 한다
"블록 쌓기"에서 가능한 Action은 다음과 같다
pick-up : 테이블 위에 있는 블록 하나 집어올리기
put-down : 들고있는 블록 내려놓기 (table 위에다 내려놓기)
stack : 들고있는 블록을 어느 블록위에 내려놓기
unstack : 어느 블록위에 쌓여진 최상위 블록 들기
task/problem.pddl
task/problem.pddl이란 "계획 수립을 위한 초기 상태/목표 상태"를 정의해놓은 pddl 파일이다
따라서 추상화 개념인 domain.pddl을 여기서 구체화한다고 볼 수 있다
Initial State
굉장히 구체적인 초기 상태를 술어 논리로 묘사해야 한다
Goal Conditions
Goal State가 아닌 Goal Conditions인 이유는 다음과 같다
"블록 쌓기"에서 예를 들어서 (B가 A위에 있어야 한다/C는 D 위에 있어야 한다)라는 조건이 있다고 하자
이 조건을 만족하는 Goal State는 당연히 여러가지 존재한다
>> 여기서 Goal Conditions을 만족하기만 하면 Goal State로 인정한다는 의미이다
따라서 Goal Conditions는 추상적인 목표 조건이고 "계획 수립 방식"에 따라서 만족만 한다면 즉시 계획 수립이 완료되었다고 볼 수 있다
▶ B - A
▶ C - D
>> Goal Condition 만족
▶ B - A - C - D
>> Goal Condition 만족
▶ C - D - B - A
>> Goal Condition 만족
따라서 여러가지 Goal State가 나올 수 있다
Example) Blocks World
domain.pddl & task/problem.pddl을 정의해야한다
domain.pddl
define (domain ~~)
일단 domain(환경)을 define해야 한다. 당연히 define된 Name이 존재해야 한다
여기서 domain은 java로 생각해보면 "Class"의 개념과 유사하다
당연히 "Class Name"은 설계자 마음대로 작성할 수 있다
domain.pddl에서 Class Name은 <domain ~~~>로 작성한다
define (domain BLOCKS)
types
types란 말그대로 Objects의 추상적 type을 가리킨다
"블록 쌓기"니까 Objects인 여러 블록들 (x, y, z, ...)의 추상적 type은 "block"이다
(:types block)
predicates
predicates는 실제 Objects간의 존재하는 여러 관계들을 정의한다
Parameters로 들어가는 Objects는 domain.pddl에서는 구체화하지 않기 때문에 추상적으로 묘사한다
(:predicates
(on ?x-block ?y-block)
(ontable ?x-block)
(clear ?x-block)
(handempty)
(holding ?x-block)
)
action
action은 여러가지가 존재할 수 있다
1. pick-up
pick-up이라는 것은 "Agent가 table위에 놓여진 블록 하나를 집는다"라는 action이다
action에는 precondition과 action에 따른 effect를 정의해야 한다.
그리고 action을 위해 필요한 추상화된 Objects를 Parameter로 던져줘야 한다
▶ Parameters
pick-up을 해야하니까 당연히 파라미터로 "블록 하나"를 주어야 한다
:parameters (?x-block)
▶ Precondition
pick-up을 위한 선행 조건은 다음과 같다
(clear ?x) : x를 집어야 하니까 x 위에는 아무것도 없어야 한다
(ontable ?x) : 테이블위에 있는 x를 집는 action이니까 x는 테이블위에 존재해야 한다
(handempty) : x를 집어야 하는 Agent는 현재 손에 아무것도 없어야 한다
:precondition
(and
(clear ?x)
(ontable ?x)
(handempty)
)precondition이 여러가지일 경우 "and"를 통해서 표현해준다
▶ Effect
pick-up을 수행하고 환경의 변화는 다음과 같다
(holding ?x) : Agent가 x를 집었으니까 holding으로 표현해준다
(not (handempty)) : Agent가 x를 집었으니까 더이상 handempty는 아니다
(not (ontable ?x)) : x는 Agent가 집었으니까 x는 더이상 테이블위에 존재하지 않는다
(not (clear ?x)) : x는 현재 Agent에 의해서 들어올려진 상태니까 table위에서는 clear였던 x의 clear 상태는 더이상 모른다
:effect
(and
(holding ?x)
(not (handempty))
(not (ontable ?x))
(not (clear ?x))
)
전체적인 pick-up에 대한 action Code는 다음과 같다
(:action pick-up
:parameters (?x-block)
:precondition
(and
(handempty)
(clear ?x)
(ontable ?x)
)
:effect
(and
(not (handempty)
(holding ?x)
(not (clear ?x))
(not (ontable ?x))
)
)
2. put-down
put-down이라는 것은 "Agent가 table위에 블록 하나를 내려놓는다"라는 action이다
▶ Parameters
put-down은 당연히 블록 하나를 내려놓으니까 parameter로 블록 하나를 전달한다
:parameters (?x-block)
▶ Precondition
put-down을 위한 선행 조건은 다음과 같다
(holding ?x) : 당연히 put-down을 하려면 Agent는 들고있는 블록 하나가 있어야 한다
:precondition
(holding ?x)
▶ Effect
put-down을 수행하고 환경의 변화는 다음과 같다
(not (holding ?x)) : x를 테이블위에 내려놓았으니까 Agent는 더이상 x를 들고있지 않는다
(handempty) : x를 테이블위에 내려놓았으니까 Agent는 손이 비게 된다
(clear ?x) : x를 테이블위에 내려놓았으니까 x위에는 아무것도 없다
(ontable ?x) : x를 테이블위에 내려놓았으니까 x는 테이블 위에 존재한다
:effect
(and
(not (holding ?x))
(handempty)
(clear ?x)
(ontable ?x)
)
전체적인 put-down에 대한 action Code는 다음과 같다
(:action put-down
:parameters (?x-block)
:precondition
(holding ?x)
:effect
(and
(not (holding ?x))
(handempty)
(clear ?x)
(ontable ?x)
)
)여기서 precondition은 하나이므로 and를 사용할 필요가 없다
3. stack
pick-up이라는 것은 "Agent가 어느 최상위 블록위에 블록 하나를 내려놓는다"라는 action이다
▶ Parameters
stack이란 "어느 최상위 블록위에 들고있는 블록을 내려놓는다"라는 action이므로 최상위 블록이 무엇인지 & 내려놓을 블록이 무엇인지에 의해서 2개의 block을 parameter로 전달해야 한다
:parameters (?x-block ?y-block)
▶ Precondition
stack을 위한 선행 조건은 다음과 같다
(holding ?x) : x를 stack해야하니까 Agent는 x를 들고있어야 한다
(clear ?y) : x를 y위에 올려놓을거니까 y 위에는 깨끗해야 한다
:precondition:
(and
(holding ?x)
(clear ?y)
)
▶ Effect
stack을 수행하고 환경의 변화는 다음과 같다
(not (holding ?x)) : Agent는 x를 더이상 들고있지 않는다
(handempty) : Agent는 x를 y에 내려놓았으므로 손에 들고있는게 없다
(clear ?x) : x를 y위에 올려놓았으니까 x위에는 깨끗하다
(not (clear ?y)) : y위에 x가 올라왔으니까 y위에는 더이상 깨끗하지 않다
(on ?x ?y) : 결론적으로 x는 y위에 올라갔다
:effect
(and
(not (holding ?x))
(handempty)
(clear ?x)
(not (clear ?y))
(on ?x ?y)
)
전체적인 stack에 대한 action Code는 다음과 같다
(:action stack
:parameters (?x-block ?y-block)
:precondition
(and
(holding ?x)
(clear ?y)
)
:effect
(and
(not (holding ?x))
(handempty)
(clear ?x)
(not (clear ?y))
(on ?x ?y)
)
)
4. unstack
pick-up이라는 것은 "Agent가 어느 블록위에 놓여진 최상위 블록 하나를 집는다"라는 action이다
▶ Parameters
unstack이란 "어느 블록위에 놓여진 최상위 블록 하나를 집는다"라는 action이므로 들어올릴 최상위 블록이 무엇인지 & 해당 최상위 블록이 어느 블록 위에 존재하는지에 의해서 2개의 block을 parameter로 전달해야 한다
:parameters (?x-block ?y-block)
▶ Precondition
unstack을 위한 선행 조건은 다음과 같다
(on ?x ?y) : 일단 x가 y위에 존재해야 한다
(clear ?x) : 들어올릴 x 위에는 깨끗해야 한다
(handempty) : x를 들어올릴 Agent는 현재 손에 아무것도 없어야 한다
:precondition
(and
(on ?x ?y)
(clear ?x)
(handempty)
)
▶ Effect
unstack을 수행하고 환경의 변화는 다음과 같다
(holding ?x) : x를 집었으니까 Agent는 x를 들고있어야 한다
(not (handempty)) : x를 집었으니까 Agent는 더이상 손에 아무것도 없지 않다
(not (clear ?x)) : x를 집었으니까 x위에 clear인지 관심이 없다
(clear ?y) : x를 집었으니까 x밑에 있는 y의 위는 이제 깨끗하다
(not (on ?x ?y)) : 결론적으로 x는 y위에 존재하지 않는다
:effect
(and
(holding ?x)
(not (handemtpy)
(not (clear ?x))
(clear ?y)
(not (on ?x ?y))
)
전체적인 unstack에 대한 action Code는 다음과 같다
(:action unstack
:parameters (?x-block ?y-block)
:precondition
(and
(clear ?x)
(handempty)
(on ?x ?y)
)
:effect
(and
(holding ?x)
(not (handempty))
(not (clear ?x))
(clear ?y)
(not (on ?x ?y))
)
)
※ Full "domain.pddl"
(define (domain BLOCKS)
(:types block)
(:predicates
(on ?x-block ?y-block)
(ontable ?x-block)
(clear ?x)
(holding ?x)
(handempty)
)
(:action pick-up
:parameters (?x-block)
:precondition
(and
(clear ?x)
(ontable ?x)
(handempty)
)
:effect
(and
(not (clear ?x))
(not (handempty))
(holding ?x)
(not (ontable ?x))
)
)
(:action put-down
:parameters (?x-block)
:precondition
(holding ?x)
:effect
(and
(not (holding ?x))
(handempty)
(ontable ?x)
(clear ?x)
)
)
(:action stack
:parameters (?x-block ?y-block)
:precondition
(and
(holding ?x)
(clear ?y)
)
:effect
(and
(not (holding ?x))
(handempty)
(clear ?x)
(not (clear ?y))
(on ?x ?y)
)
)
(:action unstack
:parameters (?x-block ?y-block)
:precondition
(and
(handempty)
(clear ?x)
(on ?x ?y)
)
:effect
(and
(holding ?x)
(not (handempty))
(not (clear ?x))
(clear ?y)
(not (on ?x ?y))
)
)
)
task/problem.pddl
define (problem ~~)
여기서는 풀어야할 problem이 정의된다
problem의 Name은 설계자 마음대로 정의해도 된다
define (problem BLOCK-6)
domain
어느 domain을 활용할 것인지 정의해줘야 한다
우리는 위에 domain.pddl에서 정의한 (domain BLOCKS)를 사용할 것이다
(:domain BLOCKS)
objects
이전에 domain.pddl에서는 추상적인 "types"를 정의하였다
task/problem.pddl에서는 추상적 개념인 types를 objects로 구체화해야 한다
(:objects A B C D E F - block)
init
초기 상태란 "눈에 보이는 현재 상태" 그대로를 굉장히 구체적으로 묘사해야 한다
domain.pddl에서 추상화시킨 predicates를 여기서는 구체화해야 한다
(:init
(handempty)
(clear A)
(clear D)
(clear F)
(ontable C)
(ontable D)
(ontable B)
(on A E)
(on E C)
(on F B)
)
goal
여기서는 Goal 조건만을 설정해주면 된다 :: Goal Conditions
(:goal
(and
(on B C)
(on C F)
(on F A)
(on D E)
)
)
※ Full "domain.pddl"
(define (problem BLOCK-6)
(:domain BLOCKS)
(:objects A B C D E F - block)
(:init
(handempty)
(clear A)
(clear D)
(clear F)
(ontable C)
(ontable D)
(ontable B)
(on A E)
(on E C)
(on F B)
)
(:goal
(and
(on B C)
(on C F)
(on F A)
(on D E)
)
)
)
실제로 정의한 domain.pddl & task/problem.pddl을 "Google Colab"을 사용해서 계획 수립을 하게 되면 결과는 다음과 같다
▶ task56.pddl.soln (Solution)
(unstack a e)
(put-down a)
(unstack f b)
(stack f a)
(unstack e c)
(put-down e)
(pick-up c)
(stack c f)
(pick-up b)
(stack b c)
(pick-up d)
(stack d e)
위에 설명한 것은 "계획 수립"과 관련된 것이고 계획이 수립되었다면 Agent는 어떻게 스스로 계획을 수립할까?? :: "계획 수립 방식"
전통적 계획 수립 방식은 "Forward State-Space Search(+ Heuristics)"를 사용한다
일단 <initial state>로부터 가능한 action들을 수행하고 그 결과를 Tree형태로 펼치는 것은 이전의 여러 탐색 방식과 유사하다
여기서 당연히 알아야할 것은 "action에 의해서 그 상태에서의 State는 변경"이라는 사실이다
이전에 domain.pddl에서 여러가지 action들을 미리 정의하였다
여기서 action은 (parameters & precondition & effect)들이 존재한다
1. 현재 놓여진 환경에서 먼저 action을 수행할 수 있는 precondition이 만족되었는지부터 확인
→ precondition이 만족되었으면 action을 수행하고 만족되지 않았으면 skip한다
2. action을 수행하고 "effect"에 따른 <현재 state>를 update한다
예를 들어서 "action : unstack"을 보게되면
(:action unstack
:parameters (?x-block ?y-block)
:precondition
(and
(clear ?x)
(handempty)
(on ?x ?y)
)
:effect
(and
(holding ?x)
(not (handempty))
(not (clear ?x))
(clear ?y)
(not (on ?x ?y))
)
)effect는 크게 2가지로 나눌 수 있다
▶ 긍정적 effect
(holding ?x)
(clear ?y)
▶ 부정적 effect
여기서 부정적 effect라고해서 환경에 안좋은 영향을 미치는 것은 아니다
단지 not이 붙은 effect를 의미한다
(not (handempty))
(not (clear ?x))
(not (on ?x ?y))
initial state가 다음과 같다 unstack action을 수행했다고 하자
## initial state ##
(clear C)
(clear B)
(ontable A)
(ontable B)
(on C A)
여기서 unstack을 수행하면 initial state에서 "긍정적 effect는 추가"하고 "부정적 effect"는 제거하면 된다
1. 긍정적 effect 추가
(clear C)
(clear B)
(ontable A)
(ontable B)
(on C A)
(holding C)
(clear A)
2. 부정적 effect 제거
(not (handempty)) ~> (handempty) 제거
(not (clear ?x)) ~> (clear C) 제거
(not (on ?x ?y)) ~> (on C A) 제거
(clear B)
(ontable A)
(ontable B)
(holding C)
(clear A)
이제 이것이 "unstack action"에 의한 "새로운 State"가 될 것이다
