Multi-Objective Kinodynamic Motion Planning with Asymptotic Pareto Optimality

로봇에게 미로를 탐색하도록 프로그래밍하는 상황을 상상해 보십시오. 과거의 엔지니어들은 로봇에게 단 하나의 목표만을 주었습니다: "최대한 빨리 출구에 도달하라." 로봇은 다른 모든 것은 무시한 채 최단 경로를 계산할 것입니다. 하지만 현실 세계는 복잡합니다. 자율주행 자동차는 단순히 빠르기만을 원하지 않습니다. 안전하고, 편안하며, 에너지 효율적이어야 합니다. 배송 드론은 속도와 배터리 수명, 그리고 새와 충돌할 위험 사이에서 균형을 잡아야 할 수도 있습니다. 로봇이 여러 개의, 종종 서로 상충하는 목표들을 조율해야 할 때, 단순히 하나의 "최선"인 경로를 선택할 수는 없습니다. 대신, "최선의 절충안"이라는 메뉴 전체를 찾아내야 합니다. 이것이 바로 다목적 모션 플래닝(multi-objective motion planning)의 세계입니다.

이 과제를 이해하기 위해, 로봇의 경로를 지도 위에 그려진 선이라고 생각해 보십시오. 로봇은 벽(장애물)을 뚫고 지나가지 않아야 하고, 물리 법칙(너무 빠르게 움직일 때는 즉각적으로 방향을 틀 수 없음)을 준수해야 하는 것과 같은 규칙을 따라야 합니다. 이러한 규칙을 "키노다이내믹 제약 조건(kinodynamic constraints)"이라고 부릅니다. 여기에 "시간 최소화"와 "안전 최대화"와 같은 여러 목표를 추가하면, 더 이상 단 한 명의 승자를 찾는 것이 아닙니다. 대신, 여러분은 "파레토 프런트(Pareto front)"를 찾게 됩니다. 이는 한 가지 목표를 개선하면 반드시 다른 목표가 나빠질 수밖에 없는 경로들의 집합을 의미하는 멋진 표현입니다. 마치 매운맛과 단맛의 완벽한 균형을 갖춘 요리들이 있는 메뉴판과 같습니다. 더 맵게 만들면 반드시 단맛을 잃게 되는 것과 같습니다.

이 논문은 로봇이 격자(grid) 위가 아닌 실제 연속적인 세상에서 움직일 때, 어떻게 이러한 완벽한 균형을 찾도록 도울 것인가라는 문제를 다룹니다. 콜로라도 대학교 볼더 캠퍼스의 유시프 라자크(Yusif Razzaq)와 그의 팀은 기존의 방식들이 복잡한 물리 법칙을 가진 로봇들에게는 잘 작동하지 않는다고 주장합니다. 그들은 로봇이 가능한 모든 "최선의 절충안"을 일일이 시도해 보는 대신, 한 번에 탐색할 수 있도록 돕는 새로운 통합적인 방법을 제안합니다.

목표를 "섞는 것"의 문제점

오랫동안 엔지니어들이 두 가지 목표(예: 속도와 안전)를 가진 로봇을 마주했을 때, 그들은 "스칼라화(scalarization)"라고 불리는 기술을 사용했습니다. 사과(속도) 한 봉지와 오렌지(안전) 한 봉지가 있다고 상상해 보십시오. 어떤 봉지가 더 나은지 결정하기 위해, 여러분은 "오렌지 하나는 사과 두 개의 가치가 있다"라고 말한 뒤 총 "과일 점수"를 계산할 수 있습니다. 이렇게 하면 두 개의 목표가 하나로 바뀝니다. 로봇은 그저 가장 높은 점수를 얻으려고 노력할 뿐입니다.

이 논문의 저자들은 이 "섞기" 기술에 치명적인 결함이 있음을 보여줍니다. 그들은 특정 유형의 문제, 특히 목표 간에 엄격한 우선순위가 있는 경우, 비용을 단순히 섞는 것만으로는 해결할 수 없다는 것을 수학적으로 증명합니다. 예를 들어, 로봇이 먼저 충돌을 피하고(안전), 그다음 빨라져야(속도) 한다면, 어떤 "과일 점수" 계산법도 안전을 올바르게 우선시하는 것을 보장할 수 없습니다. 만약 이들을 섞으려 한다면, 로봇은 수학적으로 "점수"가 더 높다는 이유로 벽에 위험할 정도로 가까운 경로를 택할 수도 있습니다. 이 논문은 단순한 가중치 합(목표를 섞는 것)이 자신들의 새로운 방법만큼 신뢰성 있게 문제를 해결할 수 없다는 점을 명시적으로 배제합니다.

새로운 접근법: 탐험가 팀

저자들의 솔루션은 SST(Stable Sparse-RRT)라고 불리는 기존 알고리즘을 기반으로 합니다. SST는 지도에 다트를 던져 경로를 찾는 로봇과 같습니다. 보통 SST는 지도의 각 작은 구역마다 단 하나의 "최선"인 경로만을 유지합니다. 만약 새로운 경로가 약간 더 낫다면, 기존의 경로를 대체합니다.

저자들은 여러 목표를 다룰 때, 단 하나의 경로만을 유지하는 것은 메뉴에서 단 하나의 요리만 보고 최선의 절충안을 찾으려는 것과 같다는 점을 깨달았습니다. 대신 그들은 알고리즘을 변경하여 각 구역에 경로의 팀을 유지하도록 했습니다. 새로운 프레임워크에서, 로봇이 영역을 탐색할 때마다 단순히 한 명의 승자를 뽑는 것이 아니라, "국소적 파레토 최적(locally Pareto-optimal)"인 경로들의 작은 그룹을 유지합니다. 이들은 너무나 훌륭해서, 하나를 개선하려면 반드시 다른 하나를 해쳐야만 하는 경로들입니다.

