MDCA

문제 정의

k 개의 드론이 각각 $N_1,N_2,\cdots,N_k$ 개의 경로점들을 따라 이동할 때, 각각의 경로점 간 간선의 길이 (경로점들의 위치) $d^{(i)}_1,d^{(i)}_2,\cdots, d^{(i)}_N$ for $i=1\sim k$가 주어졌을 때,

드론들의 경로가 서로 겹치는 구간, 즉 충돌 가능 구간에선 충돌이 일어나지 않도록 그 구간에서의 속도를 조절하도록 한다.

위와 같이 충돌을 하지 않으면서, 최종 경로점들에 최단 시간에 도달하기 위한 각 구간에서의 속도 $V^{(i)}_1,V^{(i)}_2,\cdots V^{(i)}_N for $i=1\sim k$ 를 구하여라.

변수 정의

구하고자 하는 값이 속도인 이유로 속도 V를 변수로 두게 되면, 시간은 $d^{(i)}_j / V^{(i)}_j$ 로, V에 대한 비선형적인 관계를 가지기 때문에 문제를 풀이하기 어려워진다. 따라서 변수를 시간 t로 정의하고자 한다.

목적 함수 정의

최단 시간 경로이므로, 총 소요 시간의 합이 목적 함수가 된다.

$$ \text{minimize} \sum_{i=1}^{k}T_i $$

구속 조건 정의

1. 속도 구속조건

드론은 최대 속력 $V_{max}$와 최소 속력 $V_{min}$ 의 구속조건을 가진다.

$$ V_{min}\leq{d^{(i)}j\over (t^{(i)}{j+1} - t^{(i)}j)}\leq V{max}\Leftrightarrow {d^{(i)}j\over V{max}}\leq t^{(i)}_{j+1}-t^{(i)}_j\leq {d^{(i)}j\over V{min}} $$

위 구속조건은 convex한 구속조건에 해당한다.