Multi-Robot Task Allocation and Path Planning Based on HIGWO-NSGAII

현대 물류, 재난 구호, 그리고 공장 자동화의 활기찬 세계에서 단 한 대의 로봇만으로는 충분하지 않은 경우가 많습니다. 창고를 효율적으로 통과하거나 붕괴된 건물 내부를 탐색하기 위해서는 기계 팀이 함께 협력해야 하지만, 이들을 조율하는 것은 엄청난 복잡성을 지닌 퍼즐입니다. 과제는 두 부분으로 나뉩니다. 어떤 로봇이 어떤 특정 작업을 수행할지 결정하는 것, 그리고 각 로로봇이 목적지에 도달할 때 벽에 부딪히거나 팀원들과 충돌하지 않도록 안전하고 효율적인 경로를 설정하는 것입니다. 로봇과 목표물의 수가 늘어남에 따라 이러한 작업을 배치할 수 있는 가능한 방법의 수는 폭발적으로 증가하며, 이는 전통적인 컴퓨터 방식으로는 최적의 해답을 빠르게 찾는 것을 거의 불가능하게 만듭니다. 더욱이 이러한 시스템은 종종 상충하는 목표에 직면합니다. 예를 들어, 팀 전체의 총 이동 거리를 최소화하는 계획은 한 로봇에게 매우 길고 힘든 경로를 강요할 수 있는 반면, 작업 부하를 균형 있게 맞추는 계획은 총 이동 거리를 증가시킬 수 있습니다. 이러한 경쟁적인 요구 사이에서 완벽한 균형을 찾는 데는 새로운 종류의 수학적 접근 방식이 필요합니다.

안후이 정보기술 연구소(Anhui Institute of Information Technology)의 연구진은 이 조정 문제를 해결하기 위해, 로봇 팀을 위한 고도로 숙련된 교통 관제사처럼 작동하는 하이브리드 알고리즘을 개발하여 새로운 방법을 만들어냈습니다. 그들은 자신들의 접근 방식을 HIGWO-NSGAII라고 명명했는데, 이는 작업 할당과 경로 탐색이라는 이중 과제를 처리하기 위해 두 가지 뚜렷한 계산 전략을 결합한 시스템입니다. 연구진은 체스판과 유사한 격자 형태의 환경 내에서 작동하도록 시스템을 구축했으며, 여기서 장애물은 고정된 블록이고 로봇은 칸 단위로 이동합니다. 본격적인 계획을 시작하기 전에, 시스템은 잘 알려진 경로 탐색 도구를 사용하여 모든 로봇에서 모든 잠재적 목표물까지의 최단 거리를 계산함으로써, 최적화 과정의 토대가 되는 비용 지도를 생성합니다. 이들의 혁신의 핵심은 하나의 알고리즘이 가진 광범위하고 다양한 탐색 능력과 다른 알고리즘이 가진 신속하고 집중적인 사냥 본능을 결합하는 방법이며, 이를 통해 시스템은 많은 다양한 가능성을 탐색하는 동시에 가장 효율적인 해답으로 빠르게 집중할 수 있습니다.

