[Study]Chapter 7. 제약 충족 문제

해당 포스트는 공부를 위해 개인적으로 정리한 내용으로 해당 도서에는 다양한 예시를 통해 좀 더 직관적인 이해가 가능합니다.

작성시 목차에 의존하지 말고 내가 직접 생각하면서 정리하기! 만약 목차대로 작성한다면 그냥 “깜지”랑 다를게 없지 않은가?

Artificial Intelligence : A Modern Approach 4th Edition

Part 3. 지식, 추론, 계획 수립 파트로 논리적 에이전트, 1차논리, 1차 논리의 추론, 지식 표현, 자도ㅓㅇ 계획 수립을 배울 예정이다.

이번 장에서는 복잡한 세계의 표현을 형성할 수 있고 추론 과정을 이용해서 세계에 대한 새로운 표현들을 유도할 수 있으며 그러한 새 표현들을 이용해서 다음에 할일을 연역할 수 이쓴ㄴ 에이전트를 설계한다.

연역

특정 -> 일반; 귀납 : 일반 -> 특정.

Chapter 7. 논리적 에이전트

지식 기반 에이전트는 지식의 내부 표현들에 작용하는 추론 과정을 활용해서 자신의 동작들을 결정한다. 문제 해결 에이전트가 사용하는 원자적 표현은 아주 제한적이다. 현재 삳ㅇ태에 관해 아는 것을 표현하는 유일한 방식은 모든 가능한 구체적 상태들을 나열하는 것 뿐이다. 6장에서는 상태를 변수에 값을 부여하는 배정들로 표현하는 방법을 이야기 했는데, 이는 분해된 표현의 첫 번쨰 사례에 해당한다. 이를 사용하면 에이전트의 일부 요소들이 영역 독립적 방식으로 작동하게 만들 수 있고 효율적인 알고리즘이 가능해진다. 이는 말 그대로 논리적 귀결로 연장한다. 즉, 논리를 지식 기반 에이전트를 지원하는 표현들의 일반적 부류로 취급한다.이런 에이전트는 정보를 다양한 목적에 맞게 조합 및 재조합핧 수 있다.

명시적으로 서술된 목표의 형태로 새 과제들을 받을 수 있으며, 환경에 대한 새로운 지식을 제공받거나 스스로 습득해서 경쟁력을 빠르게 갖출 수 있으며, 환경의 변화에 적응하거나 유관 지식을 갱신할 수 있다.

지식기반 에이전트

핵심 구성요소로 문장들의 집합인 지식 베이스가 있다. 각 문장은 지식 표현 언어라고 부르는 언어로 표현되며, 세계에 대한 어떤 단언\(_{assertion}\)을 나타낸다. 다른 어떤 문장에서 유도된 것이 아닌, 그 자체로 참이라고 간주되는 문장은 공리\(_{axiom}\)라고 부른다.

지식 베이스에는 새 문장을 추가흐는 TELL과 문장을 질의하는 ASK가 있고, 두 연산에는 기존 문장에서 새 문장을 이끌어 내는 과정인 추론이 관여한다. 즉, ASK로 지식 베이스에 질의했을 때, 이전 지식 베이스에 알려준 TELL 연산, 어떤 지식을 따른다는 요구조건을 충족해야한다.

Figure 1:초기에 지식 베이스에는 일정한 배경지식이 들어 있을 수 있다. 에이전트 프로그램은 TELL, ASK와 선택한 동작을 지식 베이스에 알려주고 자신을 호출한 곳에 동작을 돌려주는 세가지를 수행한다.

이러한 프로그램은 지식 수준에서의 서술을 준수하여 배경지식과 목표들만 지정해주면 에이전트 프로그램이 ㅈ동작을 결정할 수 있다. 자신의 목표를 달성하는 방법을 아는 에이전트는 구현 수준과는 독립적임을 주목해야 한다.

알아야할 모든 것을 TELL로 알려주는 단순한 방식으로 빈 지식 베이스에서 시작하여 하나씩 주입하는 선언적시스템 구축과 바람직한 행동을 프로그램 코드에 직접 집어넣는 절차적 접근 방식이 있다. 이 두 방식이 모두 들어 있는 경우가 많고, 스스로 학습하게 만드는 매커니즘을 제공할 수도 있어 학습하는 에이전트는 완전히 자율적인 에이전트가 될 수 있따.

• 지능적 에이전트가 좋은 결정을 내리려면 세계에 관한 지식이 필요하다.

• 에이전트 안에서 지식은 지식 표현 언어로 작성된 문장들의 형태로 존재하고, 에이전트 안에 지식 기반에 저장된다.

