최적화 문제:
  minimize   f(q_1, q_2, ..., q_n)
  subject to g_j(q_1, ..., q_n) <= 0,   j = 1, ..., m   (부등식 제약)
             h_k(q_1, ..., q_n) = 0,    k = 1, ..., p   (등식 제약)
             q_i in C_free,              i = 1, ..., n   (실현 가능 영역)

여기서:
- q_i = (x_i, y_i, z_i, theta_i, phi_i, psi_i): 객체 i의 위치(3) + 회전(3) = 6 자유도(DOF)
- f: 목적함수 (간섭 수 최소화, 총 이동거리 최소화 등)
- g_j: 부등식 제약 (비중첩, 이격거리, 공간 범위 등)
- h_k: 등식 제약 (연결점 유지, 고정 지점 등)
- C_free: 실현 가능한 구성 공간(free configuration space)

phi-함수 정의:
  Phi(A, B) > 0   : A와 B가 분리됨 (separated)
  Phi(A, B) = 0   : A와 B가 접촉 (touching)
  Phi(A, B) < 0   : A와 B가 중첩됨 (overlapping)

변수(Variables):
  X = {x_1, y_1, z_1, theta_1, ..., x_n, y_n, z_n, theta_n}

도메인(Domains):
  D(x_i) = [x_min, x_max]
  D(theta_i) = {0, pi/2, pi, 3pi/2}  -- 이산 회전 (또는 [0, 2pi) 연속)
  D(r_i) = {route_1, ..., route_R}    -- 경로 후보군

제약조건(Constraints):
  비중첩: for all i != j: Volume(o_i) intersection Volume(o_j) = empty
  포함:   for all i: o_i subset Omega  (건물 공간 내에 포함)
  연결:   for all (i,j) in E_connect: dist(connection_point(o_i), connection_point(o_j)) = 0
  이격:   for all i != j: dist(o_i, o_j) >= d_min(i, j)

x_i + w_i <= x_j + M(1 - delta_ij^1)     ... (i가 j의 x- 방향)
x_j + w_j <= x_i + M(1 - delta_ij^2)     ... (i가 j의 x+ 방향)
y_i + d_i <= y_j + M(1 - delta_ij^3)
y_j + d_j <= y_i + M(1 - delta_ij^4)
z_i + h_i <= z_j + M(1 - delta_ij^5)
z_j + h_j <= z_i + M(1 - delta_ij^6)

delta_ij^1 + delta_ij^2 + ... + delta_ij^6 >= 1

minimize  alpha * sum(||q_i - q_i^0||) + beta * N_clash
subject to
  비중첩 제약 (위의 Big-M 정식화)
  포함 제약: 0 <= x_i, y_i, z_i; x_i + w_i' <= W, ...
  연결 제약: |connection_out(i) - connection_in(j)| = 0, for (i,j) in E
  이동 제약: ||q_i - q_i^0|| <= D_max
  고정 제약: q_i = q_i^0, for i in Fixed

Hard Clash 조건:
  V_A intersection V_B != empty

정량적 측정:
  관통 볼륨: V_overlap = Volume(V_A intersection V_B)
  관통 깊이: d_p = min{ ||v|| : (V_A + v) intersection V_B = empty }  (EPA로 계산)

phi-함수 표현:
  Phi(A, B) < 0  <==>  Hard Clash 존재

허용 공차: 0mm ~ 3mm (실무적 시공 오차 감안)

Soft Clash(A, B, d_min):
  dist(A, B) < d_min  AND  V_A intersection V_B = empty

Minkowski Sum 기반 표현:
  A_expanded = A (+) B_{d_min/2}
  Soft Clash  <==>  A_expanded intersection B_expanded != empty  AND  A intersection B = empty

Clearance Zone(o_i):
  front:  d_front  (접근 방향, 가장 큰 값)
  back:   d_back
  left/right/top/bottom: 각각 다른 값

예시 - 밸브(Valve):
  전면(핸들 방향): 600mm
  후면: 50mm, 좌우: 100mm, 상하: 150mm

V_4D(o_i) = Volume(o_i) x [t_start_i, t_end_i]

