Mixed-Integer Programming

다른 이름: MIP, MILP, MIQP, MICP
카테고리: Planning & manipulation › Trajectory optimisation
태그: optimization, integer-programming, motion-planning, task-allocation, hybrid-systems

일부 변수가 정수 값, 흔히 0 또는 1을 가져야 하는 최적화로, 하나의 문제 안에서 이산적 선택과 연속적인 양을 결합할 수 있게 한다.

정의

혼합 정수 계획법(mixed-integer programming, MIP)은 연속 변수와 정수로 제한된 변수의 혼합에 대한 최적화이며, 정수 변수는 대개 0 또는 1의 값을 가지는 이진 변수다. 이진 변수는 이산적 결정을 인코딩한다. 경로가 어느 영역을 지나는지, 다음에 어느 발이 땅에 닿는지, 접촉이 활성 상태인지, 어느 로봇이 어느 작업을 맡는지 같은 것이다. 연속 변수는 위치, 속도, 힘 같은 나머지를 담는다. 흔한 부류는 나머지 문제의 형태에 따라 이름이 붙는다. 혼합 정수 선형 계획(MILP), 혼합 정수 이차 계획(MIQP), 그리고 더 일반적으로 혼합 정수 볼록 계획(MICP)이다.

이 문제들은 일반적으로 NP-난해하지만, 현대 솔버는 많은 실제 사례를 잘 처리한다. 이들은 분기 한정법(branch and bound)을 사용한다. 정수 요건을 뺀 연속 완화 문제를 풀고, 분수 값으로 나온 변수 하나를 골라 그 변수를 내림 또는 올림하도록 강제하는 두 하위 문제로 나누며, 완화 값이 이미 지금까지 찾은 최선의 정수 해보다 나쁜 가지는 잘라 낸다. 절단 평면이 그 과정에서 완화를 조인다. Gurobi와 CPLEX 같은 상용 솔버와 SCIP, HiGHS, CBC 같은 오픈소스 솔버가 이 방법들을 구현한다.

문제를 어떻게 쓰는지는 어떤 솔버를 쓰는지만큼 중요하다. 논리 조건은 흔히 big-M 제약(big-M constraints)으로 인코딩되는데, 이는 이진 변수와 큰 상수로 제약을 켜거나 끈다. 상수가 너무 크면 완화가 약해지고 수치적 문제가 생긴다. 완화가 타이트한 정식화는 훨씬 빨리 풀리며, 볼록 집합 그래프 같은 구조화된 접근법이 완화가 실제 문제에 가깝도록 설계되는 이유 중 하나가 이것이다.

중요한 이유

많은 로봇 계획 문제는 부분적으로 이산적이다. 장애물의 왼쪽으로 갈지 오른쪽으로 갈지, 접촉 순서를 고르는 것, 작업을 배정하는 것 등이다. 혼합 정수 계획법은 수작업 휴리스틱이나 샘플링에 의존하는 대신, 하나의 최적화 안에서 이런 선택을 정확하게 다루며, 흔히 답이 최적에서 얼마나 떨어져 있는지에 대한 경계도 함께 준다.

주요 응용

다리 로봇을 위한 발 디딤 및 접촉 순서 계획
드론과 로봇 팔을 위한 볼록 영역을 지나는 궤적 계획
로봇 군단의 작업 배정과 스케줄링
이산 모드를 가진 하이브리드 모델 예측 제어
이산적 행동 선택을 포함한 작업 및 모션 계획

실제 사례

징검돌을 건너는 휴머노이드의 발 디딤을 계획하는 팀은 각 돌의 디딜 수 있는 표면을 볼록 다각형으로 나타낸다. 앞으로의 각 걸음마다 발이 어느 다각형에 착지할지 선택하는 이진 변수를 추가하는데, 선택된 다각형에 대해서만 활성화되는 제약을 두고, 발 위치를 위한 연속 변수와 보폭 및 회전 한계를 더한다. 비용은 목표를 향한 진전에 보상을 주고 어색한 걸음에 페널티를 준다. 혼합 정수 솔버는 보통 재계획용으로 정한 시간 제한 안에 걸음 순서를 반환하며, 찾은 최선의 해와 최선의 경계 사이의 간극도 함께 반환한다. 풀이 시간이 너무 길면 팀은 한 번에 계획하는 걸음 수를 줄이거나, big-M 값을 조이거나, 이전 계획으로부터 웜 스타트한다.

흔한 오해

혼합 정수 계획은 로보틱스에는 항상 너무 느리다 — 작고 잘 정식화된 문제는 온라인 재계획에 충분할 만큼 빨리 풀릴 수 있다
연속 완화를 반올림하면 최적 정수 해가 나온다 — 완화가 타이트하지 않으면 반올림한 해는 실행 불가능하거나 최적에서 멀 수 있다
big-M 제약에서는 M에 어떤 큰 값을 써도 된다 — 지나치게 큰 값은 완화를 약하게 하고 수치적 어려움을 일으킨다
시간 제한에서 멈춘 솔버는 실패한 것이다 — 보통 지금까지의 최선의 해와, 그 해가 얼마나 좋은지를 알려 주는 최적성 간극을 반환한다

알아야 할 사람

모션 및 발 디딤 계획 엔지니어
군단 스케줄링 및 작업 할당 개발자
최적화 기반 제어 연구자
최적화를 공부하는 로보틱스 학생

동영상

Mixed Integer Linear Programming (MILP) Tutorial: APMonitor.com

위키백과

정수 계획법

Open Source Robotics