[Robotics] Multi-Robot Systems 및 2개 핵심주제 – MAPF 부터 TA 까지

이번 포스팅은 다른 포스팅과는 다르게 조금 전문적인 내용을 다뤄보려고 합니다. 특히, 로봇분야 중에서도 Multi-Robot Systems는 상대적으로 온라인에서 찾아볼 수 있는 논문이나 기타 자료가 적어 시간을 들여 작성하는 것이 의미가 있을 것 같습니다. 넓은 의미의 로봇공학에 대한 소개 보다는 더 세부적이고 구체적인 세부분야 소개가 될 것 같고, 로보틱스로의 진로를 생각하시는 분들께 도움이 되었으면 하는 마음을 글을 시작해봅니다.

본 글에서는 Multi-Robot Systems의 간단한 소개부터 시작하여, 이 분야의 주요 연구들과 그들의 성과를 조명하고자 합니다. 또한, 이 기술이 다양한 산업에 어떻게 적용될 수 있는지, 그리고 미래 사회에서 어떠한 새로운 가능성을 열어줄 수 있는지에 대해 적어보도록 하겠습니다.

참고로, 로봇 분야에서 미국으로 유학을 고려하시는 분들께서는 아래 미국 대학원 유학 관련 자세한 소개를 담은 포스팅을 참고하시면 도움이 되실 것 같습니다.

미국 대학원 준비와 박사과정 지원의 모든 것 – 준비부터 제출까지 예시와 함께 10분만에 알아보기

미국 대학원 준비 및 박사과정 지원을 위해 알아야 할 내용을 처음부터 끝까지 설명해 드립니다.
어디서부터 무엇을 어떻게 해야하는지 막막한 출발점에서 시작하는 것은 모두 같지 않을까 합니다. 처음엔 막막하고 답답했던, 다 지나서 돌아보면 한번 해볼 만 했던 미국 대학원 박사과정 유학을 위한 지원 과정을 하나씩 소개하며 경험을 공유해보고자 합니다.

미국 대학원 SOP 작성하기 – 샘플로 보는 초안부터 완성까지

미국 대학원 지원 준비에서 가장 어렵고 오래걸리는 과정이 바로 SOP (Statement of Purpose)인 것 같습니다. 우리나라 대학원에서 학업계획서에 대해 형식상 보고 넘어가는 통상적인 절차와는 다르게 미국 대학원에서는 SOP를 진지하게 고려하고 적지 않은 비중으로 평가하는 것으로 알려져 있기 때문에 실제로 오래걸려야하고 신경을 많이 써야하는 서류 입니다.

미국 대학원 Personal Statement – 예시로 보는 작성 방법

미국에서는 대학원 뿐 아니라 대학 지원에도 Personal Statement가 지원자를 어필하는 매우 중요한 항목 중 하나로 알려져있습니다. 우리나라에서 반쯤 형식적으로 적어내는 자기소개서 보다 더 평가에 비중이 높고 그래서 더 신경써서 작성해야 합니다. 이번 포스팅에서는 미국 대학원 지원을 위한 Personal Statement를 처음부터 어떤 내용으로 채워야 하는지, 그리고 작성은 어떤 양식으로 어떻게 작성해야할지 저의 샘플과 함께 소개드리도록 하겠습니다.

미국 대학원 CV / Resume 작성의 모든것 – 샘플과 함께 알아보기

미국에서 취업 혹은 대학원 진학을 앞둔 대학생들에게 CV/Resume 작성은 사실상 필수적인 과정 입니다. 준비가 빠른 경우는 대학교 2~3학년 정도 부터 인턴쉽을 위해 작성하기도 하고, 4학년이 되면 예외를 찾기 어려울 정도로 모든 학생들이 각자의 이력서를 들고 career fair(여러 기업이 참석하는 취업 행사) 자리를 알아보거나 대학원 진학을 위해 대학 교수들을 찾아다닙니다. 미국 대학원 지원에도 역시 이력서가 필요하고, 자유양식이라고는 하나 어느정도 정해진 형식이 있습니다.