4D Clash 조건:
  Volume(o_i) intersection Volume(o_j) != empty
  AND  t_start_i < t_end_j  AND  t_start_j < t_end_i

4가지 유형:
  Type 1: 물리적 4D (임시 구조물 vs 최종 구조물)
  Type 2: 작업 영역 4D (동일 공간 동시 작업 불가)
  Type 3: 접근 경로 4D (자재 반입 경로 충돌)
  Type 4: 순서 의존 4D (선행 작업 미완료)

+--------------------------------------------------+
| 4D Clash (시공 순서 포함)                          |
|  +--------------------------------------------+  |
|  | Clearance Clash (비등방 이격거리)             |  |
|  |  +--------------------------------------+  |  |
|  |  | Soft Clash (등방 이격거리)              |  |  |
|  |  |  +------------------------------+    |  |  |
|  |  |  | Hard Clash (물리적 관통)       |    |  |  |
|  |  |  +------------------------------+    |  |  |
|  |  +--------------------------------------+  |  |
|  +--------------------------------------------+  |
+--------------------------------------------------+

C_obs = O (+) (-R)   (O: 장애물, R: 로봇/객체)

C = C_free  union  C_obs
C_free = { q in C : Robot(q) intersection Obstacles = empty }

n개 객체, 각 6DOF: 전체 C-Space = 6n 차원

Sampling-based Planning:
  PRM: C_free에서 랜덤 샘플링 후 그래프 구성
  RRT: 트리를 점진적으로 확장하여 목표에 도달
  RRT*: 점근적 최적성 보장이 추가된 RRT

조합 최적화 분류 체계:
  Assignment Problems (QAP - 시설 배치)
  Packing Problems (Bin Packing 1D/2D/3D, Strip Packing, Knapsack)
  Cutting Problems (Cutting Stock, Guillotine)
  Routing Problems (VRP, Pipe Routing)
  Scheduling Problems (Job-shop, 4D 시공 순서)

간섭 수 최소화:     f_1(q) = sum_{i<j} max(0, -Phi(o_i(q_i), o_j(q_j)))
총 이동거리 최소화: f_2(q) = sum_i ||q_i - q_i^0||_p
관통 볼륨 최소화:   f_3(q) = sum_{i<j} Volume(V_i intersection V_j)
최대 이동거리 최소화(Min-Max): f_4(q) = max_i ||q_i - q_i^0||

minimize  F(q) = (f_1, f_2, ..., f_K)

Pareto 최적성:
  q^a dominates q^b  <==>
    f_k(q^a) <= f_k(q^b) for all k  AND  exists k: f_k(q^a) < f_k(q^b)

+-----------------------------------------------------------------------+
| 제약 유형          | 수학적 형태             | 선형화 가능 여부       |
|--------------------|-------------------------|------------------------|
| 비중첩             | disjunctive inequality  | Big-M으로 MIP 가능     |
| 이격거리           | dist >= d_min           | Big-M 확장으로 가능    |
| 포함               | linear inequalities     | 직접 선형              |
| 연결 유지          | equality constraint     | 직접 선형              |
| 구배 유지          | linear inequality       | 직접 선형              |
| 유지보수 공간      | directional clearance   | Big-M 확장 (복잡)      |
| 시간 분리 (4D)     | disjunctive + temporal  | Big-M + 시간 변수      |
+-----------------------------------------------------------------------+

이산 해 공간 (G^3 그리드, 6 직교 회전):
  단일 객체: 6 * G^3
  n개 객체:  (6 * G^3)^n

  G=100, n=50:  ~10^339
  G=100, n=100: ~10^678  (관측 가능한 우주의 원자 수 ~10^80 압도)

연속 해 공간 (6 DOF):
  n=50:  300차원
  n=100: 600차원
  n=500: 3000차원

3-Partition Problem (NP-Hard)  -->  1D-BPP  -->  2D-BPP  -->  3D-BPP  -->  3D Object Rearrangement