작업의 복잡성을 관리하기 위해 연구진은 늑대 무리의 사회 구조를 모방한 시스템을 설계했습니다. 자연계에서 늑대 무리는 알파, 베타, 델타가 이끄는 명확한 계층 구조 속에서 사냥을 하며, 각자는 특정한 역할을 수행합니다. 연구진은 이러한 행동을 디지털 메커니즘으로 변환하여, 지금까지 발견된 최고의 해답들이 이러한 리더 역할을 하도록 했습니다. 실제 늑대처럼 연속적으로 움직이는 대신, 디지털 버전은 이러한 '리더' 해답들의 특정 부분을 현재의 계획에 주입하여, 퍼즐의 조각을 교체함으로써 새로운 배열이 더 나은지 확인합니다. 이 과정은 모든 로봇이 정확히 하나의 고유한 목표를 할당받고 어떤 두 로봇도 같은 일을 맡지 않도록 유효한 해답을 유지하도록 정교하게 제어됩니다. 시스템이 국소적인 정체 상태에 빠지는 것을 방지하기 위해, 연구진은 실시간으로 팀의 전략을 조정하는 코치 역할을 하는 학습 구성 요소를 추가했습니다. 이 코치는 그룹의 진행 상황을 모니터링하고, 언제 새로운 아이디어를 향한 대담하고 광범기한 탐색을 장려할지, 그리고 언제 이미 발견된 최선의 아이디어를 정교화하는 데 집중할지를 결정합니다. 코치는 서로 다른 계획들을 혼합하는 확률이나 작은 무작위 변화를 만드는 과정을 자동으로 조정함으로써 이를 수행하며, 이를 통해 팀이 탐색 과정 내내 적응력을 유지할 수 있도록 합니다.

연구진은 세 가지 다른 시나리오(12대의 로봇이 있는 작은 격자, 20대의 로봇이 있는 중간 격자, 30대의 로봇이 있는 큰 격자)를 사용하여 이 새로운 방법을 기존의 7가지 알고리즘과 비교 테스트했습니다. 모든 테스트에서 이 새로운 시스템은 다른 알고리즘보다 뛰어난 성능을 보였으며, 더 나은 해답을 찾을 뿐만 아니라 더 일관된 결과를 보여주었습니다. 가장 작은 테스트와 가장 큰 테스트에서 이 시스템은 이론적 최적 참조 전선(optimal reference front)과 완벽하게 일치하는 해답 집합을 찾아내어 다른 방법들이 따라올 수 없는 신뢰성을 보여주었습니다. 중간 크기의 테스트에서는 차순위 방법과 비교했을 때 해답 집합의 전반적인 품질을 20% 이상 향상시켰으며, 최적 참조 전선까지의 거리를 90% 이상 단축했습니다. 이 시스템은 특히 양질의 옵션에 대한 다양성을 유지하는 데 효과적이었으며, 인간 운영자에게 단 하나의 경직된 계획이 아닌 풍부한 선택지를 제공했습니다. 반면, 연속적이고 매끄러운 환경에서 잘 작동했던 다른 방법들은 이 이산적인 격자 기반 문제에 적용되었을 때 크게 어려움을 겪었으며, 로봇이 불필요한 우회로를 택하거나 해답들이 너무 유사하여 실질적인 다양성을 제공하지 못하는 결과를 낳기도 했습니다.

이 연구는 서로 다른 계산 방식의 강점을 결합하고 적응형 학습 계층을 추가함으로써, 로봇 팀의 복잡한 조정 문제를 높은 정밀도와 안정성으로 해결할 수 있음을 입증합니다. 연구진은 그들의 방법이 작은 규모의 그룹부터 더 큰 규모의 함대에 이르기까지 효과를 잃지 않고 다양한 규모에서 잘 작동한다는 것을 발견했습니다. 현재의 연구는 정적인 장애물이 있는 시뮬레이션 환경에서 수행되었지만, 결과는 속도와 공정성의 균형이 중요한 창고 및 구조 작업과 같은 실제 응용 분야를 위한 강력한 도구가 될 수 있음을 시사합니다. 저자들은 향후 연구에서 움직이는 장애물과 동적인 과제를 다루어야 함을 인정하지만, 현재의 연구 결과는 여러 로봇을 효율적으로 조정하는 방법에 대한 견고하고 검증된 토대를 제공합니다. 이 하이브리드 접근 방식이 전체적인 효율성과 개별 작업 부하 사이의 최적의 절충안을 일관되게 찾아낼 수 있음을 증명함으로써, 본 연구는 물리적 세계에서 더 똑똑하고 협력적인 로봇 팀을 배치하기 위한 실질적인 경로를 제시합니다.