• 지식 기반 에이전트는 지식 베이스와 추론 매커니즘으로 구성된다. 세계에 관한 문장들을 지식 베이스에 저장하고 , 추론 매커니즘을 이용해서 새로운 문장을 추론하고, 그 문장들을 이용해서 다음 동작을 결정하는 식으로 작동한다.

웜퍼스 세계

지식 기반 에이전트의 가치가 돋보일만한 웜퍼스 세계를 설명한다.

Figure 2

2장에 나온 여러차원으로 분석하면 결정론적, 이산적, 정적, 단일 에이전트 환경이다. 주된 난제는 초기에는 환경의 구성에 대해 아는 것이 없다는 점이다. 이러한 무지를 극복하려면 논리적 추론이 필요하다.

이는 서로 다른 시간과 장소에서 얻은 지식을 결합해야하고, 중요한 진척을 이루는 데 지각의 ‘부재’를 고려해야 하나는 점에서 상당히 어려운 추론이다.

주어진 정보로부터 에이전트가 어떤 결론을 이끌어 낼 떄마다,. 만일 주어진 정보가 정확하다면 그 결론 역시 정확함이 보장된다는 점을 주목해야한다. 이는 논리적 추론의 근본 속성이다.

논리

논리적 표현과 추론의 근본 개념들을 개괄한다.

위에서 문장을 언급했는데 이 지식 표현 언어인 문장은 문장의 구조를 명시하는 문법인 표현 언어의 구문\(_{syntax}\)을 따른다.

논리는 문장의 의미론, 즉 문장의 뜻도 정의해야한다. 의미론은 각각의 가능한 세계(잠재적 실제 환경) 또는 모형(수학적인 추상) 안에서의 문장의 진릿값을 정의한다

문장 α가 모형 m에서 참일 떄, 이를 “m이 α를 충족한다”라고 말한다. α의 모든 모형의 집합을 M(α)라고 표기한다. 진리의 개념이 확실해졌으니, 논리적 추론을 이야기 해보자.

문장들 사이의 논리적 필연\(_{entailment}\) 또는 함축 관계가 관여한다. 함축이란 문장이 다른 문장을 “논리적으로 따른다”는 개념을 나타내는 용어로 아래와 같이 표현하여 α가 β를 함축한다는 뜻이다.

\[if M(α) \subseteq M(β), α \vDash β\]

α가 β보다 더 강한 단언으로 가능한 세계들을 β가 더 많이 배제하는 subset이 된다.

Figure 3 : $KB \vDash α_1$, KB는 $α_2$를 함축하지 않는다. 즉, 에이전트는 [2,2]에 구덩이가 없다는 결론을 도출할 수 없다

• 추론을 이해하려면 문장들 사이의 함축 관계가 아주 중요한다. 문장 α가 참인 모든 세계에서 문장 β가 참이면, α는 β를 함축한다. 동치 정의에는 문장 α=>β의 유효성과 문장 \(α\wedge\neg β\)의 충족 불가능성이 포함된다.

위의 예는 함축의 정의를 이용해서 결론을 이끌어내는 논리적 추론을 수행하는 방법을 보여준다. 추론 알고리즘을 모형 점검이라고 부르는데, 모든 가능한 모형을 훑으면서 점검하기 떄문이다.

함축된 문장들만 유도하는 추론 알고리즘을 가리켜 건전한 알고리즘이라고 칭한다. 건전성과 완결성은 바람직한 속성으로 근거 없이 꾸미지 않고, 함축된 임의의 문장을 유도할 수 있어야한다.

실제 세계에서 KB가 참이면, 건전한 추론 절차를 이용해서 KB에서 도출한 임의의 문장 α도 실제 세계에서 참이다. 비록 추론과정이 ‘구문’(내부적인 물리적 구성)들에 대해 작용한다고 해도, 그러한 과정은 실세계의 관계들에 아래와 같이 대응된다.

Figure 4 : ㅁㄴㅇ

마지막 고찰 문제로 실세계에서 참임을 어떻게 알 수 있는가의 근거짓기\(_{grounding}\) 문제이다.간단하게 에이전트의 감지기들이 그러한 연결을 만들어 낸다. 즉, 지각 문장들의 의미와 진리는 그에 대한 감지 과정과 문장 생성 과정에 의해 정의된다. 나머지 지식은 어떨까? 이는 어쩌면 지각적 경험으로 부터 유도한 일반적인 규칙으로 학습이라고 부르는 문장 구축 과정이 만들어 낸다. 이러한 학습은 틀리기 쉬운데, 실세계에서는 좋은 학습 절차가 있다면 낙관한 만한 이유가 존재한다.

• 추론은 기존의 문장들에서 새 문장을 이끌어 내는 과정이다. 건전한 추론 알고리즘은 오직 기존 문장들이 함축하는 문장들만 유도한다. 완결적인 추론 알고리즘은 기존 문장들이 함축하는 모든 문장을 유도한다.