미국 대학원 박사과정 지원 연구실 고르기 – 학교 및 학과 선택과 연구실 컨택

미국 대학원으로의 유학 결정은 큰 용기있는 결정입니다. 유학의 결정은 단순히 좋은 학교로 가겠다는 것 이상의 의미가 있고, 그만큼 더 어렵고 중요한 인생의 결정입니다. 유학의 결정의 순간 가진 목표에 다가가기 위해 나에게 맞는 학교를 찾아가는 것은 그 중요한 여정의 시작입니다.

Multi-Robot Systems (MRS)

로봇공학 초기부터 지금까지 수십년에 걸친 로봇연구는 거의 모두 한대의 로봇을 잘 동작시키는 데에 중점을 두었습니다. 휴머노이드 로봇을 잘 걷게하거나 어려운 동작을 자동으로 가능하게 하는 등 한대의 로봇이 특정한 작업을 잘 수행하는 것과 같이 목표가 구체적이고 한대의 로봇에 국한되었습니다.

그러나 최근 십수년의 로봇공학 연구는 꽤 많이 진보하였고, 머신러닝과 높아진 PC 성능을 기반으로 그동안의 문제를 훌륭하게 해결하는 연구성과들이 빠르게 등장하였습니다. 제한적인 환경에서의 실내외 자율주행은 상당히 많이 가능해졌고, 아직은 극히 일부이지만, 일부 로봇들은 공장을 벗어나 사회로 나오기 시작하였습니다.

로봇공학 연구의 궁극적인 목표로 꼽을 수 있는 것이 ‘인간을 대신’하여 어렵고 위험한 혹은 번거로운 작업을 하도록 로봇을 발전시키는 것이라는 점을 생각하면, 한대의 로봇을 넘어 여러대의 로봇을 활용하는 방향으로 옮겨가는 것은 어찌보면 매우 자연스러운 흐름입니다. 여기서 시작되는 분야가 바로 Multi-Robot Systems 입니다. (Multi-Agent Systems로 부르기도 합니다.)

Multi-Robot Systems는 여러 로봇이 협업하여 복잡한 작업을 수행하는 기술을 지칭합니다. 이러한 시스템은 단독 로봇의 한계를 넘어서서 더 광범위하고 복잡한 임무를 수행할 수 있는 잠재력을 지니고 있습니다. 예컨대 탐사, 구조, 물류 등 다양한 분야에서 로봇들이 팀워크를 발휘하여 보다 큰 목표를 달성합니다.

이 분야의 연구는 로봇들 간의 효율적인 협력 방안, 서로의 작업을 어떻게 보완할 수 있는지, 그리고 공동 목표를 향해 나아가는 전략들에 중점을 두고 있습니다. 이러한 연구는 로봇공학의 근본적 질문에 대한 답을 모색하는 동시에, 로봇이 인간의 삶을 어떻게 보다 나은 방향으로 이끌 수 있는지에 대한 새로운 관점을 제시합니다.

Multi-Robot Systems 연구 내용

Multi-Robot Systems는 다른 로봇분야들에 비해 본격적으로 연구되어 온 기간이 짧고 비교적 초기단계라고 볼 수 있습니다. 이에, 지금 Multi-Robot Systems 분야에서 나오고있는 연구들은 쉽게 표현하여 ‘기반 조성’에 가까운 연구들이 주를 이루고 있습니다. 당장 실제 환경에서 활용이 가능한 연구보다는 필요한 기능 하나하나를 만들어가는 단계에 가깝습니다.

Multi-Robot Systems는 개념적으로 다양한 로봇들의 Coordination을 포함하지만, 아직은 자유도가 높은 로봇들 보다는 모델링이 쉬운 Mobile Robot의 협력에 중점을 둔 연구가 많이 이루어지고 있습니다. Mobile Robot에 대한 연구인 만큼 Path Planning이 가장 founding work로 볼 수 있습니다.

Multi-Agent Path Finding (MAPF)

