당신은 신비롭고 끊임없이 변하는 섬의 지도를 그리려 한다고 상상해 보십시오. 전체 모습을 한 번에 볼 수는 없기에, 당신은 탐사를 위해 작고 빠른 작은 배들을 파견합니다. 각 배는 해안의 특정 지점에서 출발하여 정해진 시간 동안 조류를 따라 이동합니다. 배들이 멈추면, 당신은 그 최종 위치를 지도에 표시합니다. 목표는 무엇일까요? 점들을 연결하여 섬의 전체 윤곽을 완벽하게 그려내는 것입니다. 이것이 바로 로봇 공학과 자율주в차에서 매우 중요한 도구인 **도달 가능성 분석(reachability analysis)**의 핵심입니다. 이는 "내가 여기서 시작한다면, 결과적으로 어디에 도달할 수 있는가?"라는 질문에 답합니다. 만약 로봇이 벽에 부딪히지 않을 수 있다고 생각했지만, 지도가 잘못되어 실제로 벽에 도달할 수 있다면 그것은 재앙입니다.

오랫동안 과학자들은 복잡한 수학 방정식을 사용하여 이러한 지도를 그리려 노력해 왔으며, 이 방정식들은 경직된 격자(grid)처럼 작동했습니다. 하지만 세상이 더 복잡해짐에 따라(예를 들어, 로봇이 많은 움직이는 관절을 갖거나, 자율주행차가 교통, 날씨, 보행자를 고려해야 하는 경우), 이 격자 방식은 너무 느리고 무거워져 사용할 수 없게 되었습니다. 그래서 엔지니어들은 "배 함대" 방식을 도입했습니다. 즉, 단순히 많은 시작점을 샘플링하고, 시뮬레이션을 실행한 뒤, 그들이 어디에 착륙하는지 확인하는 것입니다. 이 방식은 빠르고 유연하며 거의 모든 시스템에 적용 가능합니다. 하지만 함정이 있습니다. 만약 배를 몇 척만 보낸다면, 절벽 뒤에 숨겨진 작고 위험한 만(cove)을 놓칠 수도 있다는 것입니다. 과거의 수학은 "우리가 수역의 99%를 커버했다!"라고 말할 수 있지만, 그 작은 치명적인 만을 완전히 놓칠 수 있습니다. 과학자들의 큰 질문은 이것이었습니다. "섬의 모양이 아무리 기이하거나 조류가 아무리 강하더라도, 우리가 어떤 부분도 놓치지 않았음을 보장하기 위해 실제로 얼마나 많은 배가 필요한가?"

존스 홉킨스 대학교와 워싱턴 대학교 세인트루이스 캠퍼스의 연구진이 작성한 이 논문은 바로 그 문제에 대해 깊이 파고듭니다. 그들은 도달 가능 집합(섬)을 단순한 점들의 집합이 아니라, 시스템의 역학(dynamics)에 의해 늘어나고 뒤틀리는 기하학적 형상으로 취급합니다. 그들은 진정한 정확도를 가진 지도를 얻기 위해서는 두 가지를 알아야 한다는 것을 발견했습니다. 시작 지점이 "건강해야" 하고(무한히 얇은 바늘 같은 돌출부가 없어야 함), 조류가 예측 가능해야 합니다(너무 격렬하게 물체를 찢거나 벌려놓아서는 안 됨).

저자들은 만약 이러한 조건들이 충족된다면, 단순한 "우리가 대부분의 면적을 커버했다"라는 보장을 엄격한 "우리는 모든 가장자리로부터 아주 미세한 거리 안에 있다"라는 보장으로 바꿀 수 있다는 것을 발견했습니다. 그러나 그들은 또한 다소 냉혹한 진실을 증명해 냈습니다: 샘플링하는 양은 시스템이 복잡해짐에 따라 폭발적으로 증가합니다. 구체적으로, 필요한 샘플의 수는 시스템의 차원(움직이는 부품의 수)과 관찰 시간(time horizon)에 따라 수학적으로 피할 수 없는 방식으로 증가합니다. 그들은 어떤 영리한 기술이나 더 똑똑한 샘별링 방법도 이 "차원의 저주"를 피할 수 없음을 보여주었습니다.