function AABB_Intersect(a, b):
    if a.maxX < b.minX or a.minX > b.maxX: return false
    if a.maxY < b.minY or a.minY > b.maxY: return false
    if a.maxZ < b.minZ or a.minZ > b.maxZ: return false
    return true

function SpatialHash_BroadPhase(objects, cellSize):
    hashTable = {}
    for obj in objects:
        cells = GetOccupiedCells(obj.aabb, cellSize)
        for cell in cells:
            hashKey = Hash(cell.x, cell.y, cell.z)
            hashTable[hashKey].append(obj)
    // 같은 버킷 내 쌍 검사
    ...

function Hash(x, y, z):
    return (x * 92837111 ^ y * 689287499 ^ z * 283923481) % TABLE_SIZE

function OBB_Intersect(A, B):
    axes = [A.axisX, A.axisY, A.axisZ, B.axisX, B.axisY, B.axisZ]
    for i in A.axes:
        for j in B.axes:
            axes.append(Normalize(CrossProduct(i, j)))
    for axis in axes:
        if not Overlap(ProjectOBB(A, axis), ProjectOBB(B, axis)):
            return false   // 분리축 발견
    return true

function GJK(shapeA, shapeB):
    d = initial_direction
    simplex = [Support(A-B, d)]
    d = -simplex[0]
    loop:
        point = Support(A-B, d)
        if Dot(point, d) < 0: return NO_COLLISION
        simplex.add(point)
        if DoSimplex(simplex, d): return COLLISION

function SAT_with_MTV(A, B):
    min_overlap = INFINITY
    for axis in CandidateAxes(A, B):
        overlap = ComputeOverlap(Project(A, axis), Project(B, axis))
        if overlap <= 0: return NO_COLLISION, null
        if overlap < min_overlap:
            min_overlap = overlap
            mtv_axis = axis
    return COLLISION, mtv_axis * min_overlap

function BVH_Query(nodeA, nodeB):
    if not Intersect(nodeA.bv, nodeB.bv): return
    if nodeA.isLeaf and nodeB.isLeaf:
        NarrowPhaseTest(nodeA.obj, nodeB.obj)
        return
    if nodeA.volume > nodeB.volume:
        BVH_Query(nodeA.left, nodeB)
        BVH_Query(nodeA.right, nodeB)
    else:
        BVH_Query(nodeA, nodeB.left)
        BVH_Query(nodeA, nodeB.right)

function EPA(simplex, shapeA, shapeB):
    polytope = InitPolytope(simplex)
    loop:
        closestFace = FindClosestFace(polytope)
        support = Support(A-B, closestFace.normal)
        newDist = Dot(support, closestFace.normal)
        if (newDist - closestFace.distance) < TOLERANCE:
            return (closestFace.normal, closestFace.distance)
        RemoveFacingFaces(polytope, support)
        FillHole(polytope, support)

function ResolvePenetration(objA, objB, mtv):
    // 방법 1: 한쪽만 이동
    objA.position += mtv
    // 방법 2: 질량 비례 분배
    totalMass = objA.mass + objB.mass
    objA.position += mtv * (objB.mass / totalMass)
    objB.position -= mtv * (objA.mass / totalMass)
    // 방법 3: 우선순위 기반 (BIM)
    if objA.priority < objB.priority:
        objA.position += mtv
    else:
        objB.position -= mtv

function AStar_3D_MEP(start, goal, voxelGrid):
    openSet = PriorityQueue()
    openSet.push(start, f=0)
    while openSet is not empty:
        current = openSet.pop()
        if current == goal: return ReconstructPath(cameFrom, current)
        for neighbor in OrthogonalNeighbors(current):  // +X,-X,+Y,-Y,+Z,-Z
            if voxelGrid[neighbor] == BLOCKED: continue
            turnPenalty = TURN_COST if direction_changed else 0
            heightPenalty = HEIGHT_COST if neighbor.z != current.z else 0
            tentative_g = gScore[current] + 1 + turnPenalty + heightPenalty
            ...