Multi-Robot Systems의 핵심 도전 중 하나는 여러 로봇이나 에이전트가 서로 충돌하지 않으면서도 효과적으로 목적지까지 이동하는 경로를 찾는 것입니다. 이를 통틀어서 Multi-Agent Path Finding(MAPF)라고 합니다.

MAPF는 다수의 에이전트가 각각의 출발 지점에서 목적지까지 이동하는 동안 서로 충돌하지 않고, 가능한 한 최적의 경로를 찾는 문제를 다룹니다. 이 과제는 단순히 개별 로봇의 경로를 최적화하는 것을 넘어, 그들 간의 상호작용과 조정에 중점을 둡니다. 이는 특히 동적이고 예측하기 어려운 환경에서 로봇들이 효율적으로 협력하고, 임무를 수행하는 데 필수적인 요소입니다.

MAPF 평가 요소

MAPF에서 가장 많이 고려하는 문제는 크게 아래와 같습니다:

• Optimality: Planning 결과로 나온 여러 로봇의 경로가 항상 최소 Cost(주로 거리 혹은 시간) 합을 보장할 수 있는지
• Scalability: 로봇 혹은 Task의 숫자가 늘어나도 연산시간이 더 급격히 올라가지 않는지
• Centralized/Decentralized: 경로를 찾는데 로봇이 각자 알아서 탐색이 가능한지 혹은 중앙 통제가 필요한지

Optimality

최적성은 MAPF의 주요 목표 중 하나로, 모든 에이전트가 개별적으로 그리고 전체적으로 최적의 경로를 찾는 것을 의미합니다. 이는 단순히 가장 빠른 경로를 찾는 것을 넘어, 경우에 따른 Cost를 최소화 하는 것을 보장할 수 있는지 여부 입니다. 가장 보편적인 예는 총 거리를 Cost로 하여 모든 로봇의 경로 길이의 합이 가능한 최소한의 거리가 되는 것을 보장할 수 있는지가 되겠습니다. 시스템에 따라서는 거리가 아닌 시간이 되기도 하고, 다양한 조건에 따른 에너지 소비량이 될 수도 있습니다. 어떤 Cost가 되었던 이 Cost의 합이 최소한인 결과를 항상 내어준다면 Optimal planner 라고 부르게 됩니다.

다만, Optimality가 최우선으로 고려되는 사항은 아닐 수 있습니다. 단편적인 예로, 최적의 경로를 10초 뒤에 찾아주는 시스템 보다는 최적은 아니지만 적당한 경로를 2초만에 찾아주는 planner가 더 선호될 수도 있기 때문이죠.

Scalability

MAPF에서 Scalability는 시스템이 다양한 크기와 복잡도의 환경에서 효과적으로 작동할 수 있는 능력을 의미합니다. 이는 로봇의 수가 증가하거나 작업 환경이 복잡해질 때, 시스템이 그에 맞춰 적절하게 조정되어야 함을 의미합니다.

MAPF의 Scalability는 현재도 많은 연구자들이 풀어내고자 노력하고 있는 문제입니다. 경로 탐색에 소요되는 시간이 주어진 로봇 수가 늘어나는 만큼만 늘어나면 좋을텐데, 현재까지 알려진 대부분의 MAPF는 그렇지 못합니다. 즉, 로봇 수가 늘어남에 따라 그보다 더 급격하게 연산시간이 늘어나는 높은 Computational Complexity가 병목인 경우가 많이 있습니다.

어떤 연구들은 이 Scalability에 중점을 둔 내용들도 있습니다. 주로 문제를 간소화 하여 로봇이 수십에서 수백대 까지 늘어나더라도 연산을 빠르게 유지시킬 수 있는 방법들이 있습니다만, 실제 로봇에 적용하기에는 아직 풀어야할 다른 문제들도 남아있습니다.

Centralized/Decentralized

경로 탐색을 위해 환경 전체를 통제하는 중앙 시스템이 필요한지의 여부는 제한된 환경을 벗어난 시스템으로 나아가기 위해 풀어야하는 중요한 문제 중 하나입니다.