이를 테스트하기 위해, 그들은 단순한 2D 시스템과 여러 개의 관절을 가진 복잡한 로봇 팔에 대해 실험을 수행했습니다. 그들은 "균등 샘플링(uniform sampling, 무작위로 배를 보내는 것)"과 "적대적 샘플링(adversarial sampling, 까다롭고 도달하기 어려운 지점을 찾아내려는 더 똑똑한 방법)"을 비교했습니다. 결과는 명확했습니다: 더 똑똑한 방법이 더 나은 성과를 냈고 오차를 줄였지만, 근본적인 법칙을 바꿀 수는 없었습니다. 로봇 팔이 더 복잡해질수록(더 많은 관절), 오차를 낮게 유지하기 위해 필요한 샘플의 수는 여전히 천문학적으로 치솟았습니다. 이 논문은 우리가 더 똑똑한 샘플링을 통해 지도를 개선할 수는 있지만, 수학을 속일 수는 없다는 결론을 내립니다. 고차원의 복잡한 세상에서 완벽한 안전 보장을 얻는 것은 데이터 수집 측면에서 엄청난 비용이 듭니다.

핵심 연구 결과

이 논문은 샘플링 기반 도달 가능성(sampling-based reachability) 문제를 다룹니다. 간단히 말해, 이는 어떤 시스템(로봇이나 자동차 등)이 주어진 시작 위치들을 바탕으로 일정 시간이 지난 후 도달할 수 있는 모든 가능한 장소를 파악하는 것에 관한 것입니다. 불가능한 방정식을 푸는 대신, 우리는 많은 시작점을 시뮬레이션하고 그들이 어디에 도달하는지 확인합니다.

주요 발견:
저자들은 두 가지 특정 조건이 충족될 때만 "확률" 보장(예: "우리는 면적의 1% 미만을 놓쳤다")을 엄격한 "기하학적" 보장(예: "우리는 모든 가장자리로부터 1mm 이내에 있다")으로 전환할 수 있음을 증명했습니다.

1. 시작 형상이 "건강함": 초기 집합은 "양의 도달 범위(positive reach)"라는 특성을 가져야 합니다. 쉬운 말로, 이 형상은 무한히 얇은 가시나 날카로운 안쪽 컵 모양의 틈을 가져서는 안 됩니다. 모든 곳에서 충분히 "두꺼워야" 합니다.
2. 조류가 예측 가능함: 시스템의 움직임(역학)은 "립시츠 연속(Lipschitz continuous)"이어야 합니다. 이는 시스템이 물체를 너무 격렬하게 늘리거나 찢어놓지 않는다는 뜻의 전문 용어입니다. 시작 지점의 아주 작은 변화가 끝 지점의 거대하고 예측 불가능한 도약으로 이어진다면, 수학은 무너집니다.

이러한 조건이 충족되면, 논문은 필요한 샘플 수($N$)에 대한 공식을 제공합니다. 이 공식은 샘플 수가 차원(시스템이 얼마나 복잡한지)과 시간 지평에 따라 지수적으로 증가함을 보여줍니다.

그들이 배제한 것:
이 논문은 우리가 샘플링을 하는 위치를 더 똑똑하게 결정함으로써 샘플링 문제를 쉽게 "해결"할 수 있다는 생각에 명시적으로 반박합니다.

• 마법의 탄환은 없다: 그들은 "미니맥스 하한(minimax lower bound)"을 증명했는데, 이는 어떤 추정기(아무리 똑똑하더라도)도 샘플 복잡도의 지수적 증가를 피할 수 없다는 수학적 증명입니다.
• 적대적 샘플링의 한계: 실험에서 그들은 "적대적" 샘플링 방법(가장 도달하기 어려운 지점을 목표로 삼는 방법)을 사용했습니다. 이 방법은 결과를 개선했습니다(동일한 샘플 수에 대해 지도를 더 정확하게 만들었습니다). 하지만 이 방법은 근본적인 척도 법칙을 바꾸지는 못했습니다. 즉, 시스템이 복잡해질수록 오차는 여전히 악화되었으며, 단지 조금 더 나은 속도로 악화될 뿐이었습니다. "차원의 저주"는 방법론의 문제가 아니라 본질적인 문제입니다.

얼마나 확신하는가?
저자들은 자신들의 이론적 결과에 매우 확신하고 있는데, 그 이유는 이를 수학적으로 증명했기 때문입니다. 그들은 충분한 샘플이 있으면 가능하다는 것을 보여주는 상한(upper bound)과, 더 적은 샘플로는 불가능하다는 것을 보여주는 하한(lower bound)을 모두 도출했습니다. 이 두 경계가 만나기 때문에, 그들은 가능한 것의 정확한 한계를 찾아낸 것입니다.

