방향 나열 염색체를 사용한 2 단계 유전 알고리즘 기반 다중로봇 경로계획

I. 서론

최근 물류, 제조, 서비스 산업 등 다양한 분야에서 로봇 자동화에 대한 수요가 급증함에 따라, 하나의 작업 공간 내에서 다수의 이동로봇을 운용하는 다중로봇 시스템에 대한 관심이 증가하고 있다.

풀필먼트 센터와 스마트 팩토리와 같은 산업 현장에서는 다품종 소량생산, 주문 맞춤형 물류 등의 복잡한 작업이 요구되며, 이에 따라 모바일로봇 기반의 멀티로봇 시스템이 활발히 도입되고 있다. 예를 들어, 풀필먼트 센터에서는 물류 전문기업이 판매자를 대신해 상품 보관, 포장, 배송까지 물류의 전 과정을 처리한다. 이러한 과정에서 상품 포장 시 모바일로봇이 상품을 선반 단위로 이동시켜 작업자가 고정된 자리에서 주문을 처리할 수 있도록 지원하고 있으며, 작업효율을 개선시키기 위한 다양한 연구도 이루어지고 있다[1-2]. 공장 자동화 환경에서는 모바일로봇이 부품이나 자재를 자동으로 운반함으로써 작업자의 개입을 최소화하고 공정 간 병목을 줄이고 있다. 이러한 방식은 기존의 고정된 컨베이어 시스템 대비 높은 공간 활용성과 작업 적응성을 제공하며, 공정 변화 등에도 빠르게 적응이 가능하다.

다중로봇 시스템 운용에서 중요한 기술적 과제는 로봇 간의 충돌을 방지하는 경로계획이다[3]. 로봇이 지역적인 회피 기능을 제공하더라도, 다수의 로봇이 한 구간에 몰리면 교착 상태(deadlock)가 발생할 수 있기 때문에 이를 고려한 경로계획 알고리즘 개발이 필수적이다.

다중로봇 경로계획법은 다양한 방법으로 연구되어 왔으며 고전적인 접근 방식, 휴리스틱 기반 방식, 인공지능 기반 방식, 생물 모사 메타휴리스틱 알고리즘 등으로 분류할 수 있다[4]. 휴리스틱 연구 중 하나인 HCA* (Hierarchical Cooperative A*)에서는 개별 로봇의 이동 경로를 예약 테이블에 저장하고, 다른 로봇과 공유하여 동시에 같은 위치를 점유하지 않도록 하였다[5]. A*+OD(A* with Operator Decomposition) 에서는 하나의 노드에 모든 로봇의 상태를 담아 탐색을 수행하되, 연산자 분해를 통해 확장 노드를 최소화하여 경로를 탐색하였다[6]. CBS (Conflict Based Search)에서는 개별 로봇의 경로를 독립적으로 계획한 뒤, 충돌이 발생할 때마다 충돌을 해결하기 위해 제약 조건을 생성하고 분기하여 탐색하는 계층적 알고리즘을 사용하였다[7].

생물 모사 메타 휴리스틱 알고리즘 중 대표적인 알고리즘으로는 유전 알고리즘(genetic algorithm, GA)이 있다. 많은 다중로봇 연구들이 다수 순회 판매원 문제(multiple traveling salesmen problem, MTSP)[8]의 개념을 확장하고 적용하여 해결할 수 있었다. 이때, MTSP는 NP-hard 문제이기 때문에 유전 알고리즘을 사용하여 근사해를 구하는 접근법이 많이 사용되었다[9]. MTSP에 특화된 염색체 구조를 새로 제안하여, 탐색공간을 줄여 탐색 효율을 향상시키는 연구도 진행되었다[10]. 하지만 많은 연구들에서 작업지 방문 순서 결정에만 유전 알고리즘을 활용하고, 경로계획에는 다른 알고리즘을 사용하는 한계가 있었다[11-12].