Centralized System은 말 그대로 환경에 대해 모든걸 알고 로봇을 통제할 수 있는 중앙 시스템이 있는 조건이 포함된 경우 입니다. 모든 로봇의 위치와 환경을 파악하고 있고 로봇에게 명령을 내릴 수도 있는 시스템이 있으면 경로생성 및 다양한 상황에 대한 대처도 쉽게 가능할 수 있지만, 동시에 그만큼 제한된 환경에서의 사용만 가능하다는 의미이기도 합니다. 잘 통제된 물류창고에서는 가능할 수 있어도 조건이 조금만 다라져도 사용이 불가하다는 의미가 됩니다. 중앙집권 시스템이라고 비유할 수 있겠습니다.

Decentralized System은 모든 시스템에 대한 절대적인 통제권이 있는 주체가 있지 않고 각 로봇이 알아서 판단하는 조건의 환경을 의미합니다. 각 로봇이 가진 정보가 제한적인 만큼 Optimality를 확보하기는 어렵지만, 그만큼 제약조건이 적다는 장점이 있습니다. 로봇 시스템이 궁극적으로 현실로 나와 중앙 시스템이 없는 사람 속으로 들어오려면 꼭 필요한 조건이기도 합니다.

알려진 연구

MAPF에서 가장 많이 언급되고 참고되는 몇몇 유명 연구들이 있어 소개하고자 합니다. 제가 놓친 연구도 있을 수 있고, 이는 종종 업데이트 하고자 합니다.

Cooperative A* (Space-Time A* 혹은 STA*)

로봇의 경로탐색에 가장 많이 쓰이는 A* 방식을 기반으로 시간축을 추가한 탐색방식 입니다. 각 Agent가 순서대로 탐색을 하고, 각 Timestep에 Cell을 Reserve 해 두면 그 다음 로봇은 탐색 시 Reserve된 Cell은 후보에서 제외하는 방식입니다. (Reservation Table 로도 불립니다.) 직관적이고 속도도 빠르지만, 탐색하는 로봇의 순서가 결과에 영향을 줄 수 있습니다. 또한, A*와는 달리 항상 Optimality를 보장하지는 않습니다. [논문링크]

Cooperative Pathfinding | Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment

Cooperative Pathfinding is a multi-agent path planning problem where agents must find non-colliding routes to separate destinations, given full information about the routes of other agents. This paper presents three new algorithms for efficiently solving this problem, suitable for use in Real-Time Strategy games and other real-time environments. The algorithms are decoupled approaches that break down the problem into a series of single-agent searches. Cooperative A* (CA*) searches space-time for a non-colliding route. Hierarchical Cooperative A* (HCA*) uses an abstract heuristic to boost performance. Finally, Windowed Hierarchical Cooperative A* (WHCA*) limits the space-time search depth to a dynamic window, spreading computation over the duration of the route. The algorithms are applied to a series of challenging, maze-like environments, and compared to A* with Local Repair (the current video-games industry standard). The results show that the new algorithms, especially WHCA*, are robust and efficient solutions to the Cooperative Pathfinding problem, finding more successful routes and following better paths than Local Repair A*

Conflict-Based Search (CBS)

현재까지 MAPF에서 가장 많이 활용되고 언급되는 방식은 충돌지점을 중심으로 문제를 풀어내는 CBS 방식 입니다. 우선 여러 로봇이 다른 로봇을 고려하지 않고 각자의 경로를 생성 후, 두 로봇의 충돌이 예상되는 지점에서 각 로봇의 상대 로봇을 회피하는 경로를 만드는 State를 각각 expand 하는 과정을 최종적으로 경로가 찾아질 때 까지 반복합니다. Optimal한 solver 이지만, 로봇이 많아질 경우, 특히 넓지 않은 공간에 몰려있어 state를 expand하는 횟수가 늘어날 수록 연산시간이 크게 증가하는 탓에 Scalability에서 아쉬운 planner 입니다. [논문링크]

Conflict-Based Search For Optimal Multi-Agent Path Finding | Proceedings of the AAAI Conference on Artificial Intelligence