명제 논리.

명제 논리는 구문과 의미론을 설명하고, 함축의 의미론적 개념을 구현하는 논리적 추론을 위한 간단한 구문적 알고리즘을 고안한다.

명제 논리는 명제 기호들과 논리 접속사들로 이루어진 간단한 언어로 명제 논리는 참임이 알려진 명제들과 거짓임이 알려진 명제들, 그리고 전혀 알려지지 않은 명제들을 처리할 수 있다.

• 구문
  • 허용되는 문장들을 정의. 원자적 문장\(_{literal}\)은 하나의 명제 기호로 구성.

  $\neg$ 부정;NOT

  $\wedge$ 논리곱;AND

  $\vee$ 논리합;OR

  $\Rightarrow$ 함의 또는 조건부 문장;implication; 좌항을 전제 또는 전항, 우항을 결론 또는 후건

  $ \Leftrightarrow$ 상호조건

  $\dot{\vee}$ 또는 $\oplus$ XOR 배타적 논리합

Figure 5 :

• 의미론
  • 특정 모형에 대한 문장의 진리를 결정하는 규칙들을 정의한다.
• 간단한 지식 베이스
• 간단한 추론 절차
  • 명제 논리적 함축은 co-NP-hard이다. 따라서, 명제 논리에 대한 모든 알려진 추론 알고리즘의 최악의 경우 복잡도는 입력의 크기에 대해 지수적이다.

명제 정리 증명

함축 관계 확인 알고리즘은 모형들을 열거하면서 문장이 모든 모형에서 성립하는지 점검하는 모형 점검 방식이다. 이번 절에서는 정리 증명을 이요해서 함축 관계를 확인하는 방법을 살펴본다.이 접근방식은 지식 베이스에 있는 문ㅁ장들에 추론 규칙들을 직접 적용해서 주어진 문장의 증명을 구축함으로써 함축 관계를 확인한다.

• 논리적 동치; if \(α \vDash β\)이고, \(β \vDash α\), \(α \equiv β\)
• 유효성; 모든 모형에서 참인 문장은 유효한 문장으로 \(P \wedge \neg P\)는 동어반복\(_{tautology}\)라고 한다. 이는 함축의 정의에서 연역 정리를 이끌어 낼 수 있따.
• 충족성; 주어진 문장을 충족하는 모형이 존재하면, 그 문장은 충족 가능한 문장이다. 명제논리에서 문장의 충족성을 결정하는 문제, 즉 SAT문제는 NP-완전임이 판명된 최초의 문제이다.

if \((α\wedge \neg β)\)가 충족불가능, \(α \vDash β\)

\((α\wedge \neg β)\)의 충족 불가능성을 점검해서 α로부터 β를 증명하는 것은 귀류법에 해당한다. 이를 반박에 의한 증명 또는 모순에 의한 증명으로 β를 거짓이라 가장허가ㅗ, 가정이 알려진 공리 α와의 모순으로 이어짐을 보인다.

추론과 증명

증명을 이끌어내는데 사용하는 추론 규칙을 살펴본다. 증명이란 어떤 원하는 목표로 이어지는 결론들의 사슬이다.

\[\frac{α\Rightarrow β, α}{β}\]

위와 같은 표현하는 형태를 증명을 구축하는데 쓰이는 규칙인 전건긍정이라고 한다. \(α\Rightarrow β, α\)가 주어졌을때, β를 추론할 수 있음을 뜻한다.

또 다른 추론 규칙은, 아래와 같은 논리곱 소거이다.

\[\frac{α\wedge β}{α}\] \[\begin{align*} &α:B_{1,1}; \space β:(P_{1,2} \wedge P_{2,1})&(1) \\ &(α \Rightarrow β) \wedge (β \Rightarrow α)&(2) \\ &(β \Rightarrow α)\text{(논리곱 소거)}&(3) \\ &\neg α \Rightarrow \neg β \text{(대우 명제에 대한 논리적 동치)}&(4) \\ &\text{위 수식과 }\neg β \text{를 통해 }\neg α\text{(전건긍정)}&(5)\\ &\neg P_{1,2} \vee \neg P_{2,1}\text{(즉, [1,2], [2,1]에는 구덩이가 없다.)}&(6) \end{align*}\]

검색 알고리즘 중 하나를 이용해서 증명을 구성하는 일련의 단계들을 찾아낼 수도 있따. 즉, 증명을 찾는 것은 모형들을 모두 열거하는 것의 한 대안이다. 실제 문제들에서는 증명을 찾는 것이 더효율적인 경우가 많은데, 이는 증명과 무관한 명제들은 무시할 수 있기 떄문이다.

