조합최적화 강화학습(Combinatorial optimization reinforcement learning)

#

지금 연구하는 분야를 설명하자면 멀티로봇시스템을 운용하게 될 때, 진행해야하는 다양한 작업들을 어떻게 효율적으로 로봇에 할당시켜 실행할 것인지를 결정하는 의사결정 알고리즘을 만드는 것이 목표이다.

 

#

좀 간단하게 구체화 하자면 내가 운용할 $N$대의 멀티로봇 개체가 존재하고,

$$(A_1, A_2, A_3, \cdots, A_N)$$

내가 원하는 복합적 미션을 수행하기위한 임의의 작업이 $M$개 주어졌다고 했을 때

$$(T_1, T_2, T_3, \cdots, T_M)$$

각 로봇들을 어떤 작업에, 어떤 순서로 할당해야 수행하고자하는 미션의 performance를 최대화하고 거기에 사용되는 cost를 최소화 할 수 있는지, 최대한 최적화된 의사결정을 하는 것을 의미한다.

 

여기서 작업(task)이란, 단순한 모바일로봇의 방문점으로도 볼 수 있지만 좀 더 높은 단계의 작업으로 생각할 수 도 있는데 예를 들면

$T_1$: 지정된 위치 방문

$T_2$: 매핑

$T_3$: 감시

같은 복합적인 sub task들에 대한 할당으로 하여 각 임무들의 관계를 edge와 weight로 정의한 하나의 그래프 형태로 보고 임무를 수행할 수 도있는 것이다.

 

#

아무튼 이런 문제 formulation을 풀어내려면 이 문제들은 대체로 NP-hard로 알려져 있는데 NP-hard를 간단히 말하면 로봇과 임무의 수가 늘어날 수록 풀어야되는 복잡도가 어마어마하게 커진다. 이게 얼마냐 커지냐면 세상 모든 컴퓨터를 끌어와도 내가 죽을 때까지 못 풀 정도라고 해도 무방하다.

그런 문제를 풀때 대체로 approximation/heuristic을 사용해 푸는데 최근 deep learning을 이용한 접근들이 점점 많아지고 특히 강화학습을 통해 꽤 좋은 성능을 취할 수 있음이 보여졌다.

 

#

아무튼 아래의 발표자료는 나름의 survey를 통해 굵직한 접근들만 모아서 발표한 것이다.

---

Combinatorial optimization and deep reinforcement learning