In the multi agent path finding problem (MAPF) paths should be found for several agents, each with a different start and goal position such that agents do not collide. Previous optimal solvers applied global A*-based searches. We present a new search algorithm called Conflict Based Search (CBS). CBS is a two-level algorithm. At the high level, a search is performed on a tree based on conflicts between agents. At the low level, a search is performed only for a single agent at a time. In many cases this reformulation enables CBS to examine fewer states than A* while still maintaining optimality. We analyze CBS and show its benefits and drawbacks. Experimental results on various problems shows a speedup of up to a full order of magnitude over previous approaches.

M*

M* 알고리즘은 멀티 에이전트 경로 탐색(Multi-Agent Path Finding, MAPF) 문제에 대한 해결책 중 하나로, 특히 복잡한 환경에서 여러 로봇 또는 에이전트가 충돌 없이 효율적으로 목적지까지 이동할 수 있는 경로를 찾는 데 사용됩니다. 이 알고리즘은 각 에이전트의 독립적인 경로 계획과 동시에 다른 에이전트들과의 상호작용을 고려하여 전체적인 경로를 최적화합니다. Optimal 하며 동적 환경에 대해 대처가 가능하지만, Scalability가 높지 않고 연산이 복잡하여 시간이 더 걸리는 단점이 있습니다. [논문링크]

M*: A complete multirobot path planning algorithm with performance bounds

Multirobot path planning is difficult because the full configuration space of the system grows exponentially with the number of robots. Planning in the joint configuration space of a set of robots is only necessary if they are strongly coupled, which is often not true if the robots are well separated in the workspace. Therefore, we initially plan for each robot separately, and only couple sets of robots after they have been found to interact, thus minimizing the dimensionality of the search space. We present a general strategy called subdimensional expansion, which dynamically generates low dimensional search spaces embedded in the full configuration space. We also present an implementation of subdimensional expansion for robot configuration spaces that can be represented as a graph, called M*, and show that M* is complete and finds minimal cost paths.

Network Flow

RRT로 로봇 분야에서 상당히 잘 알려진 Steven Lavalle 교수가 교신저자로 있는 논문으로, Network Flow Problem을 기반으로 Multi-Agent Path Planning을 시도한 연구 입니다. (저도 아직 더 알아봐야 하는 연구내용 입니다.) [논문링크]

Multi-agent Path Planning and Network Flow

This paper connects multi-agent path planning on graphs (roadmaps) to network flow problems, showing that the former can be reduced to the latter, therefore enabling the application of combinatorial network flow algorithms, as well as general linear program…

Task Allocation (TA)

Multi-Robot Systems에서 Path Planning 만큼이나 중요한 것이 바로 Task Allocation, 즉 작업 배정 입니다. 여러대의 로봇을 사용하는 궁극적인 목표가 하나 혹은 여러 Task를 여러 로봇의 협력으로 해결하려는 것인 만큼 각 로봇에게 어떤 일을 시킬것인지 결정하는 모델은 필연적으로 필요한 MRS의 요소 입니다.

여러 상황을 고려한 효과적인 Task Allocation 방법을 찾기 위하 다양한 방법이 시도되고 있지만, 아직 연구가 많이 필요한 부분입니다.

Hungarian Algorithm

Hungarian Algorithm은 최적 할당 문제를 해결하기 위한 고전적인 방법 중 하나입니다. 각 Agent와 Task 수행 Cost를 정의한 Matrix를 형성하고, Optimization 방식으로 Task Allocation을 찾습니다.

Cost의 합이 minimum인 optimal solution을 보장하고 연산이 빠르지만, Static한 환경에서만 적용이 가능하다는 단점이 있습니다.

Search Tree Expansion

각 로봇이 Task를 Allocation 받았을 모든 혹은 일부 가정을 State로, Cost가 가장 낮은 Task Allocation을 Tree에서 Search해 나가는 방식입니다.