논리 체계에서 살펴볼 마지막 속성은 단조성이다. 이는 지식 베이스에 정보가 추가됨에 따라 함축된 문장들의 집합이 항상 커지기만 함을 뜻한다. 단조성은 지식 베이스에서 적절한 전제를 찾았다면 언제라도 추론 규칙들을 적용할 수 있음을 뜻한다. 추론 규칙의 결론은 지식 베이스에 있는 다른 지식과는 무괂라게 옳아야한다.

분해증명

추론 알고리즘이 완결적인가? 분해라는 추론 규칙을 임의의 완결적 검색 알고리즘과 결합하면 완결적인 추론 알고리즘이 나온다.

\[\begin{align*} &\neg P_{2,2}&(1) \\ &\neg P_{1,1}&(2) \\ &P_{1,1} \vee P_{2,2} \vee P_{3,1}&(3) \\ &P_{1,1} \vee P_{3,1}&(4) \\ \end{align*}\]

위와 같이 (1)과 (3)을 활용하여 (4)라는 분해식을 얻었고, (2)와 (4)를 마찬가지로 분해하면 \(P_{3,1}\)을 얻게된다. 이 두 추론 단계는 다음과 같은 단위 분해 추론 규칙의 예이다.

\[\frac{l_1 \vee \cdots \vee l_k, m}{l_1 \vee \cdots \vee l_k}\]

위에서 \(l\)은 리터럴이고, \(l_i, m\)은 상보\(_{complementary}\) 리터럴 즉, 하나가 다른 하나의 부정인 리터럴들이다. 정리하자며느, 단위 분해는 절(리터럴들의 논리합)하나와 리터럴 하나로부터 새로운 절을 산출한다. 하나의 리터럴은 두 성분 모두 그리터럴인 논리합과 동치임을 주목하자. 이를 단위 절이라고 부리기도 하고 완전한 분해 규칙으로 일반화할수있따.

\[\frac{P \vee \neg Q \vee R, \neg P \vee Q}{\neg Q \vee Q \vee R}\]

P와 Q를 한꺼번에 분해해서 R을 추론할 수는 없고, 리터럴의 중복된 복사본들을 제거하는 것을 인수분해라고 부르는데 분해의 결과로 나오는 절에 각 리터럴의 복사본이 하나씩만 있어야한다.

이것이 완결적인 추론 절차들이 속한 모임의 기저를 형성해 분해 기반 정리 증명기는 명제 논리의 임의의 문장 α와β에 대해 \(α \vDash β\)의 진리를 결정할 수 있따.

• 논리곱 표준형; conjuntive normal form, CNF
  • 절들의 논리곱 형태로 이러우진 문장을 논리곱 표준형이라 부른다.
  • 분해 규칙은 절(즉, 리터럴들의 논리합)에만 적용되므로 모든 명제 논리 문장은 절들의 논리곱과 논리적으로 동치라는 점을 이용해 분해 규칙으로 모든 명제 논리를 위한 완결적인 추론 절차를 얻는다.

  Figure 6

• 분해 알고리즘

  Figure 7

• 분해의 완결성
  • 완결성 증명을 위해 분해 닫힘이라는 개념을 도입한다. 분해 규칙을 반복 적용해서 얻을 수 있는 모든 절의 집합을 분해 닫힘이라고 부른다.
  • Figure 8 구축할 수 있는 서로 다른 절들이 유한하다는 점을 생각하면 분해 닫힘이 유한하다는 걸 확인할 수 있다. 이러한 완결성 정리를 기초 분해 정리라고 부른다.

  만일 절들의 집합이 충족 불가능이면, 그 절들의 분해 닫힘에는 빈 절이 포함되어 있다.

  위 정리는 그 대우 즉, 만일 닫힘에 빈 절이 없으면 절들의 집합은 충족 가능이다가 참임을 보임으로써 증명할 수 있따.

• 주어진 고정된 명제 어휘하에서 가능한 모형들의 집합은 유한하다. 따라서 모형들을 모두 열거해서 함축 관계를 점검할 수 있다. 명제 논리를 위한 효율적인 모형점검 추론 알고리즘에는 역추적 방법과 국소 검색 방법들이 포함되는데, 이들을 이용해서 커다란 문제를 빠르게 풀 수 있는 경우가 많다.

혼 절과 한정절

완결성 덕분에 분해는 아주 중요한 추론 방법이 된다. 제한된 형태의 하나가 한정절이고, 긍정 리터럴이 정확히 하나인 논리합이다. 좀 더 일반적인 절이 혼 절로 긍정 리터럴이 최대 하나인 논리합이다. 긍정 리터럴이 하나도 없는 절을 목표절이라고도 부른다.