본 연구팀의 선행연구[13]에서는 유전 알고리즘을 활용한 충돌 최소화 경로 탐색 기법을 제안하였다. 이 연구에서는 로봇의 이동 정보를 효과적으로 표현하기 위해 방향 나열 염색체를 설계하고 이를 활용하였다. 본 논문에서는 탐색 효율 향상을 위해 2단계 유전 알고리즘을 적용하였으며, 제안한 기법의 성능을 MATLAB 시뮬레이션을 통해 검증하였다. 또한, 휴리스틱 기반의 대표적 경로탐색 알고리즘인 CBS와 비교 분석을 수행하였다.

II. 문제 정의

본 연구에서는 로봇이 그림 1과 같은 일정한 간격으로 장애물이 배치된 공간에서 동작한다고 가정하였다. 장애물 사이는 로봇이 지나갈 수 있는 통로가 되며, 통로가 가로세로로 만나는 곳은 교차로이다. 로봇들의 시작 위치와 목표 위치는 교차로이며, 무작위로 결정된다. 그림 1에서 “O” 표시는 각 로봇의 시작 위치이며, 같은 색깔의 “X” 표시는 도착 위치이다. 로봇이 도착 위치에 도달하면 충돌계산에서 제외하였다.

Fig. 1.

Robot operation environment.

모든 로봇들의 속도는 동일하며, 한 통로를 지나 다음 교차로에 도착할 때까지 두 시간 간격이 소요된다. 또한, 로봇들은 시간 간격이 동기화되어있다고 가정한다. 각 로봇은 교차로에 위치할 때, 상하좌우로 이동을 선택할 수 있다.

로봇은 통로에서만 정지할 수 있게 하였다. 이동 중 정지하는 것은 효율적인 충돌 회피 전략이 되며, 때로는 우회경로를 선택하는 것보다 좋은 선택이 되기도 한다. 다만, 교차로에서 정지하는 것은 다른 로봇의 이동을 방해할 우려가 있기 때문에 통로에서만 정지할 수 있다고 하였다. 예외로 로봇이 이동을 시작하기 전에는 교차로에서도 정지할 수 있도록 하였다. 정지는 두 시간 간격 동안 유지되는데, 이는 그림 2에서 볼 수 있듯이 통로를 지나는 시간과 일치시켜야 교차로에서 만나는 경우를 줄일 수 있기 때문이다.

Fig. 2.

Example of collision avoidance by stopping.

III. 유전 알고리즘

1. 방향 나열 염색체

유전 알고리즘은 진화론에서 기초하여 자연 선택과 유전재생산의 원리를 모방하여 최적해를 탐색하는 최적화 알고리즘이다. 염색체를 어떻게 설계하는지가 해의 수렴성과 알고리즘의 성능에 많은 영향을 미친다. 본 연구에서는 로봇들의 경로를 이동 방향의 순서로 표현할 수 있는 방향 나열 염색체를 활용하였다.

방향 나열 염색체는 로봇들의 이동 경로가 각 로봇별로 순차적으로 담겨있다. 하나의 로봇의 이동 경로는 이동방향을 표현한 앞부분과 정지시간을 표현한 뒷부분으로 나뉜다. 이동방향 부분에서는 위, 아래, 오른쪽, 왼쪽으로의 이동이 각각 정수 1, 2, 3, 4로 매칭되어 표현된다. 그림 3에서는 1번 경로와 2번 경로 모두 로봇의 최단경로에 해당한다. 오른쪽으로 3번의 이동과 위로 2번의 이동은 각각 3과 1로 변환되어 그림의 하단 오른쪽 예시와 같이 표현된다. 이동방향 부분은 로봇의 최단거리만을 표현하기 때문에, 시작과 도착 위치가 가로로 a 칸, 세로로 b 칸 떨어져 있다면, 이동방향 부분은 a + b의 길이를 갖게 된다.

Fig. 3.

Example of direction ordering chromosome.