function RRT(start, goal, obstacles, maxIter):
    tree = Tree(root=start)
    for i in range(maxIter):
        qRand = goal if random() < GOAL_BIAS else RandomSample()
        qNearest = tree.NearestNeighbor(qRand)
        qNew = Steer(qNearest, qRand, stepSize)
        if CollisionFree(qNearest, qNew, obstacles):
            tree.AddNode(qNew, parent=qNearest)
            if Distance(qNew, goal) < threshold:
                return ExtractPath(tree, qNew)
    return FAILURE

function SA_ClashResolution(objects, clashes, T_init, T_min, alpha):
    state = CurrentPositions(objects)
    bestState = state
    T = T_init
    while T > T_min:
        neighbor = Perturb(state)
        deltaCost = Cost(neighbor) - Cost(state)
        if deltaCost < 0:
            state = neighbor
        else:
            if random() < exp(-deltaCost / T):
                state = neighbor
        if Cost(state) < Cost(bestState): bestState = state
        T = T * alpha
    return bestState

function NSGA2_ClashResolution(population, maxGen):
    for gen in range(maxGen):
        fronts = FastNonDominatedSort(population)
        for front in fronts: CrowdingDistanceAssignment(front)
        parents = TournamentSelection(population, fronts)
        offspring = Crossover(parents) + Mutation(parents)
        offspring = FilterFeasible(offspring, constraints)
        combined = population + offspring
        population = SelectByRankAndCrowding(combined, popSize)
    return ParetoFront(population)

function ConstraintPropagation(objects, constraints):
    queue = AllConstraints(constraints)
    while queue is not empty:
        constraint = queue.dequeue()
        if Revise(objA, objB, constraint):
            if Domain(objA) is empty: return FAILURE
            for c in ConstraintsInvolving(objA) - {constraint}:
                queue.enqueue(c)
    return SUCCESS

우선순위 1 (하드): 구조체 관통 불가, 공간 경계, 연결 유지
우선순위 2 (규범): 이격거리, 지지 간격, 경사 기울기
우선순위 3 (소프트): 이동 최소화, 꺾임 최소화, 병렬 정렬

매 물리 프레임:
1. Broad Phase (SAP / BVH) -> 잠재적 충돌 쌍
2. Narrow Phase (GJK + EPA / SAT) -> 접촉 매니폴드
3. Constraint Solver (Sequential Impulse / TGS) -> 접촉+조인트 동시 해결
4. Integration -> 속도/위치 갱신

function SequentialImpulseSolver(contacts, joints, iterations):
    for contact in contacts: ApplyAccumulatedImpulse(contact)  // Warm Starting
    for iter in range(iterations):
        for contact in contacts:
            relVel = GetRelativeVelocity(contact)
            bias = -BETA * max(0, penetration - SLOP) / dt + RESTITUTION * normalVel
            lambda = -(normalVel + bias) / effectiveMass
            // 누적 충격량 클램핑
            contact.accumulatedLambda = max(0, oldLambda + lambda)
            // 충격량 적용
            ...

delta_lambda = (-C(x) - alpha_tilde * lambda) / (grad_C * M_inv * grad_C^T + alpha_tilde)
delta_x = M_inv * grad_C^T * delta_lambda
alpha_tilde = alpha / (dt^2)   // alpha=0 -> 완전 강체

Phase 1: Hard Clash (구조체 관통, 대구경 교차)
Phase 2: Soft Clash (이격거리 미달, 유지보수 공간)
Phase 3: 4D Clash (시공 순서 간섭)
Phase 4: 최적화 (병렬 정렬, 미관, 지지대)

Rule 1 (배관-보): 소구경이면 슬리브, 아니면 보 하부 우회
Rule 2 (배관-배관): 소구경을 수직 이동
Rule 3 (덕트-배관): 배관을 이동 (덕트 단면적이 커서 이동 비용 높음)
Rule 4 (케이블트레이): 항상 케이블트레이를 이동 (가장 유연)
Rule 5 (경사 배관): 경사 유지하며 전체 라인 시프트

변수: V_i = (x_i, y_i, z_i, rx_i, ry_i, rz_i) -- 6-DOF
도메인: 그리드 포인트 또는 연속 구간
제약: C_no_clash, C_clearance, C_boundary, C_connectivity, C_priority