한정절만 담은 지식베이스가 흥미로운 이유는 세 가지이다.

1. 모든 한정절은 전제가 긍정 리터럴들의 논리곱이고 결론이 하나의 긍정 리터럴인 함의 문장으로 변환할 수 있다. 혼 형식에서는 전제를 본체, 결론을 머리, 긍정 리터럴 하나로 이루어진 문장을 사실이라 부른다.
2. 혼 절들에 대한 추론을 수행할떄는 순방향, 역방향 연쇄 알고리즘들로 논리 프로그래밍의 기초를 사용한다.
3. 혼 절들에 대한 함축 관계 판정에 걸리는 시간이 지식 기반 크기에 선형적이다.

순방향 연쇄와 역방향 연쇄

• 추론 규칙은 증명을 찾는 데 사용할 수 있는 건잔한 추론 패턴이다. 분해 규칙을 이용하면 논리고 ㅂ 표준형으로 표현된 지식 베이스를 위한 완결적인 추론 알고리즘을 만들 수 있다. 순방향 연쇄와 역방향 연쇄는 혼 형식의 지식 베이스를 위한 아주 자연스러운 추론알고리즘들이다.

순방향 연쇄 알고리즘 한정절들로 이루어진 지식 베이스가 하나의 명제 기호 q(query)를 함축하는지의 여부를 판정한다. 지식 베이스에 긍정 리터럴들로 시작한다.전제가 알려진 사실이라면 해당 결론을 알려진 사실들의 집합에 추가한다.

Figure 9 알려진 잎 노드 A와 B를 설정하고, 그래프를 따라 추론을 최대한 전파한다. 그 과정에서 논리곱을 만나면 그 논리곱의 성분들을 모두 처리한 후 다음으로 나아간다. 이러한 순반향 연쇄가 건전하다는 점은 모든 추론이 본질적으로 전건 긍정의 적용이기 떄문에 확인 가능하고 완결적이라는 것은 함축된 원자적 문장들이 모두 유도됨으로 오나결적이다. 더 나아가서 원래의 지식 베이스에 있던 모든 한정절은 이 모형에서 참이다.

순방향 연쇄는 좀 더 일반적인 데이터 주도적 추론, 즉 알려진 데이터에 초점을 두고 추론을 시작하는 추론 방식의 한 예이다. 에이전트가 이러한 추론 방식을 이용함으로써 입력된 지각들로부터 결론을 이껄어 낼 수있으며, 특정한 질의를 염두에 두지 않고 추론을 수행해서 새로운 결론을 얻을 수 있는 경우도 많다.

사람은 세심한 통제하에서 순방향 연쇄를 수행한다. 그러나 역방향 연쇄는 질의에서 시작해서 역방향으로 추론을 진행한다. 질의 q가 참임이 알려졌다면 더 이상의 작업은 필요하지 않다. 그렇지 않다면 알고리즘은 지식 베이스에서 결론이 q인 함의들을 찾는다. 만일 그 함의들 중 모든 저제를 증명할 수 있는 함의가 존재하면 q는 참이다. Figure 9에서 보는 것처럼 결국 알려진 사실 A와 B의 집합에 도달하며 이들은 증명의 토대를 형성한다. 역방향 연쇄는 목표 지향적 추론의 한 형태이다. 이는 “이제 무엇을 할것인가?” 같은 구체적인 질문의 답을 얻는데 유용하다.

효과적인 명제 모형 점검

모형 점검에 기초한 일반적인 명제 추론을 효율적으로 수행하는 두 부류의 알고리즘을 설명한다.이제부터 서술할 알고리즘들은 충족 가능성을 점검한다 즉, SAT 문제를 푼다.

컴퓨터 과학에는 명제 논리 문장의 충족 가능성 점검 문제로 환원할 수있는 조합 문제들이 대단히 만기 때문이다.

역추적 검색

데이비스-퍼트넘 알고리즘 DPLL이라 불리는 알고리즘은 본질적으로 모든 가능한 모형을 재귀적으로, 그리고 깊이 우선으로 열거한다.

• 이른 종료: 하나의 절은 참인 리터럴이 하나라도 있으면 참이다. 이렇게 이른 종료가 가능하면 검색 공간의 한 부분 트리 전체를 조사하지 않아도 된다.
• 순수 기호 발견법 : 순수 기호란 모든 절에서 부호가 같은 기호로 만일 문장에 모형이 존재한다면, 리터럴들이 참이 되게하는 순수 기호들로 이루어진 모형이 존재한다는 점은 쉽게 증명할 수 있따.
• 단위 절 발견법: 단위절은 리터럴이 단 하나인 절로 리터럴이 이미 지식 ㅔ이스에 있음을 증명하는 시도가 즉시 성공ㅎ한다는 것이다. C를 false로 설정하면, (C\(\vee\)A)가 하나의 단위 절이 되며, A에 true가 배정된다. 이러한 강제 배정들의 ‘중첩’을 가리켜 단위 전파라고 부른다.