Tree expansion 방식은 여러 Task의 Order Constraint가 존재할 때, 즉 일부 Task는 먼저 해결되어야 하는 task가 있을 때 이를 고려한 결과를 낼 수 있습니다. 단, Cost 연산에 따라 탐색 시간이 길어 Scalable하지 않을 수 있습니다.

제가 가장 최근 ICRA/iROS 논문에 사용한 방식이기도 합니다. [논문링크]

Coordination of two robotic manipulators for object retrieval in clutter

We consider the problem of retrieving a target object from a confined space by two robotic manipulators where overhand grasps are not allowed. If other movable obstacles occlude the target, more than one object should be relocated to clear the path to reach the target object. With two robots, the relocation could be done efficiently by simultaneously performing relocation tasks. However, the precedence constraint between the tasks (e.g, some objects at the front should be removed to manipulate the objects in the back) makes the simultaneous task execution difficult. We propose a coordination method that determines which robot relocates which object so as to perform tasks simultaneously. Given a set of objects to be relocated, the objective is to maximize the number of switches between the robots in performing relocation tasks. Thus, one robot can pick an object in the clutter while the other robot places an object in hand to the outside of the clutter. However, the object to be relocated may not be accessible to all robots, so switching could not always be achieved. Our method is based on the uniform-cost search so the number of switches can be maximized. We also propose a greedy variant whose computation time is shorter. From experiments, we show that our method reduces the completion time of the mission by at least 22.9% (at most 27.3%) compared to the methods with no consideration of switching.

강화학습 (Reinforcement Learning 혹은 RL)

강화 학습을 통한 작업 할당은 로봇이 작업 수행에 따른 보상을 받으며 학습합니다. 로봇은 시행착오를 거쳐 최대의 누적 보상을 얻을 수 있는 작업 할당 전략을 찾아갑니다.

이 방법은 특히 동적이고 예측 불가능한 환경에서 유용합니다. 로봇은 환경의 변화에 따라 할당 전략을 지속적으로 조정하며, 더 효과적인 작업 분배 방법을 학습합니다..

하지만, 이 방법은 많은 학습 데이터와 시간이 필요하며, 초기에는 비효율적일 수 있습니다. 또한, 학습 과정에서 부정확한 결과를 초래할 수 있으며, 최적 해를 항상 보장하지는 않습니다.

지금까지의 RL을 이용한 TA는 충분한 Generality를 보이지는 않고 있는것으로 알고 있습니다.

기타 방법

위 방법들 외에도 다양한 Task Allocation 방법들이 시도되고 있습니다. Generic algorithm, Bio-inspired methods (i.e. Ant Colony Optimization) 등 여러 접근방법이 있습니다.

마무리

이번 포스팅에서는 Multi-Robot Systems에 대한 전반적인 소개와 함께 이 분야에서 가장 중심이 되는 연구주제인 Multi-Agent Path Finding (MAPF) 및 Task Allocation에 대해 소개드렸습니다.

본 글에서는 멀티 로봇 시스템의 기본 원리, 작업 할당 문제에 대한 다양한 해결책, 그리고 이 분야가 직면한 주요 도전과제들을 상세히 검토하였습니다. 특히, 헝가리안 알고리즘, 강화 학습, 시장 기반 접근법, 유전 알고리즘과 같은 다양한 작업 할당 메커니즘에 대한 분석을 통해 이들이 멀티 로봇 시스템의 효율성과 협력적 역량을 어떻게 증진시키는지에 대한 심도 있는 이해를 도모했습니다.

이러한 멀티 로봇 시스템의 연구는 다양한 응용 분야에 걸쳐 중요한 시사점을 제공합니다. 이 시스템들은 복잡한 문제 해결을 위한 집단 지능과 협력의 실현을 목표로 하며, 이를 통해 향후 다양한 분야에서의 응용 가능성을 탐색하고 있습니다. 그러나 이 분야의 진전을 위해서는 지속적인 연구 개발과 기술 혁신이 요구됩니다.

이상으로, 로봇연구로의 진로를 생각하시는 분들께 MRS 분야에 대한 도움이 되는 소개가 되었길 바라며 글을 마칩니다.