이 단 한 번의 변화를 통해, 그들은 동일한 핵심 아이디어를 바탕으로 세 가지 특화된 로봇을 구축할 수 있었습니다.

1. LEXSST (엄격한 상사): 이 로봇은 목표에 엄격한 우선순위 목록이 있는 상황(예: "안전 우선, 속도 차선")을 처리합니다. 저자들은 연속적인 세상에서 이러한 순서를 강제하기 위해 단순히 수학 공식만을 사용하는 것이 불가능하다는 것을 발견했습니다. 따라서 LEXSST는 영리한 "퍼지(fuzzy)" 규칙을 사용합니다. 이 로봇은 가장 안전한 경로들을 찾되, 그것들이 절대적인 최고 수준만큼은 아니더라도 (사용자가 정의한 아주 작은 허용 오차 범위 내에서) 거의 안전하도록 허용합니다. 그런 다음, 이 "거의 완벽한" 안전한 경로들 중에서 가장 빠른 경로를 선택합니다. 이를 통해 로봇은 수학적으로 불가능한 "완벽한" 동점을 찾으려다 갇히지 않고, 우선순위 순서를 존중할 수 있습니다.
2. COSST (규칙 준수자): 이 로봇은 하드 리미트(hard limits)가 있는 상황(예: "속도는 시속 50마일 미만이어야 하지만, 연료는 최소화하라")을 처리합니다. 논문은 기존 SST 방식이 여기서 실패할 수 있음을 보여줍니다. 왜냐하면 SST는 속도를 높이는 데 너무 집중한 나머지, 속도 제한을 아슬아슬하게 넘기는 경로를 선택하여 갑작스러운 장애물을 피할 여지를 남겨두지 않을 수 있기 때문입니다. COSST는 규칙 내에 머무는 모든 경로를 유지함으로써, 로봇이 너무 빠르게 달리는 데만 몰두하다가 실수로 막다른 길에 갇히는 일을 방지합니다.
3. POSST (메뉴 제작자): 이것은 가장 야심 찬 로봇입니다. 이 로봇의 임무는 최선의 절충안이라는 전체 메뉴를 찾아내는 것입니다. 단 하나의 승자를 고르는 대신, 전체 "파레토 프런트"를 그려냅니다. 이 로봇은 설계자(인간)에게 가능한 모든 트레이드오프를 보여줍니다: "여기 매우 빠르지만 위험한 경로가 있고, 여기 매우 안전하지만 느린 경로가 있으며, 그 사이의 모든 완벽한 균형들도 있습니다."

연구 결과

연구팀은 단순한 개활지부터 좁은 통로가 있는 복잡한 미로까지 다양한 시뮬레이션 환경에서 이 새로운 알고리즘들을 테스트했습니다. 그들은 이 방법들을 기존의 "섞기" 기술(스칼라화)과 비교했습니다.

결과는 명확했습니다. "엄격한 상사" 시나리오에서 기존 방식들은 엔지니어가 수학적 설정을 어떻게 조정하느냐에 따라 너무 위험하거나 너무 느린 경로를 만들어냈습니다. 반면 LEXSHT는 우선순위를 완벽하게 존중하는 경로를 일관되게 찾아냈습니다. "규칙 준수자" 시나리오에서, 까다로운 좁은 통로 테스트를 수행했을 때 기존 방식은 93%의 실행에서 해결책을 찾는 데 실패했지만, COSST는 100% 성공했습니다. 이는 기존 방식이 초기에 좋아 보이는 경로를 선택하느라 너무 탐욕적이었던 반면, COSST는 길을 찾아낼 수 있도록 충분한 옵션을 열어두었기 때문입니다.

아마도 가장 인상적인 점은, 트레이드오프의 전체 메뉴를 그려내는 것(POSST)에 있어서 새로운 방법이 훨씬 더 효율적이었다는 것입니다. 기존의 "섞기" 방법을 사용하여 유사한 다양성의 솔루션을 얻으려면, 컴퓨터는 서로 다른 설정으로 101번의 플래닝 알고리즘을 실행해야 했습니다. 하지만 POSST는 단 한 번의 실행만으로 더 다양하고 우수한 솔루션 세트를 찾아냈습니다.

결론

이 논문은 단순히 약간의 수정을 제안하는 것이 아니라, 로봇이 여러 개의 경쟁하는 목표를 가질 때 어떻게 결정을 내리는지에 대한 새로운 사고방식을 제공합니다. 단순한 수학적 혼합이 특정 문제에서 실패한다는 것을 증명하고, 단 하나의 "승자"가 아닌 "팀"을 유지하는 방법을 도입함으로써, 저자들은 더 신뢰할 수 있고 효율적인 툴킷을 만들었습니다.

그들의 연구는 로봇이 존재한다면 반드시 솔루션을 찾아낸다는 것(완전성)과, 그 솔루션이 최적의 결과에 매우 근접할 것이라는 것(근사 최적성)을 보장하는 수학적 증명에 의해 뒷받침됩니다. 비록 논문에서 몇 가지 과제(예: "엄격한 상사" 시나리오에서 두 개 이상의 목표를 처리하는 법)가 남아있음을 언급하긴 했지만, 그들의 새로운 알고리즘인 LEXSST, COSST, POSST는 차세대 지능형 다목적 로봇을 위한 견고한 토대를 제공합니다. 이들은 때때로 최선의 경로를 찾기 위해서는, 단 한 명의 승자를 찾는 것을 멈추고 전체 팀의 가치를 인정해야 한다는 것을 보여줍니다.