1. 구성요소 분석: 변수들에 진릿값을 배정하는 과정에서 절들의 집합이 공통의 미배정 변수가 없는 서로소 부분집합들로 분리될 수 있따. 그런 부분집합을 구성요소러가ㅗ 부른다. 이런 부분 집합을들 효율적으로 검출할 수 있다면, 각 부분 집합을 개별적으로 처리함으로써 검색 속도를 크게 높일 수 있따.
2. 변수와 값의 순서: 임의의 변수 순서를 사용하며 차수 발견법을 이용하면 나머지 절들 중 가장 자주 나오는 변수를 먼저 시도할 수 있다.
3. 지능적 역추적 : 유관한 충돌 지점으로 즉시 되돌아가는 지능적 역추적을 수행하는 SAT 해결기는 어떤 형태로든 충돌 절 학습을 이용해서 기록하고 되풀이 하지 않는다.
4. 무작위 재시작 : 검색이 그리 진척되지 않는 경우 검색 트리의 최상단에서 다시 시작하되 변수나 값을 무작위로 선택한다. 해답을 더 빨리 발견하게 되는 것은 아니지만, 해답을 구하는데 걸리는 시간의 분산이 줄어드는 것은 확실하다.
5. 현명한 색인 적용

이러한 개선안들 덕분에 현대적인 해결기는 변수가 수천만개인 문제들도 처리할 수 있으며 사람이 일일이 증명들을 구축해야 했던 분야에 혁신을 가져왔다.

국소 언덕 오르기 검색

적절한 평가 함수를 선택한다면 충족 가능성 문제에도 이런 알고리즘들을 직접 적용할 수 있따. 목표는 모든 절을 충족하는 하나의 배정을 찾는 것이므로, 충족되지 않은 절들의 개수를 세는 평가 함수라면 그런 목적으로 사용할 수 있다. 일반적으로 공간에는 극솟ㄱ값들이 여럿 존재하는데, 극솟값에서 탈출하려면 다양한 형태의 무작위 성이 필요하다. 최근 몇년 사이에는 탐욕성과 무작위성 사이의 적절한 균형점을 차즌ㄴ 실험이 많이 진행되었다. 효과적인 알고리즘하나가 WALKSAT라는 아래와 같은 알고리즘이다

Figure 10

• WALKSAT 같은 국소 검색 방법들을 해답을 찾는 데 사용할 수 있다. 그런 알고리즘들은 건전하지만 완결적이지는 않다. 즉, 충족 불가능성을 항상 검출하지는 못한다.

무작위 SAT 문제들의 지형

충족 가능성 문제를 논리곱 표준형으로 고찰한다고 할 때, 과소 제약된 문제는 변수들을 제약하는 절들이 비교적 적은 문제에 해당한다. 반면 과대제약된 문제에서는 변수 개수에 비해 절들이 ㅏㄶ으며 해가 존재하지 않을 가능성이 높다.

Figure 11

이론적으로, 충족 가능성 문턱값 추축에 의하면, n이 무한대로 감에 따라 \(CNF_k(n,rn)\)이 충족될 확률이 문턱값 밑의 모든 r값에 대해 1이되고 문턱값 위의 모든 값에 대해서는 0이 되는 문턱값 비율 \(r_k\)가 존재한다.이제 충족가능한 문제들과 충족불가능한 문제들이 어디에 있는지 어느정도 확실하게 파악했다. 그렇다면 다음 질문은, 어려운 문제들은 어디에 있는가이다. 이들역시 문턱값 근처에 몰려 있 음이 판명되었다. 과소제약 문제들은 풍기각 ㅏ장쉽다. 과대제약문제들은 과소제약 문제들만큼 쉽지는 않지만 문턱값에 있는 ㅜㄴ제들보다는 훨씬쉽다.

명제 논리에 기초한 에이전트

에이전트가 자신의 지각 역사에 기초해서 세계의 상태를 가능한 한도까지 연역할 수 있게 만드는 것으로 동작들의 효과에 대한 완결적인 논리적 모형을 작성해야한다. 그 후에는 에인전트가 논리적 추론을 어떻게 활용하는지 살펴본다. 마지막으로, 지식 베이스가 실제 세계에서 참이기만 하다면 반드시 목표달성이 보장되는 계획들을 에이전트가 논리적 추론을 이용해서 구축하는 방법을 제시한다.

세계의 현재 상태

