스튜어드 러셀의 인공지능을 읽어보자(7) : 문제 형식화

다시 돌아온 인공지능을 읽어오자입니다.

저번 글은 startagainbornagain.tistory.com/78

스튜어드 러셀의 인공지능을 읽어보자(6) : 검색을 통한 문제 해결

이고요

문제 형식화

앞에서는 루마니아 여행(부쿠레슈티로 도달하는 예)으로 초기 상태와 동작들, 전이 모형, 목표 판정, 경로 비용으로 형식화해 보았습니다. 이는 여전히 하나의 모형, 즉 추상적인 수학적 서술이지 실질적인 어떤 것은 아닙니다. 표현에서 세부사항을 제거하는 절차를 추상화(abstractonh)라고 합니다.

지금 현재 상황에 대한 상태 서술의 추상화는 물론, 동작 자체의 추상화도 필요합니다. 그 이유는 항상 환경은 바뀌고 그에 따라 동작도 능동적으로 바뀌어야 하기 때문입니다.

하지만 추상화는 '정확한' 행동을 명시하지는 않습니다. 그렇다면 이 '적절한' 추상화 수준을 좀 더 정밀하게 정의할 수 없을까요?

상세한 세계 상태들과 상세한 동작 열들의 커다란 집합과 대응되는 추상적인 상태들과 동작들을 앞에서처럼 선택했다고 합시다. 그리고 추상적인 문제에 대한 해답을 하나 고찰해봅시다. 예를 들어 저번 루마니아 예를 대입하여 시비우, 림니쿠 빌 차, 피 테스티를 거쳐 부쿠레슈티로 도달하는 경로를 선택했다고 합니다.

이 추상적 해는 다수의 좀 더 상세한 경로들에 대응됩니다. 예를 들어 시비우와 림니쿠 빌 차 사이에서는 라디오를 켜고 주행을 하다가 그 이후부터는 내내 라디오를 끄고 주행할 수도 있습니다. 임의의 추상적 해답을 좀 더 상세한 세계의 한 해답으로 확장할 수 있다면 그 추상은 유효합니다(valid). 이에 대한 충분조건은 "아라드에 있음"에 해당하는 모든 상세 상태에 대해 "시비우에 있음"에 해당하는 상태로의 상세 경로가 존재한다는 것입니다. 만일 추상화된 문제의 해답에 있는 각 동작을 원래 문제의 것보다 더 쉽게 수행할 수 있다면, 그 추상화는 유용합니다(useful). 지금 예에서 동작들은 평균적인 주행 에이전트가 추가적인 검색이나 계획 수립 없이도 충분히 수행할 수 있을 정도로 쉽습니다. 따라서 좋은 추상화에는 유효성을 유지하고 추상적 동작들을 쉽게 실행할 수 있음을 보장하는 한도 안에서 세부사항을 최대한 제거하는 것이 관여합니다. 유용한 추상을 구축하는 능력이 없다면 지능적 에이전트는 현실 세계에 완전히 매몰될 것입니다. 

 

문제의 예

 

문제 해결 접근방식은 광범위한 과제 환경에 적용된 바가 있습니다.  이번에는  가장 잘 알려진 몇 가지 과제 환경을 장난감 문제와 실세계 문제로 구분해서 나열하여 봅시다. 장난감 문제(toy problem)들은 다양한 문제 해결 방법의 이해 또는 연습을 목적으로 한 것입니다. 실세계 문제(real - world problem)들은 사람들이 그 해답을 실제로 원하고 요구하는 문제들입니다. 이런 문제들은 모두가 동의하는 한 가지 방식으로 서술하기 힘든 경우가 많은데, 아래에 나온 서술에서 적어도 해당 형식화들의 전반적인 상을 파악할 수는 있을 것입니다.

 

출처 위키백과 (https://en.wikipedia.org/wiki/Toy_problem)

장난감 문제들

첫 번째로 살펴볼 것은 진공청소기 세계입니다. 이 세계는 이렇게 형식화될 수 있습니다.

• 상태: 상태들은 에이전트 위치와 먼지들의 위치 모두에 의해 결정됩니다. 에이전트는 두 장소 중 하나에 있으며, 각 장소에는 먼지가 있을 수도 있고 없을 수도 있습니다. 따라서 가능한 세계 상태는 총 8가지(2*2^2)입니다. 장소가 n개인 좀 더 큰 환경이라면 n * n^2입니다.
• 초기 상태: 어떤 상태라도 초기 상태로 지정될 수 있다.
• 동작들: 이 간단한 환경에서 각 상태마다 가능한 동작은 Left, Right, Suck 세 가지뿐입니다. 더 큰 환경이라면 Up과 Down도 포함될 것입니다.
• 전이 모형: 동작마다 기대 효과가 있습니다. 단, 제일 왼쪽 사각형에서의 Left 이동 동작과 제일 오른쪽 사각형에서의 Left 이동 동작과 제일 오른쪽 사각형에서의 Right 이동 동작, 그리고 깨끗한 사각형에서의 Suck 동작에는 효과가 없습니다. 
• 목표 판정: 모든 사각형이 깨끗하면 목표가 달성된 것입니다.
• 경로 비용: 각 단계의 비용을 1로 가정하므로 경로 비용은 경로의 단계 수입니다.

 

 

출처 https://www.lotteon.com/p/product/LO1035402743?sitmNo=LO1035402743_1035402744&mall_no=1&dp_infw_cd=SCH%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9%ED%8D%BC%EC%A6%90

8-퍼즐은 번호가 표시된 타일 여덟 개와 빈칸 하나로 이루어진 3*3 크기의 판에서 진행됩니다. 빈칸에 인접한 타일은 그 공간으로 밀어서 움직일 수 있습니다. 목적은 지정된 목표 상태(위 사진과 같이)에 도달하는 것입니다 표준적인 형식화는 이렇습니다.

• 상태들: 상태 서술은 여덟 타일 각각의 위치와 빈칸의 위치를 지정합니다.
• 초기 상태: 어떤 상태라도 초기 상태로 지정될 수 있다. 모든 초기 상태 중 임의의 주어진 목표에 도달할 수 있는 것은 정확히 절반이다.
• 동작들: 가장 간단한 형식화는 빈칸으로의 이동에 해당하는 동작들인 Left, Right, Up, Down입니다. 특정 상태에서, 빈칸의 위치에 따라서는 이들 중 일부만 가능할 수도 있습니다.
• 전이 모형: 상태와 동작이 주어졌을 때 전이 모형은 그 동작의 결과로 나온 상태를 돌려줍니다.
• 목표 판정 : 현재 상태가 목표 구성과 부합하는지 판정합니다.
• 경로 비용: 각 단계의 비용을 1로 가정하므로 경로 비용은 경로의 단계 수입니다.

그 외 8-퀸이나 다른 문제들에서도 형식화를 할 수 있습니다.

이렇게 특정 가정 상황뿐만 아니라 실세계 문제에서도 적용이 가능합니다.

 

실세계 문제들

노선 찾기 문제, 순회 문제, 순회 판매원 문제와 같은 것들이 있으니 이런 실세계 문제는 여러분들이 직접 생각해서 답을 내려보세요!

 

오늘은 이렇게 끝내고요 다음에는 해답 검색에 대해 공부해보도록 하겠습니다.