글 수 27

MDP 기반의 스케줄링 구현

조회 수 1312 추천 수 0 2016.03.24 03:36:23


mdp.jpg

 

소스코드 : 첨부파일

 

 

 

MDP(Markov Decision Process)의 개요

 

어떤 주어진 환경에서 최적의 행동을 결정하는 문제는 여러 분야에서 중요하게 고려되는 사항중의 하나이다. 예를 들어 아래 그림과 같이 현재 위치부터 목적지 까지 가장 최적의 길을 찾는 문제를 생각해보자.

 

figure1.jpg

 

 

 

현재 위치에서 가능한 행동은 여러 방향 중 하나를 선택하는 것이다. 그런데 각 행동마다 결정할 수 있는 확률이 다르고(특정한 길을 더 좋아한다던지), 각 행동을 수행했을 때 주어지는 보상값이 다를 때(특정한 길이 더 빠르다면 높은 보상값을 얻는 것처럼), 현재 위치에서 최적의 행동을 결정할 수 있다면 목적지까지 가장 효율적으로 도착할 수 있을 것이다.

 

이러한 결정을 위해서 각 상태(위치)에서 확률과 보상값에 기반하여 각 행동을 수행했을 때의 행동값(V)을 계산할 수 있다면, 가장 높은 수치의 행동을 선택함으로써 최적의 행동을 결정할 수가 있다. 이러한 목적을 위해서 MDP 모델을 사용할 수 있다. MDP가 활용되는 분야는 로봇의 길찾기, 공장의 작업공정 조절 등 여러 복잡한 문제들에서 사용될 수 있다.

 

 

 

강화학습(Reinforcement Learning)으로의 확장

 

MDP 모델을 구현하기 위해서는 각 상태들을 정의할 수 있어야 하고, 각 행동마다 확률과 보상값이 주어져야 한다. 주어진 환경의 범위가 작을 경우에는 이러한 조건들을 얻을 수 있지만, 범위가 커질 경우 상태의 개수가 엄청나게 증가하고 확률이나 보상값을 결정하기 불가능할 수 있다.

 

이러한 경우에는 최적의 행동을 결정하기 위해 계산을 할 수가 없으므로 보통 강화학습이란 방법을 사용한다. 확률이나 보상값이 주어져있지 않아도 여러번 반복을 통한 학습으로 각 행동에 대한 행동값을 추정할 수 있다.

 

 

 

MDP기반의 스케줄링 구현

 

대학원 확률 동적 프로그래밍이란 과목의 프로젝트로 MDP를 사용하여 간단한 작업 스케줄링을 구현하여 보았다. 왼쪽의 건물에서 각각 다른 확률로 유닛들이 생성되고 각 유닛마다 다른 공격력을 가지고 있어 공격을 받았을 때의 피해정도가 다르다. 방어기지에서는 가장 피해가 적도록 유닛들을 선택하여 공격을 해야하는데, 각 확률(Rho)과 보상값(Lambda)을 변화시킬 때 최적이 행동을 결정하는 문제이다.

 

오른쪽의 확률과 보상값을 변화시킴에 따라 최적의 행동이 달라짐을 볼 수 있다. 예를 들어 보상값이 적은 유닛일 경우에는 그 유닛이 가까이 있어도 보상값이 큰 다른 유닛을 선택하는 행동을 결정하게 된다.

 

 

 

[참고자료]

    - 논문 Algorithms for Sequential Decision Making, Michael Lederman Littman

List of Articles
제목 글쓴이 날짜 조회 수
알아두면 쓸데있는 신기한 강화학습 깊은바다 2017-08-24 753
알파고를 탄생시킨 강화학습의 비밀 깊은바다 2017-06-25 580
신경망 Q-Learning으로 구현한 오목 게임 깊은바다 2017-03-29 9332
강화학습 Q-Learning과 DQN에 대한 설명 깊은바다 2017-03-27 6103
텐서플로우에서 DQN 강화학습으로 캐치게임 구현 file 깊은바다 2017-03-18 3615
딥 강화학습으로 퐁 게임 학습 file 깊은바다 2017-03-13 1151
딥 강화학습 쉽게 이해하기 [2] 깊은바다 2017-02-28 1351
딥러닝 강화학습으로 둠 게임 구현 깊은바다 2017-02-28 435
강화학습 기반의 지능적인 가상캐릭터 file 깊은바다 2016-03-24 373
강화학습 기반의 자율적인 행동 학습 file 깊은바다 2016-03-24 1305
MDP 기반의 스케줄링 구현 file 깊은바다 2016-03-24 1312
딥마인드의 게임을 학습하는 딥러닝 인공지능 깊은바다 2016-03-21 670