실용적인 측면에서, 그들은 다음을 통해 이러한 아이디어를 시뮬레이션했습니다:

1. 비선형 역학을 가진 2D 시스템 (수학이 까다로워지는 경우).
2. 2, 3, 4개의 링크를 가진 로봇 팔 (고차원을 시뮬레이션하는 경우).

시뮬레이션은 그들의 이론을 확인해주었습니다: 샘플을 더 많이 추가할수록 오차는 감소했지만, 로봇 팔이 복잡해질수록 개선 속도는 급격히 느려졌습니다. "적대적" 방법이 도움이 되었지만, 지수적인 벽을 깨뜨릴 수는 없었습니다.

비유를 통한 이야기

당신이 끊임없이 늘어나고 뒤틀리는 거대한 투명 벽에 페인트를 칠하려고 한다고 상상해 보십시오. 당신에게는 페인트 양동이와 스프레이 건이 있습니다. 벽이 보이지 않기 때문에 당신은 어디에 뿌릴지 추측해야 합니다.

과거의 방식 (확률): 당신은 무작위로 1,0로 점을 뿌립니다. 그리고 "벽 표면적의 99%를 덮었다!"라고 말합니다. 하지만 잠깐, 만약 벽에 머리카락처럼 가느다란 틈이 있다면 어떨까요? 만약 로봇이 그 틈을 지나가려 한다면, 로봇은 낭떠러지로 떨어질 것입니다. "99%의 커버리지"는 당신을 구해주지 못했습니다.

새로운 방식 (기하학): 당신은 모든 지점이 페인트 점으로부터 머리카락 한 올의 너비 안에 있도록 보장하고 싶습니다. 논문은 이렇게 말합니다. "좋습니다, 할 수 있습니다. 하지만 벽이 무한히 얇은 실로 만들어져 있지 않고(양의 도달 범위), 늘어나는 정도가 너무 미친 듯이 격렬하지 않다면(립시츠) 말이죠."

함정 (저주): 논문은 만약 당신의 벽이 10차원 공간(예: 10개의 관절을 가진 로봇)에 있다면, 단순히 페인트를 10배 더 많이 써야 하는 것이 아니라고 증명합니다. $10^{10}$배 더 많은 페인트가 필요합니다. 이것은 폭발적인 증가입니다.

"똑똑한" 스프레이 건 (적대적 샘플링): 당신은 틈과 늘어나는 부분을 집중적으로 겨냥하는 똑똑한 총을 사용하려고 합니다. 논문은 이 똑똑한 총이 훌륭하다고 말합니다. 이 총은 무작위 총보다 틈을 더 잘 칠합니다. 하지만, 이 총도 폭발을 막을 수는 없습니다. 벽의 복잡성이 두 배가 되면, 여전히 엄청난 지수적 양의 추가 페인트가 필요합니다. 똑똑한 총은 그 "엄청난" 숫자를 아주 조금 덜 엄청나게 만들어줄 뿐, 그 숫자를 작게 만들지는 못합니다.

이것이 왜 중요한가

이 연구는 로봇 공학과 AI 안전 분야에 대한 현실적인 점검입니다. 이는 샘플링 방식이 강력하고 필수적이지만, 우리가 단순히 "샘플링을 많이 하는 것"만으로 안전 보장 문제를 해결할 수는 없다는 것을 알려줍니다. 만약 우리가 100개의 관절을 가진 로봇이 충돌하지 않을 것임을 인증하고 싶다면, 필요한 데이터의 양이 엄청나다는 사실을 받아들여야 합니다.

이 논문은 앞으로의 연구가 단순히 더 많은 샘플을 문제에 던지는 대신, "물리 정보 기반(physics-informed)"의 기술들—즉, 세상이 어떻게 작동하는지에 대한 지식(예: 에너지 보존 법칙)을 사용하여 수학을 약간 속이는 방법—을 사용해야 할 수도 있음을 시사합니다. 하지만 현재로서는, 이 논문이 명확한 한계를 설정하고 있습니다. 기하학과 역학이 안전의 비용을 결정하며, 그 비용은 매우 높습니다.