지식베이스는 공리들과 특정 세계에서의 에이전트의 경험으로 부터 얻은 지각문장들로 이루어진다. 우선 공리들을 수집하는 것으로 시작한다.지각 단언이 오직 현재 시간에에만 해당한다는 점에서 모순을 해결할 수 있따. 명제에 시간 단계를 연관시킨다는 착안은 ㅅ ㅣ간에 따라 변하는 세계의 다른 모든 측면에도 적용할 수 있다. 시간에 따라 변하는 측면을 유량이 라고 부리기로 하겠다 유량은 분해된 표현에 대한 논의에서 설명한 의미에서의 ‘상태 변수’와 동일한 것이다. 세계의 영속적인 측면에 연관된 기호에는 시간을 나타내는 ㅟ 첨자를 붙일 필요가 없고 그런 기호를 비시간적 변수라고 부리기도 한다.

전이 모형을 일단의 논리적 문장들로 표기해야한다. 세계가 변하는 방식을 서술하기 위해, 한 동작이 다음 시간 단계에 어떤 결과를 만들어 내는지를 지정하는 효과 공리들을 작성할 수 도 있다. 동작의 결과에 의해 변하지 않는 것이 무엇인지를 효과 공리가 말해주지 않는 문제가 발생하는데 이를 극복하려면 기준계 문제를 해결해야한다. 가능한 해법은 모든 명제가 동일하게 유지됨을 명시적으로 단언하는 기준계 공리들을 추가하는것이다.이들은 동작 하에서 시간 t에서 시간 t+1로 갈떄 모든 명제가 변하지 않고 그대로 유지됨을 명시적으로 단언한다. 그러나 기준계 공리들이 많아지면 추론의 효율이 눈에띄게 감소한다. 공리들의 집합의 크기는 \(O(mn)\)이 된다. 이러한 증상을 가리켜 표현적 기준계 문제라고 부르기도 한다. 이 문제가 중요한 이유는 실세계에 유ㅜ량들이 아주 많다는 것이다. 다행히 사람의 동작에 의해 변하는 유량들의 개수 k는 비교적 작다. 이는 세계가 국소성을 보이는 것에 해당한다. 또한 동작의 t-단계 계획의 결과들을 \(O(nt)\)가 아니라 \(O(kt)\)의 시간으로 순방향 투사하는 추론적 기준계 문제도 있다. 이런 문제의 해결책은 동작들에 대한 공리가 아니라 유량들에 대한 공리를 작성하는 것으로 초점을 바꾸어야 한다. 각 유량 F마다 t+1시간의 진릿값이 설정되는 방식은 두가지이다. 하나는 어떤 동작을 시간 t에 실행한 결과로 시간 t+1에서 F가 참이되는 것이고, 또 하나는 시간 t에서 F가 이미 참이며 시간 t에서 실행된 동작이 F를 거짓으로 바꾸지 않는것이다. 이론 종류의 공리를 후행 상태 공리라고 부른다.

표현적 추론적 기준계 문제들을 풀 수 있다는 것은 커다란 진보이지만, 어떤 동작이 의도된 효과를 내는 데 필요한 모든 전제 조건이 성립하는지 확인해야한다는 치명적인 문제점이 있다. 이러한 모든 예욀를 지정해야하는 문제를 가리켜 한정 문제라고 부른다. 논리 안에는 완전한 해답이 없다. 설계자가 모형을 얼마나 상세하게 명시할 것인지, 어떤 세부사항을 제외시킬 것인지 잘 판단해야한다.

혼성 에이전트

세계의 상태에 대한 여러 측면을 추론하는 능력을 조건-동작 규칙들 및 문제 해결 알고리즘들과 상당히 직접적인 방식으로 결합해서 혼성 에이전트를 만들어 낼 수 있다. 에이전트 프로그램은 지식 베이스와 현재 계획을 유지, 갱신한다. 초기의 지식베이스에는 비시간적 공리들, 즉 t에 의존하지 않는 공리들이 들어있다. 각 시간 단계에서는 새로운 지각 문장과 t에 의존하는 모든 공리들이 지식 베이스에 추가된다. 그런 다음 에이전트는 논리적 추론을 이용해서, 지식 베이스에 질의해서ASK 알아낸다.

논리적 상태추정

• 논리적 상태 추정을 위해서는 지금까지의 관측들에 일관적인 가능한 상태들의 집합을 서술하는 논리적 문장을 유지해야한다. 각각의 갱신 단계에는 환경의 전이모형을 이용한 추론이 요구되는데, 그러한 전이 모형은 각 유량의 변화 방식을 명시하는 후행 상태 공리들로부터 구축된다.