정지시간을 표현한 뒷부분은 로봇이 멈춰 있는 시간을 표현한다. 정지시간은 1 단위마다 두 시간 간격 동안 정지하는 것을 의미한다. 정지시간 부분의 첫 번째 요소는 출발하기 전 멈춰 있는 시간을 의미하며, 그 뒤로 i(i 번째 요소는 이동방향 부분의 (i − 1) 번째 요소대로 움직이던 중간에 멈추는 시간을 의미한다. 따라서 이동방향부분의 길이가 n이면, 정지시간 부분은 n + 1이 된다.

2. 교차, 변이 연산자

하나의 방향 나열 염색체는 모든 로봇의 이동 경로를 담고 있으며, 이러한 염색체들을 무작위로 다수 생성하여 초기 개체군을 구성한다. 유전 알고리즘은 초기 개체군에서 시작하여 여러 세대를 거치면서 점차 최적해를 탐색한다. 각 세대마다 최적해에 가까운 염색체들이 부모 염색체로 선택되며, 이들 부모 염색체 간의 교차와 변이를 통해 다음 세대를 구성할 자식 염색체들이 생성된다. 이 과정에서 방향 나열 염색체에 적합한 교차 연산자와 변이 연산자를 사용해야 한다.

교차 연산자는 2개의 선별된 부모 염색체에 대해 각 로봇들의 이동방향과 정지시간 부분을 어떤 부모로부터 가져올지 무작위로 선택한다. 그리고 선택한 대로 조합하여 자식 염색체를 생성한다. 변이 연산자는 우선 변이 확률에 따라 개체군에서 변이가 발생할 염색체를 선택한다. 그 염색체에 대해 각 로봇의 이동방향 부분에서는 무작위로 2개의 유전자를 선택하여 자리를 바꾼다. 정지시간 부분에서는 무작위로 한 개의 유전자를 선택하여 1을 증가시키거나 감소시켰다. 그림 4는 교차 연산자와 변이 연산자의 동작 방식을 나타낸 것이다.

Fig. 4.

The crossover operator and the mutation operator.

IV. 2단계 유전 알고리즘

유전 알고리즘으로 해를 탐색하는 과정에서 적은 충돌횟수와 정지횟수를 함께 고려할 때, 로봇이 의미 없는 정지를 하거나 충돌횟수가 적절하게 감소하지 않는 경우가 있었다.

유전 알고리즘에서 목적에 따라 탐색과정을 2단계로 나누고, 1단계 탐색결과를 2단계의 초기 염색체로 설정하는 2단계 유전 알고리즘을 적용하면 더 좋은 해를 찾을 수 있다[14]. 본 연구에서도 2단계 유전 알고리즘을 적용하여 적은 충돌횟수를 가지며, 불필요한 정지가 없는 해를 찾고자 하였다. 1단계에서는 적합도 함수에서 충돌횟수만 고려하여 더 넓은 탐색공간에서 해를 탐색하고 충돌이 없는 해를 우선적으로 찾고자 하였다. 그리고 2단계에서는 적합도 함수에서 충돌횟수와 정지시간을 같이 고려하여 로봇이 정지하는 횟수를 감소시키고자 하였다.

최종적인 유전 알고리즘의 설계는 다음과 같다. 염색체 구조는 1단계, 2단계 모두 방향 나열 염색체 사용하였다. 초기 염색체는 1단계에서는 무작위로 생성한 개체군을 사용하였고, 2단계에서는 1단계에서 탐색되었던 개체군을 그대로 사용하였다. 적합도 함수는 1단계에서 충돌횟수만을 사용하여 식 (4)와 같이 설정하였고, 2단계에서는 충돌횟수와 로봇들의 정지횟수를 합해 식 (3)과 같이 설정하였다. 선택에서는 1단계, 2단계 모두 룰렛-휠 선택 방법(roulette wheel selection)을 사용하였다. 염색체 재생산 단계에서는 1단계, 2단계 모두 염색체의 이동방향 부분과 정지시간 부분에 대해 모두 교차 연산과 변이 연산을 적용하였다.

V. 시뮬레이션

시뮬레이션은 MATLAB을 이용하여 수행하였으며, 사용한 PC사양은 core i9 5.80 GHz 프로세서와 64GB RAM이었다. 시뮬레이션을 진행한 뒤 본 연구에서 제안한 알고리즘의 주요 특성을 확인하기 위해 두 가지 분석을 진행하였다. 첫째, 2단계 방식의 유전 알고리즘과 기존의 단일단계 방식 간의 비교를 통해 2단계 탐색의 효과를 입증하였다. 둘째, 기존의 다중 로봇 경로탐색 알고리즘으로 많이 알려진 CBS 알고리즘과의 비교를 통해 각 알고리즘의 특성을 분석하였다.

1. 단일단계와 2단계 유전 알고리즘 간 비교

제안한 2단계 유전 알고리즘의 1단계 탐색에서는 적합도 함수가 충돌만 고려하기 때문에 염색체의 다양성이 증가할 것이라고 예상하였다. 염색체의 다양성을 판단하는 기준으로 해밍거리(Hamming Dist)를 구해 비교할 수 있다[15]. 해밍거리란 같은 길이의 두 염색체에서 동일한 위치에서 다른 값을 갖는 유전자의 개수를 구한 것이다. P_i[k], P_j[k]가 각각 개체군의 i 번째, j 번째 염색체의 k 번째 위치의 값을 의미하고 염색체의 길이가 m일 때, 해밍거리는 식 (5)~(6)과 같다. 그리고, 개체군 내의 전체적인 염색체 다양성을 따질 수 있는 평균 해밍거리는 식 (7)과 같다.

$\[ f\left(a,b\right)=\left\{\begin{array}{cc}1& if a\ne b\\ 0& otherwise\end{array}\right. \]$

(5)

$\[ H_{i,j}=\sum _{k=1}^{m}f\left(P_i\left[k\right],P_j\left[k\right]\right) \]$

(6)

$\[ avg.HamDist=\sum _{i=1}^{n-1}\sum _{j=i+1}^n{H}_{i,j}/{}_n{}^{}{C}_2 \]$

(7)

그림 1과 같은 5×8 크기의 맵 환경에서 20대의 로봇을 대상으로 단일단계 유전 알고리즘과 2단계 유전 알고리즘을 실행하였다. 두 알고리즘 모두 식 (3)의 가중치 파라미터는 동일하게 설정하였으며, α = 1, β = 0.02 로 하였다. 그리고, 각 세대에서 개체군 내 최소 적합도를 가지는 염색체의 적합도 값과 충돌 횟수, 그리고 개체군의 평균 해밍거리를 계산하였다. 이 시뮬레이션은 로봇들의 시작 위치와 목표 위치를 변경해가며 총 100회 반복 수행되었고, 그 평균값을 그래프로 나타낸 것이 그림 5이다.

Fig. 5.

The comparison of fitness, collision and average hamming distance between single-stage and two-stage genetic algorithms.

그림 5의 상단은 세대 반복에 따른 적합도와 충돌 횟수의 변화를 나타낸다. 단일단계 유전 알고리즘은 두 그래프 모두 1 ~ 1000세대동안 초반에는 급격하게 감소한 뒤, 이후로 완만하게 우하향하는 형태를 보였다. 그리고, 2단계 유전 알고리즘의 충돌 횟수는 전 세대에서 단일단계 유전 알고리즘보다 더 적은 횟수를 보였다. 적합도 그래프는 1단계인 1~500세대까지는 충돌 횟수 그래프와 일치하였으며, 2단계인 501세대부터는 충돌 횟수와 정지 횟수를 모두 고려하여 일시적으로 적합도가 증가하였지만 세대가 진행됨에 따라 단일단계 유전 알고리즘보다 낮은 적합도로 수렴하였다.

그림 5의 하단은 평균 해밍 거리의 변화를 보여준다. 2단계 유전 알고리즘은 초반부터 약 640세대까지 단일단계 알고리즘보다 높은 평균 해밍 거리를 보였다. 이는 2단계 유전 알고리즘이 탐색 초반에 다양한 염색체를 탐색하며 충돌이 적은 해를 더 빠르게 찾아낼 수 있었음을 보여준다.

이후 같은 환경에서 로봇 대수를 5, 10, 15, 20, 25로 증가시키며 각 100번씩 시뮬레이션 하였다. 그리고 평균 충돌 수, 로봇당 평균 작업시간, 로봇당 평균 정지시간를 구해 표 1에 나타내었다.

Table 1.

Performance comparison between single-stage and two-stage genetic algorithms.

로봇 대수가 5일 경우, 단일단계 유전 알고리즘과 2단계 유전 알고리즘 모두에서 동일한 결과가 도출되었다. 그러나 5대를 초과하는 경우부터는 2단계 유전 알고리즘이 전반적으로 우수한 성능을 보였다. 평균 충돌 횟수는 약 14%~27%가량 감소하였으며, 로봇당 평균 작업시간은 1%~19%, 로봇당 평균 정지시간은 18%~46%까지 감소하는 경향을 보였다. 이러한 결과는 2단계 유전 알고리즘이 단일단계 유전 알고리즘과 비교하여 동일하거나 더 나은 최적해를 도출했음을 보여준다. 그리고, 방향 나열 염색체는 기존의 경로보다 더 멀리 돌아가는 우회경로는 생성할 수 없기 때문에, 평균 정지시간 만큼 평균 작업시간이 증가하였다.

2. CBS 알고리즘과의 비교

기존의 알고리즘과 제안한 알고리즘의 비교를 위해 CBS 알고리즘과 비교를 진행하였다. CBS 알고리즘은 로봇 대수가 늘어나면, 탐색 시간이 급격하게 늘어나는 특징이 있다. 따라서 600 s의 연산시간 제한을 두어 이를 초과할 경우 탐색을 중지하고 마지막으로 탐색했던 High level search의 Constraint Tree의 노드를 최종해로 설정하여 결과를 도출하였다. Low level search에서는 A* 알고리즘을 적용하여 각 로봇의 경로를 탐색하였고, 기존 문제와 동일하게 로봇은 움직이기 시작 전과 통로 중앙에서만 멈출 수 있게 하였다.

제안한 알고리즘과 CBS 알고리즘 모두 그림 1과 같은 5×8 맵에서 로봇 대수를 5, 10, 15, 20, 25로 증가시키며, 각 100번씩 시뮬레이션하였다. 그리고 표 2는 평균 충돌 수, 로봇당 평균 작업시간, 로봇당 평균 정지시간 그리고 각 알고리즘의 평균 연산시간을 나타낸 결과이다.

Table 2.

Performance comparison between CBS and the proposed algorithm.

CBS 알고리즘은 10대 이하의 로봇에서는 충돌이 없는 경로와 빠른 연산 속도를 도출하였지만, 15대 이상의 로봇에서는 연산 시간이 크게 증가하여 제한시간 600s를 넘어가는 경우도 존재하게 되었다. 특히, 25대일 경우는 100번 중 94번의 시뮬레이션이 제한시간을 초과하였다. CBS 알고리즘은 해를 찾는데 성공하면 충돌이 없는 경로를 보장하지만, 이번 시뮬레이션에서는 시간제한을 두어 중단시켰기 때문에 시간 초과가 발생한 15대 이상에서 충돌이 존재하는 경우가 발생하였다.

이에 반해, 제안한 알고리즘은 15대 이상의 경우에서 비교적 빠른 연산속도와 적은 충돌횟수를 보였다. 다만, 10대 이하에서는 CBS 알고리즘보다 조금 더 큰 연산시간과 충돌 횟수를 보였다. 로봇당 평균 작업시간과 정지시간은 모든 경우에서 CBS 알고리즘이 더 적은 작업시간을 보였다. 이는 CBS 알고리즘은 Best-First Search방식으로 작업시간의 합이 증가하지 않는 해를 우선적으로 탐색하지만, 제안한 알고리즘은 충돌을 회피하기 전략으로써 정지하는 것을 적극 활용하였기 때문으로 보인다.

IV. 결론

본 연구에서는 다중로봇 경로계획 문제에 2단계 유전 알고리즘을 적용하여 충돌을 최소화하는 경로 탐색 방법을 제안하였다. 로봇의 이동방향과 정지시간을 유전자로 구성한 방향 나열 염색체를 사용하였고, 이를 기반으로 2단계 유전 알고리즘을 도입하여 탐색 효율을 향상시켰다. 1단계에서는 충돌 없는 해를 우선적으로 탐색하고, 2단계에서는 정지시간을 줄이는 방식으로 탐색을 이어감으로써 염색체 탐색공간을 넓혀서 더 적은 충돌과 효율적인 경로생성을 목표하였다.

다음 두 가지 시뮬레이션을 통해 제안한 알고리즘의 성능을 분석하였다. 첫 번째로, 단일단계와 2단계 유전 알고리즘을 비교하였다. 개체군의 평균 해밍거리를 구해 2단계 유전 알고리즘에서 염색체의 다양성이 증가함을 보였고, 충돌횟수와 로봇 당 평균 작업시간이 감소함을 보였다. 두 번째로, CBS 알고리즘과 비교를 진행하였다. 로봇 수를 5대 ~ 25대로 다양하게 시뮬레이션 한 결과, CBS는 15대 이상에서 연산시간이 크게 증가하고 충돌횟수가 증가하였다. 하지만 제안한 알고리즘은 15대 이상에서도 준수한 연산시간과 충돌횟수를 유지하였다.

본 연구는 기존 연구들과 비교해 몇 가지 중요한 차별성과 기여점을 가진다. 먼저, 기존의 유전 알고리즘을 사용한 다중 로봇 연구들은 주로 작업지의 방문 순서를 결정하는 경로계획의 사전 단계에 국한되어 유전 알고리즘을 활용하였다. 반면, 본 연구는 경로계획 문제 자체에 유전 알고리즘을 직접적으로 적용하였다. 또한, 본 연구는 충돌 회피와 정지 시간 최소화라는 이중의 목표를 달성하기 위해 2단계 유전 알고리즘을 도입하여 탐색효율을 향상시켰다. 그리고, 기존의 휴리스틱 기반 알고리즘들이 동작하기 어려운 많은 로봇들이 있는 환경에서도 비교적 우수한 성능을 보였다.

다만, 본 연구에는 다음과 같은 한계도 존재한다. 첫째, 제안된 알고리즘은 충돌이 최소화된 해를 찾고자 하였지만 충돌이 없는 해를 보장하지 못한다는 점이다. 둘째, 알고리즘은 일정 간격으로 장애물이 배치된 격자 기반의 제한적인 환경을 전제로 동작하므로, 일반적인 환경에서는 적용이 어려울 수 있다. 셋째, 현재 방법은 정지 전략에만 의존하고 있어, 우회 경로를 생성할 수 없고 복잡한 충돌 상황에서는 제한된 대응만 가능하다. 마지막으로, 경로 최적성 측면에서 전체 경로의 최소 길이를 보장하지 않는다는 점이다.

향후 연구에서는 충돌 회피 성능을 더욱 강화하고, 다양한 환경에서의 적용 가능성을 확보하기 위해 비격자 기반 환경에서도 적용 가능한 알고리즘을 연구하고자 한다. 그리고 우회 경로 생성, 그리고 경로 최적성 개선을 위한 보완 연구를 진행할 예정이다.

Acknowledgments

본 연구는 2023년도 산업통상자원부 및 산업기술평가관리원(KEIT) 연구비 지원(20023626)을 받았음.

REFERENCES

• M. T. Benavides-Robles, G. H. Valencia-Rivera, J. M. Cruz-Duarte, I. Amaya, and J. C. Ortiz-Bayliss, “Robotic mobile fulfillment system: a systematic review,” IEEE Access, vol. 12, pp. 16767-16782, Jan. 2024. [https://doi.org/10.1109/ACCESS.2024.3359434]
• A. Wang, “Intelligent warehouse multi-robot scheduling system based on improved A* algorithm,” Proc. of the 2024 3rd Conference on Fully Actuated System Theory and Applications, pp. 1305-1310, May 2024. [https://doi.org/10.1109/FASTA61401.2024.10595280]
• J. W. Park, D. H. Oh, and H. J. Kim, “A survey on collision avoidance for multi-robot systems,” Journal of Institute of Control, Robotics and Systems (in Korean), vol. 30, no. 4, pp. 402-411, Apr. 2024. [https://doi.org/10.5302/J.ICROS.2024.24.0033]
• S. Lin, A. Liu, J. Wang, and X. Kong, “A review of path-planning approaches for multiple mobile robots,” Machines, vol. 10, no. 9, Art. no. 773, Sep. 2022. [https://doi.org/10.3390/machines10090773]
• D. Silver, “Cooperative pathfinding,” Proc. of the 1st Artificial Intelligence and Interactive Digital Entertainment Conference, vol. 1, no. 1, pp. 117-122, Jan. 2005. [https://doi.org/10.1609/aiide.v1i1.18726]
• T. Standley, “Finding optimal solutions to cooperative pathfinding problems,” Proc. of the 24th Conf. Artificial Intelligence, vol. 24, no. 1, pp. 173-178, July 2010. [https://doi.org/10.1609/aaai.v24i1.7564]
• G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, “Conflict-based search for optimal multi-agent pathfinding,” Artificial Intelligence, vol. 219, pp. 40-66, Feb. 2015. [https://doi.org/10.1016/j.artint.2014.11.006]
• T. Bektas, “The multiple traveling salesman problem: an overview of formulations and solution procedures,” Omega, vol. 34, no. 3, pp. 209-219, June 2006. [https://doi.org/10.1016/j.omega.2004.10.004]
• T. Zhang, W. A. Gruver, and M. H. Smith, “Team scheduling by genetic search,” Proc. of the 2nd International Conf. on Intelligent Processing and Manufacturing of Materials, vol. 2, pp. 839-844, July 1999. [https://doi.org/10.1109/IPMM.1999.791495]
• A. E. Carter and C. T. Ragsdale, “A new approach to solving the multiple traveling salesperson problem using genetic algorithms,” European Journal of Operational Research, vol. 175, no. 1, pp. 246-257, Nov. 2006. [https://doi.org/10.1016/j.ejor.2005.04.027]
• R. A. Saeed, D. R. Recupero, and P. Remagnino, “The boundary node method for multi‐robot multi‐goal path planning problems,” Expert Systems, vol. 38, no. 6, Art. no. e0181747, Sep. 2021. [https://doi.org/10.1111/exsy.12691]
• J. Han, D. Wang, F. Liu, and Z. Zhao, “Multi-AGV path planning with double-path constraints by using an improved genetic algorithm,” PLOS ONE, vol. 12, no. 7, Art. no. e12691, July 2017. [https://doi.org/10.1371/journal.pone.0181747]
• J. H. Park and M. J. Hwang, “Multi-robot path planning method based on genetic algorithm with direction ordering chromosome,” Proc. of the 24th International Conf. on Control, Automation and Systems, pp. 1-2, Oct. 2024.
• D. Rooyani and F. M. Defersha, “An efficient two-stage genetic algorithm for flexible job-shop scheduling,” IFAC-Papers OnLine, vol. 52, no. 13, pp. 2519-2524, Dec. 2019. [https://doi.org/10.1016/j.ifacol.2019.11.585]
• W. G. Frederick, R. L. Sedlmeyer, and C. M. White, “The hamming metric in genetic algorithms and its application to two network problems,” Proc. of the 1993 ACM/SIGAPP Symposium on Applied Computing: States of the Art and Practice, pp. 26–130, Mar. 1993. [https://doi.org/10.1145/162754.162835]