function HybridResolution(allClashes):
    clusters = ClusterClashes(allClashes, proximityThreshold)
    for cluster in clusters:
        if cluster.size <= SMALL_THRESHOLD:
            IncrementalResolve(cluster)
        else:
            OptimizationResolve(cluster)
    newClashes = DetectNewClashes()
    if newClashes: HybridResolution(newClashes)

시나리오: 1,000건의 MEP 간섭 해결

[휴리스틱] 규칙 ~2ms + 이동벡터 ~5ms + A* ~50ms = 총 ~57초
[AI 추론]  모델로딩 ~2초 + 특징추출 ~10ms + 추론 ~20ms + 후처리 ~5ms = 총 ~37초
[AI 학습포함] 데이터 수시간 + 학습 수시간~수일 + 추론 ~37초

[간섭] -> [휴리스틱 초기해] -> [AI 개선(GNN/RL/Diffusion)] -> [검증]

[자동 해결안 제시] -> [사용자 수락/수정/거부] -> [피드백 기록] -> [모델 업데이트]

[현장 데이터]  ->  [Edge Computing]  ->  [Digital Twin Platform]
   드론               실시간 처리            Omniverse / Azure DT
   LiDAR              포인트클라우드          물리 시뮬레이션
   IoT                변환/정합              간섭 검출 + 해결
                                            -> [Feedback to Design]

┌─────────────────────────────────────────────────────────────────┐
│                    3D 간섭 자동 해결 시스템                        │
├─────────────────────────────────────────────────────────────────┤
│  [1. BIM Model Parsing]  IFC -> IfcOpenShell -> Internal Model  │
│  [2. Clash Detection]    AABB Broadphase -> FCL Narrowphase     │
│  [3. Classification]     ML Classify -> Priority Rank -> Select │
│  [4. Resolution Engine]  Heuristic | AI/ML | Hybrid Selector    │
│  [5. Validation]         Re-clash Check -> Rule Verify -> Score │
│  [6. Output]             Modified IFC | BCF Report | 3D View    │
└─────────────────────────────────────────────────────────────────┘

Phase 1 (0-6개월): 규칙 기반 MVP
  - FCL 기반 간섭 검출/분리 벡터 계산
  - OMPL 기반 배관 경로 탐색
  - IfcOpenShell 기반 BIM 파싱
  - 규칙 기반 우선순위 해결
  - 기본 시각화 (Unity)

Phase 2 (6-12개월): AI 분류기 추가
  - ML 기반 간섭 유형 분류기 (XGBoost/GNN)
  - NSGA-II 기반 다목적 최적화
  - ACO + A* 하이브리드 MEP 라우팅
  - 사용자 피드백 수집 시스템
  - 온라인 학습 파이프라인

Phase 3 (12-18개월): AI 개선 엔진
  - GNN 기반 전역 최적화
  - Diffusion Model 기반 배치 개선
  - 강화학습 기반 시퀀싱
  - 메타 학습 프레임워크
  - RL 환경 구축 (Unity ML-Agents 또는 Gymnasium)

Phase 4 (18-24개월): 완전 자율 시스템
  - LLM 기반 자연어 해결안 설명
  - 디지털 트윈 실시간 통합
  - 자율 건설 로봇 연계
  - 다중 에이전트 RL로 전체 MEP 최적화
  - 멀티 프로젝트 전이 학습

[입력: BIM 모델 + 규칙 세트]
    -> [1. Spatial Indexing] Octree/BVH
    -> [2. Broad Phase] AABB + Sweep-and-Prune
    -> [3. Narrow Phase] GJK + EPA
    -> [4. 간섭 분류 및 우선순위화] Hard/Soft 분류, 클러스터링
    -> [5. 해결 전략 선택] 규칙 1차 -> 실패 시 최적화
    -> [6-A. 이동 기반] MTV + 우선순위 + 제약 전파
       [6-B. 경로 재탐색] A* 3D Grid
    -> [7. 검증] 새 간섭 발생? Yes -> 5단계 복귀
    -> [8. 출력: 수정된 BIM 모델]