시간이 지남에 따라 ASK 호출에 관련된 계산 비용이 계속 높아진다. 주된 이유는 요구된 추론을 수행하려면 더 먼 과거로 돌아가야 하며, 더 많은 명제 기호를 처리해야 하기 떄문이다. 이를 오래 지속하는 것이 불가능함은 명백하다. 지각을 처리하는 시간이 수명에 비례해서는 안되고 필요한 것은 상수 갱신 시간이다. 즉 시간 t와는 무관해야한다. 추론의 결과들을 저장 또는 캐싱해두는 것이 해결책이 될 수 있따. 지난 지각들과 그 지각들의 모든 파급 효과의 역사를 믿음 상태, 즉 세계의 모든 가능한 현재 상태를 담은 집합의 어떠한 표현으로 대체할 수 있다. 새로 받은 지각들로 믿음 상태를 갱신하는 과정을 상태 추정이라고 부른다. 믿음 상태 짛ㅂ합은 물리적 상태 집합의 멱집합이다.물리적 상태는 \(2^n\)개이므로 믿음상태는 \(2^{2^{n}}\)개이다.

근사적 상태 추정을 위한 방안 중 하나로 믿음 상태를 리터럴들의 논리곱, 즉 1-CNF 논리식으로 표현하는 것이다. 에이전트 프로그램은 증명 가능한 리터럴들의 논리곱을 새로운 믿음 상태로 만들고, 이전의 믿음 상태는 폐기하면 된다. 시간이 지남에 따라 일부 정보가 소실 될 수 있음을 이해하는 것이 중요하다. 1-CNF 믿음 상탱 전체는 반드시 참이다. 따라서 이를 통해 표현되는 모든 가능한 상태의 집합은 완전한 지각 역사가 주어졌을 때 실제로 가능한 상태들을 모두 포함한다. 다시말해 보수적 근사로 작용한다. 복잡한 집합에 대한 보수적 근사라는 이러한 개념은 인공지능의 여러 분야에서 반복해서 나타나는 주제이다.

명젳 ㅜ론을 이용한 계획수립

에이전트는 논리적 추론을 사용하지만 계획을 수립할 떄에는 A*알고리즘을 사용한다. 계획을 논리적 추론을 이용해서 만드는 방법을 제시한다. 아래와 같은 명제 계획 수립 절차 SATPlan으로 에이전트는 목표에 도달하기까지의 단계 수를 알지 못하므로, 알고리즘은 가능한 단계들의 개수 t를 허용 가능한 최대 계획 길이 까지 점차 늘려가면서 시도한다.

Figure 12

활용의 관건은 지식 베이스를 제대로 구축하는 것이다. 함축 관계(ASK가 검증하는)에 대한 요구조건과 충족 가능성에 대한 요구조건 사이에는 중요한 차이가 존재한다. 필수적인 지식이 누락된 부분을 드러내 준다는 점에서, 해당 절차는 지식 베이스를 디버깅하는데 유용한 도구이다.

해당 절차는 불가능한 동작을 포함한 모형을 찾아내는데, 전제 조건이 충족되지 않은 동작들에 대해 후행 상태 공리들이 무엇을 말해 주는지 세심하게 살펴볼 필요가 있따. 실행 이후에 아무일도 일어나지않ㄹ는것은 정확히 예측하지만 실행할 수 없다는 ㅓㅁ은 말해주지 ㅏㄶ는다. 따라서 적법하지 않은 동작들이 포함된 계획이 생성되지 ㅏㄶ게 전제조건들이 충족되어야 함을 천명하는 전제조건 공리를 추가해야한다.

또한, 다수의 동시적 동작을 포함하는 계획을 생성한다는 점인데, 동작 배제 공리를 통해 모든 동작의 쌍에 대해 동시에 일어날수없다는 공리를 추가해야한다. 실제로 서로 간섭하는 동작에만 강제한다면 계획에 동시적 다중 동작이 포함되게 할 수 있따.

정리하자면, SATPlan은 초기 상태와 목표, 후행 상태 공리들, 전제고건 공리들, 동작 배제 공리들을 담은 문장에 대한 모형들을 찾아낸다. 그러한 공리들의 모임으로 충분하다는 점을 증명하는 것이 가능하다.

• 논리적 에이전트는 sAT 해결을 통해서, 즉 목표에 도달하는 미래의 동작열을 명시하는 가능한 모형들을 찾아냄으로써 의사결정을 수행할 수 있다. 이 접근방식은 완전 관측 가능 환경이나 무감지기 환경에서만 작동한다.

• 명제 논리는 크기가 무제한인 환경으로 확장되지 않는다. 이는 시간, 공간, 그리고 객체들 사이의 관계에 대한 보편적 패턴을 간결하게 표현하기에는 명제 논리의 표현력이 부족하기 때문이다.