매년 6월 전세계 도시를 순회하며 개최되는 ‘자동화 플래닝 및 스케줄링에 관한 국제 회의(International Conference on Automated Planning and Scheduling)’는 컴퓨터 시스템을 통해 비행기 스케줄링이나 자율 위성들의 작업 조정 같은 계획 문제를 해결하는 솔루션들이 대거 출품되는 행사다.

지난 2015년에는 이스라엘에서 열렸으며 지난해는 영국에서 6월 12일부터 17일까지 개최된 바 있다. 그러나 이들 전시회 등을 통해 소개된 최상의 알고리즘이라 하더라도 매우 단순한 일부 문제를 제외하면 MIT 학생들처럼 문제해결에 능숙한 인간만큼 효과적이지는 않다는 것이 확인된다.

여기에 착안해 MIT의 컴퓨터과학 및 인공지능연구소 연구원들이 인간의 직관력을 활용해 자동화 계획을 향상시키는 프로젝트를 진행하고 있다. 뛰어난 성취 역량을 가진 인간 플래너의 전략을 기계가 읽을 수 있는 형식으로 인코딩함으로써 풀기 어려운 일련의 문제에서 계획 알고리즘의 성능을 10~15% 더 향상시키는 접근법이다. 이 결과물들은 최근 열린 전미 인공지능협회(Association for the Advancement of Artificial Intelligence) 연례회의에서 발표됐다.

인간의 통찰력과 전략을 기계어로 전환

줄리 샤(Julie Shah) MIT 항공우주학과 조교수는 "연구실에서 다른 조사를 하다보면 플래닝 및 최적화 부문에서 진정으로 탁월한 소수의 사람들이 있다는 것을 알게 된다"며 "그들로부터 통찰력과 높은 수준의 전략을 이끌어내 기계에 적용함으로써 대부분의 인간보다는 문제 해결 능력이 뛰어난 알고리즘을 개발하는 것이 우리의 목표"라고 말했다.

이 논문의 첫번째 저자는 항공우주학과 대학원생 조셉 김(Joseph Kim)으로 샤 교수와 이 연구소에서 인턴경험을 한 바 있는 노퍽국립대 대학원생 크리스토퍼 뱅크스(Christopher Banks)와 함께 작업하고 있다.

국제플래닝공모전(International Planning Competition, IPC)에 출품된 알고리즘에는 여러가지 난이도의 관련 문제가 주어진다. 가장 쉬운 문제의 경우 몇 가지 엄격한 제약 조건을 충족하면 된다. 가령 특정 수의 공항, 특정 수의 비행기, 특정 목적지를 가진 각 공항의 일정한 사람들이라는 3가지 조건을 주고 어떤 비행기도 비어있지 않으면서 모든 승객들이 목적지에 도달하는 비행기의 경로를 계획하는 작업이다.

보다 복잡한 문제는 몇몇 유연한 수치 매개 변수를 추가한다. 원래 문제의 제약 조건을 충족시키면서 비행기의 비행 시간과 연료 소비를 최소화하는 일련의 비행 계획을 찾는 것이다. 마지막으로 가장 복잡한 문제는 수치적 문제에 시간적 제약까지 추가한다. 비행기가 특정 시간에 도착하고 출발하는 것을 보장하면서 비행 시간과 연료 소비를 최소화하는 방법을 푸는 것이다.

뛰어난 인간과 비슷한 플래닝 결과물 도출

각 문제에 대해 MIT가 개발한 알고리즘은 계획을 생성하는데 30분이 소요되는 것으로 알려진다. 계획의 품질은 총 비행 시간과 총 연료 소비를 합한 수식과 같은 '비용 함수'에 따라 측정된다.

샤, 김, 뱅크스는 비교를 위해 36명의 MIT 학부생 및 대학원생을 모집해 각기 다른 두 가지 방식으로 문제를 풀도록 했다. 하나는 비행기 경로 설정에 중점을 두었으며 다른 하나는 위성 위치에 초점을 맞췄다. 자동 계획 알고리즘과 마찬가지로 학생들은 각 문제를 해결하는 데 30분이 걸렸다. 샤는 "MIT 학생들을 선택함으로써 우리는 문제 해결에 있어 세계 최고 수준의 전문가를 얻은 셈"이라며 "이는 아마도 나머지 대부분의 인구보다는 더 낫다는 것을 의미하기도 한다"고 말했다.

내용면에서는 MIT 학생들이 자동 계획 알고리즘보다 더 우월했다. 문제 해결을 위해 사용했던 일반적인 전략에 대해 참여 학생들을 인터뷰한 결과 '비행기는 한 번에 각 도시를 방문해야 한다', '각 위성마다 3회 혹은 그 이하로 경로를 찾아야 한다'와 같은 대답까지 포함돼있었다.

내용별로 10~16%의 개선 이뤄져

연구자들은 대다수 학생들의 전략이 '선형 시간 논리'라고 불리는 공식 언어로 설명가능하다는 것을 발견했으며, 이후 문제 규정에 대해 제약 조건을 추가하는데 사용했다. 특히 서로 다른 전략을 구사하다보면 각 전략의 장점들이 상쇄될 가능성도 있기 때문에 경쟁에서 이기는 계획 알고리즘을 사용해 각 학생의 전략을 개별적으로 테스트했다. 결과는 다양했지만 확실히 진전이 있었다. 수치 문제에서 비행 계획 및 위성 위치 확인 문제에 대한 평균 개선은 각각 13%와 16%로 나타났다. 시간적 제약 문제에 있어서는 12%와 10%가 각각 개선됐다.

샤는 "사람이 만든 고차원 전략을 사용했을 때 자동 플래너는 인간이 만든 계획과 비슷한 수준이 됐다"며 “앞으로도 이 같은 접근이 유용할 것”으로 확신했다. 김과 샤는 자연 언어처리 기술을 사용해 시스템을 완전 자동으로 만드는 작업을 진행하고 있으며 인간의 고차원 전략에 대한 자유로운 형식의 묘사를 인간의 개입없이 '선형 시간 논리'로 변환하고 있다.