제약 프로그래밍에 관한 학사 논문
2019년 6월
개요
시뮬레이션에 가능한 사건이 많아질수록 반복해서 평가해야 하는 조건도 늘어난다. 그런데 시뮬레이션이 진행되면서 어떤 조건이 다시는 참이 될 수 없다는 사실이 밝혀진다면, 그 조건의 검사를 안전하게 생략할 수 있지 않을까? 하이브리드 시스템 모델링 언어 HydLa를 대상으로, 변수가 변하는 방향을 이용해 더 이상 검사할 필요가 없는 조건을 제거하는 방법을 설계하고 구현했다.
평가 모델에서는 시뮬레이션 결과를 바꾸지 않으면서 실행 시간을 기존 알고리즘의 약 절반으로 줄였다. 문제의 구조를 활용해 검토할 가능성의 수를 줄인 결과다.
이 연구에서 익힌 제약 프로그래밍의 관점은 지금 포트폴리오의 프로젝트들에도 이어진다. 모든 결과를 직접 지정하기보다 규칙, 우선순위, 경계를 정의하고, 이를 만족하는 해를 도출하는 접근이다.
문제: 가능한 사건이 많아질수록 길어지는 실행 시간
HydLa는 연속적인 변화와 이산적인 사건이 결합된 하이브리드 시스템을 수학적·논리적 제약으로 기술한다. 모든 절차를 하나씩 지정하는 대신, 성립해야 하는 조건을 모델에 선언하면 시뮬레이터가 그 조건을 만족하는 거동을 찾는다.
조건부 규칙이 많은 모델에서는 시뮬레이터가 수많은 후보 조건을 반복해서 검사한다. 더 이상 참이 될 수 없는 조건도 후보 집합에 남아 있다. 모델이 커질수록 이러한 불필요한 검사가 계산량을 늘린다.
모델: 연속적인 변화와 이산적인 사건의 결합
튀는 공은 하이브리드 시스템의 간단한 예다. 공중에 있는 동안 위치와 속도가 연속적으로 변하고, 바닥에 닿으면 튀어 오르는 이산적인 사건이 발생한다. 온도조절기, 자동차, 로봇도 서로 다른 규모에서 이 두 종류의 변화를 함께 가진다.
평가에는 여러 구간으로 나뉜 바닥 위를 수평으로 이동하며 튀는 공의 모델을 사용했다. 각 구간에는 공이 해당 영역에 도달했을 때 튀어 오르게 하는 조건부 규칙이 있다. 구간을 늘리면 더 많은 대상을 표현할 수 있지만, 시뮬레이터가 검사해야 하는 조건도 많아진다.
병목: 조건이 늘면 실행 시간도 증가한다
특정 조건이 충족될 때만 활성화되는 규칙을 가드 제약이라 한다. 평가 모델에서는 공이 바닥에 닿고 수평 위치가 특정 구간 안에 있을 때만 그 구간의 튐 규칙이 활성화된다.
구간 수를 10개에서 200개까지 늘리자 기존 시뮬레이터의 실행 시간은 대략 구간 수의 제곱에 비례해 증가했다. 모델의 규모가 커져 더 많은 대상, 접촉 영역, 가능한 사건을 포함하면 이 문제가 더욱 커질 수 있다.
분석: 실행 시간의 96%는 어디에 쓰였는가
구간이 100개인 모델을 프로파일링한 결과, 전체 실행 시간의 96%가 FindMinTime에 쓰였다. 이 루틴은 모든 후보의 가드 조건을 반복해서 평가해 다음에 일어날 수 있는 가장 이른 사건을 찾는다.
이를 통해 개선할 지점을 좁혔다. FindMinTime에 넘기는 후보를 안전하게 줄이는 것이다. 시뮬레이션 결과를 유지하면서 더 이상 평가할 필요가 없는 가능성만 제외하는 것을 목표로 했다.
접근: 다시 참이 될 수 없는 조건을 제거한다
공이 계단을 튀며 내려가는 장면을 떠올려 보자. 공이 어떤 계단을 지나 계속 앞으로 나아가면, 그 계단은 더 이상 공에 영향을 줄 수 없다. 그림을 보는 사람은 공 뒤에 있는 계단을 곧바로 무시하지만, 원래의 알고리즘은 그 하나하나를 계속 검사하고 있었다.
어려운 부분은 버린 가드가 나중에도 결코 필요하지 않다는 것을 증명하는 일이다. 지금 거짓이라는 이유만으로 제거하면, 그 조건이 다시 참이 될 때 조용히 잘못된 결과를 낳을 수 있다. 그래서 제안 방식은 단조성을 이용한다. 어떤 변수가 일정 시간 구간에서 계속 증가하거나 계속 감소한다고 보장되는지를 따지는 것이다.
변화의 방향이 유지되는 경우
첫 번째 접근은 시뮬레이션 내내 변수가 한 방향으로 변하는 경우에 적용된다. 바닥을 나눈 모델에서 공의 수평 위치는 계속 증가한다. 어떤 구간을 지나면 그 구간의 가드는 다시 참이 될 수 없다. 모델 검사 기법으로 시뮬레이션 전에 이 성질을 확인하면, 실행 중에 더 이상 관련이 없어진 가드를 안전하게 제거할 수 있다.
변화의 방향이 바뀌는 경우
많은 시스템에서 변수는 한 방향으로만 계속 변하지 않는다. 증가하다가 방향을 바꾸어 감소할 수 있다. 논문에서는 이에 대응하는 두 번째 접근을 제안했다. 변화의 방향을 가정하고 그 가정을 어서션으로 감시한다. 방향이 바뀌면 이전 단조 구간에서 제거한 가드를 복원하고 제거 절차를 다시 시작한다. 이 접근은 설계했지만, 이 프로젝트에서 구현하거나 평가하지는 않았다.
결과: 평가 모델의 실행 시간을 약 절반으로 단축
균일 단조성을 이용하는 방법을 구현해 구간별로 나뉜 바닥 모델로 평가했다. 두 알고리즘 모두 구간 수가 늘수록 실행 시간이 증가했지만, 제안 방법은 일관되게 시간이 덜 걸렸다. 곡선 적합 결과, 최고차항의 계수는 1.1463에서 0.6083으로 줄었다. 이 벤치마크의 전체 시뮬레이션 시간은 대략 절반이 되었다.
이 결과는 모든 HydLa 모델이 두 배 빨라진다는 주장이 아니다. 이 방법이 어디에서 도움이 되는지를 보여 줄 뿐이다. 가드가 걸린 대상이 많고 변화의 방향을 증명할 수 있으며, 실행 도중에 가드가 영구히 무관해지는 모델이다.
연구에서 배운 점
이 연구에서는 시스템 거동의 알려진 성질을 이용해 시뮬레이터가 검토해야 할 가능성의 집합을 줄였다. 결과를 보존하면서 탐색 공간을 좁힐 수 있다는 점은 제약 프로그래밍의 강점이다.
구현과 평가는 한 방향으로 계속 변하는 변수를 대상으로 했다. 방향이 바뀌는 경우의 처리는 설계 단계에 머물렀으며 평가가 필요하다. 단조성 이외의 성질도 불필요한 제약을 찾는 데 도움이 될 수 있다.
이 경험은 AI가 해를 탐색할 수 있는 조건과 경계를 설계하려는 현재의 관심으로 이어진다. 복잡한 결과를 다룰 때는 무엇을 계산할지 정하는 일만큼 무엇을 안전하게 무시할 수 있을지 정하는 일도 중요하다.
호리우치 다카후미, 우에다 가즈노리 「Dynamic Reduction of Guarded Constraints for the Hybrid Systems Modeling Language HydLa」 2019년도 일본인공지능학회 전국대회(제33회), 2019년. DOI: 10.11517/pjsai.JSAI2019.0_1E3OS3b02